283. Move Zeroes - Detailed Explanation

This brute-force approach does the job, but it’s not very efficient. Removing an element from the middle of an array (or list) is costly because it shifts all subsequent elements left by one. In the worst case (e.g., an array full of zeroes), you might remove and append for each element. If the array has n elements, each removal can take up to O(n) time (because of shifting), and doing that n times leads to O(n²) time complexity. The space complexity is O(1) (in-place) since we only modify the array itself.

Complexity Analysis (Brute Force): For an array of length n, the time complexity is O(n²) in the worst case . This happens when we have many zeroes and each zero causes a shift of a large portion of the array. The space complexity is O(1) because we do all operations in the original array without extra storage (the operations like pop and append modify the array in place).

While this approach is easy to understand, we need a more efficient solution for large inputs (recall that n can be up to 10,000). Next, we'll explore an optimized approach that handles the task in linear time.

Approach 2: Optimized Approach (Two-Pointer Technique)

Idea: The optimal solution uses the two-pointer technique to rearrange the array in one pass (linear time). The concept is to use one pointer (often called k or lastNonZeroIndex) to mark the position where the next non-zero element should be placed, and another pointer (i) to scan through the array looking for non-zero elements. As you find non-zero values, you swap them toward the front (or copy them forward), and leave zeroes behind to eventually occupy the end of the array.

• Explanation:
  Initialize an insert position pointer k = 0. This k will track the index where the next non-zero should go. Then iterate i through each index of the array:

  1. If nums[i] is non-zero, we want that value to appear as early in the array as possible (while preserving relative order). So we swap nums[i] with nums[k]. This moves the non-zero value into position k, and whatever was at nums[k] (which might be 0) goes to position i.

  2. After swapping, increment k by 1 to point to the next position for the following non-zero. (In other words, k always points to the first index that is currently occupied by a zero in the "front part" of the array.)

  3. If nums[i] is 0, do nothing and just continue – k will not change, so it will still point to this index, which is a candidate for the next non-zero swap.

By the end of the pass, all non-zero elements have been moved to the front [0...k-1] in their original order, and k will be at the index of the first 0. All remaining positions from k to end of array will be filled with 0. This satisfies the problem requirements, and we've done it all in one pass.

• Why it works: This method ensures that each non-zero element is swapped at most once, and each element is examined exactly once. It maintains the order of non-zero elements because we only ever swap a non-zero with a zero (and zeros have no specific relative order to maintain among themselves). The pointer k moves forward only when a non-zero is placed, so it guarantees that positions before k are finalized as non-zero and in the correct order.

• Example (Two-Pointer): Consider nums = [0, 1, 0, 3, 12]. We trace the algorithm step by step:

  • Start: nums = [0, 1, 0, 3, 12], k = 0 (position for next non-zero).

  • i = 0: nums[0] is 0, so do nothing. (k remains 0, array unchanged)

  • i = 1: nums[1] is 1 (non-zero). Swap nums[1] with nums[k] (nums[0]). After swap, array becomes [1, 0, 0, 3, 12]. Increment k to 1.

  • i = 2: nums[2] is 0, do nothing. (k still 1, array unchanged [1, 0, 0, 3, 12])

  • i = 3: nums[3] is 3 (non-zero). Swap nums[3] with nums[k] (nums[1]). Array becomes [1, 3, 0, 0, 12]. Increment k to 2.

  • i = 4: nums[4] is 12 (non-zero). Swap nums[4] with nums[k] (nums[2]). Array becomes [1, 3, 12, 0, 0]. Increment k to 3.

  • End of loop. All non-zeros [1,3,12] are now at the front in order, and all zeros are at the end.

We can illustrate this process in a table:

After this single pass, the array is [1,3,12,0,0], which is exactly the expected result. Notice that k advanced only when a non-zero was encountered, and at the end k = 3 which indicates index of first trailing zero.

Two Pointer Implementation (Python)

In the code above, the move_zeroes function implements the two-pointer approach. We then test it with the example array. The result shows the zeroes moved to the end as expected. The function operates in-place, so the original list arr is modified and printed to verify the outcome.

Implementation in Java

Here, the moveZeroes method uses the same two-pointer strategy. We print the array before and after calling moveZeroes to verify that the zeros have been moved correctly. The use of Arrays.toString helps display the array in a readable format. Just like the Python version, this Java implementation runs in-place and in linear time.

Complexity Analysis

