Algorithm-Day04-Move-Zeroes-lc#283

Posted on In , Views:

🧩 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.

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]

💡 Naive Idea (Two-Pass Write)

  • Create a new array and copy all non-zero values into it, then append zeroes.
  • ✅ Correct but ❌ not in-place. So it’s invalid.

💡 Optimal In-Place Approach (Two Pointers)

We use the two-pointer technique:

  • Use a nonZeroIndex to track the next position to place a non-zero.
  • Traverse the array:
    • If current element is not 0, write it to nonZeroIndex, then increment nonZeroIndex.
  • Finally, fill the remaining elements from nonZeroIndex to end with 0.

This is done in-place and only requires one pass + cleanup.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0;

        // First pass: move all non-zero elements forward
        for (int num : nums) {
            if (num != 0) {
                nums[nonZeroIndex++] = num;
            }
        }

        // Second pass: fill the rest with zeros
        while (nonZeroIndex < nums.length) {
            nums[nonZeroIndex++] = 0;
        }
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) – single pass for placement + fill
  • Space Complexity: O(1) – in-place manipulation

✍️ Summary

  • The key is to use two pointers to separate writing and reading.
  • Remember: “In-place” means no extra array.
  • Common interview problem — focus on efficiency and clarity.

This pattern of tracking write position separately is widely used in array transformations.