Move Zeroes to End

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 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

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.