LeetCode: 283. Move Zeroes

LeetCode: 283. Move Zeroes

Summary

Given an integer array nums, move all 0s to the end while keeping the relative order of non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Approach

Two-pointer approach.

• Pointer i scans each element from left to right.
• Pointer zero_idx stores the leftmost index where a 0 should be replaced by the next non-zero value.

Function

Initialization:

• zero_idx = -1

For each number n at index i in nums:

• If n == 0 and zero_idx < 0, set zero_idx = i (initialize zero pointer).
• Else, if n != 0 and zero_idx >= 0:
  • Swap nums[zero_idx] and nums[i].
  • Increment zero_idx by 1.

Example:

Input: nums = [0,1,0,3,12]

1. n = 0 at i = 0 -> zero_idx = 0
2. n = 1 at i = 1 -> swap nums[0] and nums[1] -> [1,0,0,3,12], zero_idx = 1
3. n = 0 at i = 2 -> skip
4. n = 3 at i = 3 -> swap nums[1] and nums[3] -> [1,3,0,0,12], zero_idx = 2
5. n = 12 at i = 4 -> swap nums[2] and nums[4] -> [1,3,12,0,0]

Return nums.

Complexity

Time complexity: O(N), where N is the size of nums.
Space complexity: O(1) since the operation is in-place.