Problem Description

You are given an integer array nums that contains both zero and non-zero elements. Your task is to rearrange the array by moving all zeros to the end while keeping the relative order of non-zero elements unchanged.

For example, if the input array is [0, 1, 0, 3, 12], after moving zeros to the end, it should become [1, 3, 12, 0, 0]. Notice that the non-zero elements 1, 3, 12 maintain their original relative order.

The key requirements are:

• All zeros must be moved to the end of the array
• The relative order of non-zero elements must be preserved (if element a appears before element b in the original array, and both are non-zero, then a must still appear before b in the modified array)
• You must modify the array in-place without creating a copy of the array
• The operation should be done directly on the input array nums

The solution uses a two-pointer technique where pointer k tracks the position where the next non-zero element should be placed. As we iterate through the array with index i, whenever we find a non-zero element at position i, we swap it with the element at position k and increment k. This ensures that all non-zero elements are moved to the front of the array in their original order, while zeros naturally end up at the end.

Intuition

When we need to move all zeros to the end while maintaining the relative order of non-zero elements, we can think of it as partitioning the array into two sections: a section for non-zero elements at the front and a section for zeros at the back.

The key insight is that we don't actually need to explicitly "move" zeros. Instead, we can focus on placing all non-zero elements in their correct positions at the beginning of the array. Once all non-zero elements are positioned correctly at the front, the zeros will naturally occupy the remaining positions at the end.

Think of it like organizing a bookshelf: instead of removing all the empty spaces first and then rearranging books, we can simply slide each book to the leftmost available position. The empty spaces will automatically end up on the right side.

This leads us to maintain a pointer k that represents the "next available position" for a non-zero element. As we scan through the array:

• When we encounter a non-zero element at position i, we know it should be placed at position k
• We swap the elements at positions i and k
• We increment k to point to the next available position

Why does swapping work instead of just overwriting? Because if k and i are at different positions, the element at position k is either:

1. A zero that needs to move to the back anyway
2. Already processed (when k = i), in which case swapping with itself doesn't change anything

This approach elegantly handles all cases while maintaining the relative order of non-zero elements and achieving the goal in a single pass through the array with O(1) extra space.

Solution Approach

We implement the two-pointer technique to solve this problem efficiently in a single pass through the array.

Algorithm Steps:

1. Initialize the pointer: We start with a pointer k = 0 which represents the position where the next non-zero element should be placed.

2. Iterate through the array: We traverse the array using enumerate(nums) to get both the index i and value x of each element.

3. Process non-zero elements: For each element x:

   • If x is non-zero (the condition if x: evaluates to True for any non-zero number)
   • We swap the current element at position i with the element at position k using Python's tuple unpacking: nums[k], nums[i] = nums[i], nums[k]
   • We increment k by 1 to point to the next available position for a non-zero element

Why this works:

• When we encounter a non-zero element, we place it at position k, which maintains the relative order since we're processing elements sequentially
• The swap operation ensures that:
  • If k == i, we're swapping an element with itself (no change)
  • If k < i, we're moving a non-zero element forward and sending a zero (or already processed element) backward
• After processing all elements, the first k positions contain all non-zero elements in their original order, and positions from k to the end contain all zeros

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the array, as we make a single pass through the array
• Space Complexity: O(1) as we only use a constant amount of extra space (the pointer k)

The beauty of this solution lies in its simplicity - by maintaining just one pointer and using swaps, we achieve the desired result without any complex logic or additional data structures.

Example Walkthrough

Let's walk through the solution with the array [0, 1, 0, 3, 12].

Initial Setup:

• Array: [0, 1, 0, 3, 12]
• Pointer k = 0 (next position for non-zero element)

Step 1: i = 0, x = 0

• Element is 0 (zero), so we skip it
• Array: [0, 1, 0, 3, 12]
• k remains at 0

Step 2: i = 1, x = 1

• Element is 1 (non-zero), so we swap nums[k] with nums[i]
• Swap nums[0] with nums[1]: [1, 0, 0, 3, 12]
• Increment k: k = 1

Step 3: i = 2, x = 0

• Element is 0 (zero), so we skip it
• Array: [1, 0, 0, 3, 12]
• k remains at 1

Step 4: i = 3, x = 3

• Element is 3 (non-zero), so we swap nums[k] with nums[i]
• Swap nums[1] with nums[3]: [1, 3, 0, 0, 12]
• Increment k: k = 2

Step 5: i = 4, x = 12

• Element is 12 (non-zero), so we swap nums[k] with nums[i]
• Swap nums[2] with nums[4]: [1, 3, 12, 0, 0]
• Increment k: k = 3

Final Result: [1, 3, 12, 0, 0]

Notice how:

• The pointer k always marks where the next non-zero should go
• Non-zero elements (1, 3, 12) maintain their original relative order
• All zeros naturally end up at the end of the array
• We achieved this with just one pass and constant extra space

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once using a single for loop with enumerate(), performing constant-time operations (comparison and swap) for each element.

The space complexity is O(1). The algorithm only uses a constant amount of extra space - a single integer variable k to track the position where the next non-zero element should be placed, and the loop variables i and x. The swapping operation is done in-place without requiring any additional data structures that scale with input size.

Common Pitfalls

1. Unnecessary Operations When No Zeros Exist

The current solution performs swaps even when non_zero_position == current_index, which happens when there are no zeros encountered yet. This leads to redundant self-swaps that don't change the array but still consume CPU cycles.

Example: For array [1, 2, 3, 4, 5] with no zeros, the algorithm performs 5 unnecessary swap operations where each element swaps with itself.

Solution: Add a condition to only swap when the pointers are different:

if current_value != 0:
    if non_zero_position != current_index:
        nums[non_zero_position], nums[current_index] = nums[current_index], nums[non_zero_position]
    non_zero_position += 1

2. Misunderstanding the Two-Pointer Concept

A common mistake is trying to use two pointers from opposite ends of the array (one from start, one from end). This approach breaks the relative order requirement because elements from the end would be moved to earlier positions.

Wrong Approach Example:

# DON'T DO THIS - breaks relative order
left, right = 0, len(nums) - 1
while left < right:
    if nums[left] == 0:
        nums[left], nums[right] = nums[right], nums[left]
        right -= 1
    else:
        left += 1

This would transform [0, 1, 0, 3, 12] into something like [12, 1, 3, 0, 0], breaking the relative order of non-zero elements.

3. Creating a New Array Instead of In-Place Modification

Some might be tempted to create a new array to store non-zero elements first, then append zeros:

# DON'T DO THIS - violates space complexity requirement
non_zeros = [x for x in nums if x != 0]
zeros = [0] * (len(nums) - len(non_zeros))
nums[:] = non_zeros + zeros  # Even though we assign back, we used O(n) extra space

4. Using Multiple Passes Unnecessarily

Another pitfall is making the solution more complex with multiple passes:

# Inefficient approach with multiple passes
# First pass: count zeros
zero_count = nums.count(0)
# Second pass: collect non-zeros
write_pos = 0
for num in nums:
    if num != 0:
        nums[write_pos] = num
        write_pos += 1
# Third pass: fill remaining with zeros
for i in range(write_pos, len(nums)):
    nums[i] = 0

While this works, it's less elegant and requires multiple iterations when one suffices.

5. Forgetting Edge Cases

Don't forget to consider:

• Empty array []
• Array with all zeros [0, 0, 0]
• Array with no zeros [1, 2, 3]
• Single element arrays [0] or [1]

The original solution handles all these cases correctly, but modifications might introduce bugs if not carefully tested against these scenarios.