LeetMotion
Given an integer array nums, move all 0s to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
insertPos that tracks where the next non-zero element should be written. Start at index 0. As you scan forward with i, whenever you find a non-zero, write it to nums[insertPos] and advance both pointers. insertPosonly moves forward when it "earns" it — by receiving a non-zero value.i gets written to position insertPos (which is always ≤ i). We don't care what was at insertPos before — it was either a zero we're discarding, or a value already safely copied. After the first pass, positions 0..insertPos-1 contain all non-zeros in original order.insertPos points to the first position that doesn't have a valid non-zero. Everything from insertPos to n-1 should be zeros. Simply loop from insertPos to n-1 setting each element to 0. This two-phase approach is O(n) time and O(1) space — perfectly in-place.Imagine a filing cabinet where important documents (non-zeros) are scattered among blank pages (zeros). You go through the cabinet left to right, pulling out every important document and re-filing it at the front — maintaining their original order. Once all important documents are at the front, you stuff blank pages into every remaining slot at the back. That's exactly what insertPosdoes: it marks "the next open slot at the front."
The most intuitive way is to create a new array of the same size. We iterate through the original array and copy all non-zero elements into the new array. Then, since the remaining spots are already filled with zeros (if we initialize it with zeros), we simply copy the new array back into the original array to satisfy the in-place constraint (sort of).
ans of size n filled with 0.ans.nums. If an element is non-zero, append it to ans.ans back into nums.Why it's not optimal: This violates the strict "in-place without extra memory" constraint of the problem, using O(n) extra space.
def moveZeroes(nums): ans = [0] * len(nums) idx = 0 for num in nums: if num != 0: ans[idx] = num idx += 1 for i in range(len(nums)): nums[i] = ans[i]
Use an insertPos pointer as a write head. In the first pass, copy every non-zero element to nums[insertPos] and advance insertPos. In the second pass, fill positions insertPos through n-1 with zeros.
insertPos = 0.i: if nums[i] != 0, write nums[insertPos] = nums[i], then insertPos++.insertPos < len(nums): set nums[insertPos] = 0, insertPos++.
Discussion
…