Let's summarize the time and space complexity for each approach discussed:

• Brute Force Approach: Time complexity is O(n²) in the worst case . This quadratic time arises because for each zero element, we potentially shift a large portion of the array. Space complexity is O(1) (in-place). This approach is acceptable for small arrays but becomes inefficient as n grows large.

• Optimized Two-Pointer Approach: Time complexity is O(n) – we make one pass through the array of length n, doing constant work for each element. Space complexity is O(1) since we only use a few extra variables. This approach is efficient even for the maximum array length of 10,000 (or more), and is the recommended solution.

For example, if n = 10^4 (the upper constraint), the optimized approach will roughly perform 10,000 operations, whereas the brute force could potentially perform on the order of 50 million operations (in the worst distribution of zeroes), which is a significant difference.

Common Mistakes

Beginners might run into some pitfalls with this problem. Here are a few common mistakes and misconceptions:

• Modifying the array during iteration incorrectly: If you remove or insert elements (like in the brute-force approach) using a standard for loop, you might skip elements or go out of bounds. For example, doing something like for i in range(len(nums)): if nums[i] == 0: nums.pop(i) will shift the list while you're iterating, causing you to miss the next element or encounter an index error. When removing elements in a loop, it's safer to use a while loop or iterate backwards, or better, use the two-pointer method to avoid this complexity.

• Not preserving order of non-zero elements: A solution that simply sorts the array or partitions without care might clump all numbers without preserving their original order. For instance, one might think to sort the array so that all 0's come last; however, sorting would destroy the relative order of non-zero elements (and also be less efficient than O(n) in most cases). The problem specifically requires maintaining the original order of the non-zero elements, so any approach that doesn't do that will be incorrect.

• Using extra space when not allowed: It's easy to solve the problem by creating a new array (e.g., filter out zeros then add them at end), but the problem explicitly asks for an in-place solution. A common mistake is to return a new array or use an additional list to store results. In an interview or on LeetCode, that would not meet the requirements (and on LeetCode, the function is void, so creating a new array won't replace the original). Make sure your final solution operates on the input array itself.

• Off-by-one errors in shifting or filling: When implementing manually (without high-level operations), people sometimes get the indices wrong when shifting elements or filling in zeros. For example, forgetting to update the length of effective array when doing the brute-force removal, or putting the first zero in the wrong position. Tracing through a simple example (as we did in the walkthrough) or writing tests for edge cases can help catch these issues.

• Inefficient swapping or unnecessary operations: In the two-pointer approach, some might swap elements even when i and k are the same index (which is harmless but unnecessary). This isn't exactly a bug (it still produces correct output), but it's an inefficiency. A minor improvement is to check if (i != k) before swapping, to avoid pointless self-swaps. However, this doesn't change big-O complexity; it's just a micro-optimization.

Understanding the logic behind the two-pointer method and carefully handling the indices will help avoid these mistakes. Always test your solution on a variety of inputs, including edge cases, to ensure correctness.

Edge Cases

When solving "Move Zeroes", consider the following edge cases to ensure your solution handles them gracefully:

• All elements are zero: e.g. nums = [0, 0, 0]. The output should be the same as the input (all zeros). The algorithm should not crash or misplace elements in this scenario. The two-pointer method would simply leave all elements as 0 (with k never moving from 0, or moving through and ending at 0).

• No zeroes in the array: e.g. nums = [1, 2, 3]. The output should be identical to the input, since there are no zeroes to move. An in-place algorithm should ideally recognize that no changes are needed (for the two-pointer approach, k will increment every time and end up equal to n, and effectively the array remains unchanged).

