Problem Description
Given an integer array nums, move all zeros to the end of the array while maintaining the relative order of the non-zero elements. This operation must be performed in-place without creating a copy of the array.
Key Insights
- Use a two-pointer technique: one pointer to iterate through the array and another pointer to track the position for the next non-zero element.
- For each non-zero element encountered, swap it with the element at the tracking pointer.
- This strategy minimizes operations by ensuring each non-zero element is moved at most once.
- After repositioning all non-zero elements, zeros will naturally occupy the remaining positions.
- The in-place requirement ensures space complexity remains O(1).
Space and Time Complexity
Time Complexity: O(n), where n is the number of elements in the array, since only one pass (or at most two simple passes) is required.
Space Complexity: O(1) extra space, as the reordering is accomplished in-place.
Solution
The solution leverages a two-pointer approach. The left pointer (j) keeps track of the index where the next non-zero element should be placed, while the right pointer (i) iterates through the array. Whenever a non-zero element is encountered, it is swapped with the element at index j, and j is then incremented. This effectively gathers all non-zero elements at the beginning while moving zeros to the end. A key optimization is to perform the swap only when necessary (i.e., when i and j are not the same) to reduce the number of write operations.