Skip to content

Instantly share code, notes, and snippets.

@davidinga
Last active December 6, 2021 17:24
Show Gist options
  • Save davidinga/259e9feeefe46cfa41c3dc66c832aa76 to your computer and use it in GitHub Desktop.
Save davidinga/259e9feeefe46cfa41c3dc66c832aa76 to your computer and use it in GitHub Desktop.
Move zeros to end of array in place
/*
Move zeros to end of array in place.
Brute force
Loop through elements n times
When 0 found
Bubble up 0 to end, perform swaps until swap performed with last element
O(n^2) time | O(1) space
Loop through elements n times
When 0 found
Shift all alements to right by index -= 1
Place zero at last index
O(n^2) time | O(1) space
Can optimize this by having a pointer segmenting the 0's from the other numbers
Would only need to shift, or bubble up to the index at the pointer
Optimized approach
Loop through elements, while indexOfFirstZero or indexOfNextNonZero < arr.count
indexOfFirstZero, pretty self explanitory
indexOfNextNonZero, pretty self explanitory
Increment indexOfFirstZero until zero found
Increment indexOfNextNonZero until non zero found
Perform a swap
O(n) time | O(1) space
n
z
[1, 10, 2, 8, 3, 6, 4, 5, 7, 0, 0, 0, 0, 0]
*/
func moveZerosToEnd(arr: [Int]) -> [Int] {
var arr = arr
var indexOfFirstZero = 0
var indexOfNextNonZero = 0
while indexOfFirstZero < arr.count && indexOfNextNonZero < arr.count {
(arr[indexOfFirstZero], arr[indexOfNextNonZero]) = (arr[indexOfNextNonZero], arr[indexOfFirstZero])
while indexOfFirstZero < arr.count, arr[indexOfFirstZero] != 0 {
indexOfFirstZero += 1
}
indexOfNextNonZero = indexOfFirstZero
while indexOfNextNonZero < arr.count, arr[indexOfNextNonZero] == 0 {
indexOfNextNonZero += 1
}
}
return arr
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment