Shift Zeros to the End
Given an integer array nums, move all 0s to the end of the array
while maintaining the relative order of the non-zero elements. You
must do this in place without making a copy of the array, and you
should minimize the total number of write operations.
Example 1
Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Example 2
Input: nums = [0, 0, 1]
Output: [1, 0, 0]
Constraints
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 1
Use a slow "write" pointer and a fast "read" pointer, both starting at index 0. The read pointer scans every element; whenever it finds a non-zero value, that value is placed at the write pointer's position (swapping it with whatever is currently there), and the write pointer advances. By the time the read pointer reaches the end, every non-zero value has been moved to the front in its original relative order, and every zero has naturally been pushed toward the back via the swaps.
A naive approach might build a new array of non-zero values followed by zeros, which uses O(n) extra space; the two-pointer swap technique does the same job in place with O(1) extra space and at most n swaps.
def shift_zeros_to_the_end(nums: list[int]) -> None:
write = 0
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1
# nums is modified in place; nothing to return
Complexity: O(n) time, since the read pointer visits each element once. O(1) extra space, since the array is rearranged in place.
Share this question