Last active
December 6, 2021 17:24
-
-
Save davidinga/259e9feeefe46cfa41c3dc66c832aa76 to your computer and use it in GitHub Desktop.
Move zeros to end of array in place
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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