Coding Interview PatternsMove Zeroes
EasyTwo Pointers
Move Zeroes
Explanation & Solution
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.
You must do this in-place without making a copy of the array.
Input:nums = [0,1,0,3,12]
0
0
1
1
2
0
3
3
4
12
Output:[1,3,12,0,0]
0
1
1
3
2
12
3
0
4
0
Explanation: All zeroes are moved to the end while 1, 3, and 12 maintain their original relative order.
Constraints
1 <= nums.length <= 10⁴-2³¹ <= nums[i] <= 2³¹ - 1
Approach
Two Pointers pattern
1. Initialize a Write Pointer
- Create a variable
insertPos = 0 - This tracks the next position where a non-zero element should be placed
2. Iterate Through the Array
- Loop through every element with index
i - Check if
nums[i] !== 0
3. Place Non-Zero Elements
- When a non-zero element is found:
- Copy it to
nums[insertPos] - Increment
insertPos - This shifts all non-zero values to the front in their original order
4. Fill Remaining Positions with Zeroes
- After the first pass,
insertPosmarks where non-zero values end - Fill every position from
insertPosto the end of the array with0
5. Return the Modified Array
- The array is now modified in-place
- All non-zero elements are at the front in their original order
- All zeroes are at the end
Key Insight
The two-pointer technique uses one pointer (i) to scan through the array and another (insertPos) to track where the next non-zero element should go. Since insertPos only advances when a non-zero element is found, it always stays behind or equal to i, guaranteeing an in-place solution with O(n) time and O(1) space.
Visualization
Input:
[0, 1, 0, 3, 12]
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
9 steps