Problem Description
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array.
Key Insights
- We need to maintain the order of non-zero elements while moving all zeros to the end.
- An in-place solution is required, meaning we cannot use additional arrays for storage.
- A two-pointer technique can effectively solve this problem by keeping track of the position to place non-zero elements.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
The solution uses a two-pointer approach. One pointer (lastNonZeroFoundAt) keeps track of the index of the last non-zero element found, while the other pointer (current) traverses the entire array. When a non-zero element is found, it is swapped with the element at the lastNonZeroFoundAt index, and the lastNonZeroFoundAt index is incremented. This ensures that all non-zero elements are moved to the front of the array, and all zeros are pushed to the end.