• Array of length 1: e.g. nums = [0] or nums = [5]. Single-element arrays should remain the same after the operation (either already a zero at end, or a single non-zero which is trivially "at front"). Ensure that your loops handle length 1 without issues (they generally will, but it's good to note).

• Zeroes already at the end: e.g. nums = [4, 1, 0, 0]. The output should be the same as input in this case, since the zeroes are already in the correct position. A correct algorithm will not disturb the order. The two-pointer approach, for example, will still swap non-zeroes with themselves in this case and leave the array as is.

• Alternating zero and non-zero: e.g. nums = [0, 7, 0, 7, 0, 7]. This is a pattern where every non-zero is separated by zeroes. After moving zeroes, all the 7's should come first and all the 0's last: [7, 7, 7, 0, 0, 0]. This tests that your method truly gathers all non-zeroes at front and all zeroes at back without mixing the sequence.

• Negative numbers and other values: e.g. nums = [0, -1, 0, -2, 0, -3]. The actual values (positive, negative, etc.) aside from zero don't matter to the algorithm – it should treat any non-zero as valid to keep. But it's good to ensure your code doesn't inadvertently treat negative or other values as special. The expected output would be [-1, -2, -3, 0, 0, 0] in this example.

By testing these edge cases, you can be confident that your solution works for all valid inputs and respects the problem constraints.

Alternative Variations

The "move zeroes" problem is a specific instance of a more general class of problems where you need to partition or rearrange elements based on some condition. Some variations and related scenarios include:

• Moving a different target value: Instead of zero, the task might be to move all occurrences of a particular value (say, all -1 or all "#") to the end (or beginning). The approach would be very similar: you'd use a condition if nums[i] != target (or the opposite) to decide when to swap. The two-pointer technique can be generalized to any "segregate X from others" problem.

• Move zeroes to the front: A twist on the problem could be to move all zeroes to the start of the array, while keeping the order of non-zeroes the same. This would simply involve a similar approach but perhaps scanning from the end or using two pointers from opposite ends. Alternatively, you could still do it in one pass by iterating from the end and moving non-zeroes towards the end (or using a backwards pointer for zero placement).

• Stable partitioning by other properties: For example, "move all even numbers to the front and odds to the back" or "move all negative numbers to the front". If the relative order needs to be preserved, the approach is again analogous: two-pointer or two-pass (gather and fill) methods can be used. If relative order doesn't need to be preserved, there are even more efficient partitioning methods (like the Lomuto partition scheme from quicksort) that can be used.

• Two-pass approach with counting: A simple variant solution is: count the number of zeroes, then fill the array with all the non-zero elements in their original order, and finally fill the remaining slots with zeroes. This is effectively what the two-pointer method (in the non-swapping variant) does, but conceptually it's a different way to think about it. This approach is straightforward but involves two passes through the array (still O(n) time). It's worth noting as an alternative solution, especially in contexts where simplicity is favored over the absolute optimal number of operations.

• Using built-in functions (for high-level languages): In Python, for instance, one could do something like: nonzeros = [x for x in nums if x != 0] and then nums[:] = nonzeros + [0]*zero_count. This achieves the result in a very concise way, but it violates the in-place constraint because it creates new lists under the hood (and uses extra space). Still, it's a variation you might think of. Similarly, one could sort with a custom key (treat 0 as greater than any non-zero) to move zeros, but again that doesn't preserve relative order unless the sort is stable and you're careful with the key.

In interviews or practice, it's good to solve the problem with the intended constraints (in-place, O(n)), but being aware of these variations and alternative approaches can help improve your understanding and adaptability for other problems.

Related Problems

Moving zeroes is conceptually related to several other problems that involve array manipulation and two-pointer techniques. If you want to practice further, here are some related problems:

• Remove Element (LeetCode 27): Remove all occurrences of a given value from an array in-place and return the new length. This is very similar in spirit – essentially "move all X's out" (you don't need to maintain the order of removed elements, but you do maintain order of the rest). The two-pointer approach is commonly used here as well.

• Remove Duplicates from Sorted Array (LeetCode 26): Another in-place array operation using two pointers. You need to remove duplicate values from a sorted array such that each element appears only once. While the context is different, the idea of using one pointer to build the result in-place is analogous.

• Sort Array by Parity (LeetCode 905): Move all even numbers to the front of the array and odd numbers to the back (order of evens or odds doesn't necessarily need to be preserved here unless stated). This can be solved with an approach similar to move zeroes (treat even as "non-zero", odd as "zero", for example, in terms of partitioning logic).

• Duplicate Zeros (LeetCode 1089): This is another array manipulation problem where you have to duplicate each occurrence of zero in the array and shift the remaining elements to the right. It's a different outcome, but it also involves careful in-place operations and shifting elements. Mastering the move-zeroes problem helps in understanding how to approach this one (and vice versa).

• Sort Colors (LeetCode 75): Also known as the Dutch National Flag problem, where you have to sort an array of 0s, 1s, and 2s in-place (grouping all 0s, then 1s, then 2s together). This is a classic problem that uses a two-pointer (or three-pointer) technique to partition the array. It's a bit more complex, but the idea of moving certain values to the end (and others to the beginning) in one pass is related.