Given an integer array nums, move every 0 to the end while keeping the relative order of the non-zero elements. Do it in place, without making a copy of the array. The function returns nothing.
- 1 <= nums.length <= 10^4
- -2^31 <= nums[i] <= 2^31 - 1
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The simple approach builds a second array of the non-zero values and then pads it with zeros, which costs O(n) extra space. Instead, treat the front of the same array as that output: a write pointer marks where the next non-zero value should go. Swapping each non-zero value into the write position pushes zeros backwards naturally, and order is preserved because we place values in the order we meet them.
Algorithm
- Set the write pointer
w = 0. - Scan
rfrom 0 to n-1. - If
nums[r] != 0, swapnums[w]andnums[r], thenw++. - When the scan ends, all zeros sit after index
w - 1.
O(n)Space: O(1)w == r.class Solution: def moveZeroes(self, nums: List[int]) -> None: w = 0 # next slot for a non-zero value for r in range(len(nums)): if nums[r] != 0: nums[w], nums[r] = nums[r], nums[w] w += 1