Move Zeroes to End

[MyrinNew]

In array manipulation problems, a common task is to move all zeroes to the end of an array while keeping the relative order of non-zero elements. This is especially important for optimizing in-place operations in coding interviews.


Problem Statement


Given an integer array nums, move all 0s to the end of it while maintaining the relative order of the non-zero elements.


You must do this in-place without making a copy of the array.


Examples:


Input: [0,1,0,3,12] → Output: [1,3,12,0,0]

Input: [0] → Output: [0]


Constraints:


1
-2^31


Approach


Use a pointer lastNonZeroFoundAt to track the position where the next non-zero element should go.

Traverse the array. For each non-zero element, place it at the lastNonZeroFoundAt index and increment the pointer.

After placing all non-zero elements, fill the remaining positions with 0s.


This approach ensures relative order is preserved and the array is modified in-place.


Time Complexity: O(n) – single pass through the array

Space Complexity: O(1) – in-place solution


Python Code


class Solution:

def moveZeroes(self, nums):

# Pointer for the next non-zero element

lastNonZeroFoundAt = 0





# Step 1: Move non-zero elements forward

for i in range(len(nums)):

if nums[i] != 0:

nums[lastNonZeroFoundAt] = nums[i]

lastNonZeroFoundAt += 1


# Step 2: Fill remaining positions with 0
for i in range(lastNonZeroFoundAt, len(nums)):
nums[i] = 0









Example Test Cases

-------------------------------

sol = Solution()


nums1 = [0, 1, 0, 3, 12]

sol.moveZeroes(nums1)

print(nums1) # Output: [1, 3, 12, 0, 0]


nums2 = [0]

sol.moveZeroes(nums2)

print(nums2) # Output: [0]


nums3 = [4, 2, 4, 0, 0, 3, 0, 5, 1, 0]

sol.moveZeroes(nums3)

print(nums3) # Output: [4, 2, 4, 3, 5, 1, 0, 0, 0, 0]


Explanation


For the input [0, 1, 0, 3, 12]:

lastNonZeroFoundAt = 0

Traverse the array and place non-zero numbers at the lastNonZeroFoundAt index: [1, 3, 12, 3, 12]

Fill remaining positions with 0: [1, 3, 12, 0, 0]

The relative order of non-zero elements is maintained.

Works in-place and is efficient.


Key Takeaways

Keep track of the position for the next non-zero element.

Move non-zero elements forward and fill zeros at the end.

Works in O(n) time and O(1) space, suitable for large arrays.




More...