Master Move Zeroes (LeetCode 283) in a Single Pass: In-Place Two-Pointer Trick | Day 3 of 180

Plaintext

================================================================================
BLOG ARTICLE CONTENT (Markdown / HTML)
================================================================================

# 180-Day DSA Roadmap | Day 3: Move Zeroes (LeetCode #283)

* **Topic:** Arrays & Strings  
* **Pattern:** Two Pointers (Reader & Writer / Same-Direction Scan)  
* **Difficulty:** Easy / Core Foundation  
* **LeetCode Problem:** LeetCode #283 - Move Zeroes  
* **Target Companies:** Microsoft, Amazon, Apple, Meta, Google, Adobe  

---

## 1. Problem Statement

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

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

### Constraints
* 1 <= nums.length <= 10^4
* -2^31 <= nums[i] <= 2^31 - 1
* Follow up: Could you minimize the total number of operations done?

### Example Walkthrough
```text
Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Explanation:
Non-zero elements are 1, 3, 12. Their relative order is strictly maintained.
All zeros are pushed to the tail end of the array.

2. Pattern Recognition: The Reader-Writer Pattern

In Days 1 and 2, we used opposite-direction two pointers (inward scan). Day 3 introduces the same-direction two-pointer pattern (often called Fast & Slow or Reader & Writer).

Spot this pattern whenever:

1. Filtering / Compacting in Place: You must collect valid elements at the front while pushing unwanted elements to the rear.
2. Order Preservation: The relative order of valid elements cannot be scrambled (which rules out inward swaps from opposite ends).
3. Strict $O(1)$ Space: Creating a secondary buffer or new array is forbidden.

The strategy assigns two distinct roles:

• Writer (writer / slow): Points to the exact index where the next non-zero element should be placed.
• Reader (reader / fast): Scans every index forward to find the next valid non-zero element.

3. Algorithmic Approaches

Approach 1: Extra Array Buffer (Suboptimal)

• Allocate a new array of size $N$. Copy all non-zero numbers first, fill remaining slots with zeros, and copy back.
• Time Complexity: $O(N)$
• Space Complexity: $O(N)$
• Verdict: Fails the in-place constraint.

Approach 2: Two-Pass Overwrite + Fill Zeroes (Acceptable)

• First pass: Copy all non-zero numbers forward into nums[writer++].
• Second pass: Fill all positions from writer up to n - 1 with 0.
• Time Complexity: $O(N)$
• Space Complexity: $O(1)$
• Verdict: Valid and runs in $O(N)$, but writes multiple times to memory (suboptimal for the follow-up question).

Approach 3: Optimal Single-Pass Swap (MNC Interview Standard)

• Both pointers start at index 0.
• Iterate reader across the array:
  • If nums[reader] != 0:
    • If reader != writer, swap nums[writer] with nums[reader].
    • Increment writer++.
• Why this works: Every non-zero found is swapped into the earliest available slot (writer). Because any elements between writer and reader are guaranteed to be zeros, swapping automatically drags zeros forward without needing a second zero-filling loop!

Plaintext

Visual Execution Trace:
Initial: nums = [0, 1, 0, 3, 12] | writer = 0

Step 1 (reader = 0): nums[0] == 0
  Do nothing. reader advances.
  [ 0 , 1 , 0 , 3 , 12 ]
    ▲   ▲
    w   r

Step 2 (reader = 1): nums[1] == 1 (Non-zero found!)
  Swap nums[writer] and nums[reader] ──► Swap nums[0] & nums[1]
  writer++ ──► writer becomes 1
  [ 1 , 0 , 0 , 3 , 12 ]
        ▲   ▲
        w   r

Step 3 (reader = 2): nums[2] == 0
  Do nothing. reader advances.
  [ 1 , 0 , 0 , 3 , 12 ]
        ▲       ▲
        w       r

Step 4 (reader = 3): nums[3] == 3 (Non-zero found!)
  Swap nums[writer] and nums[reader] ──► Swap nums[1] & nums[3]
  writer++ ──► writer becomes 2
  [ 1 , 3 , 0 , 0 , 12 ]
            ▲       ▲
            w       r

Step 5 (reader = 4): nums[4] == 12 (Non-zero found!)
  Swap nums[writer] and nums[reader] ──► Swap nums[2] & nums[4]
  writer++ ──► writer becomes 3
  [ 1 , 3 , 12 , 0 , 0 ]  <── COMPLETE!

4. Production-Ready Code Implementations

Java Solution

Java

class Solution {
    public void moveZeroes(int[] nums) {
        int writer = 0;

        for (int reader = 0; reader < nums.length; reader++) {
            if (nums[reader] != 0) {
                // Optimize: avoid self-swaps when no zeros have been encountered yet
                if (reader != writer) {
                    int temp = nums[writer];
                    nums[writer] = nums[reader];
                    nums[reader] = temp;
                }
                writer++;
            }
        }
    }
}

Python 3 Solution

Python

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        writer = 0

        for reader in range(len(nums)):
            if nums[reader] != 0:
                if reader != writer:
                    nums[writer], nums[reader] = nums[reader], nums[writer]
                writer += 1

C++ Solution

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    void moveZeroes(std::vector<int>& nums) {
        int writer = 0;

        for (int reader = 0; reader < nums.size(); ++reader) {
            if (nums[reader] != 0) {
                if (reader != writer) {
                    std::swap(nums[writer], nums[reader]);
                }
                writer++;
            }
        }
    }
};

5. Complexity Analysis

• Time Complexity: $O(N)$
  The reader pointer traverses each array element exactly once. Inside the loop, all operations (comparisons, index increments, and swaps) take $O(1)$ constant time.
• Space Complexity: $O(1)$
  Operates strictly in-place by swapping values within the existing array buffer. No auxiliary data structures are instantiated.

6. Key Takeaways & Interview Follow-Up

• Minimizing Operations: If an array has no zeros (e.g., [1, 2, 3, 4]), checking if (reader != writer) skips redundant self-assignment swaps, keeping total write operations strictly bounded to the count of out-of-place elements.
• Invariant Maintenance: At any moment during the scan:
  • Elements in nums[0 ... writer - 1] are non-zero elements in correct relative order.
  • Elements in nums[writer ... reader - 1] are guaranteed to be zeros.

Master Move Zeroes (LeetCode 283) in a Single Pass: In-Place Two-Pointer Trick | Day 3 of 180

Learn how to solve LeetCode 283 (Move Zeroes) in a single pass with O(1) space. Master the Reader-Writer two-pointer pattern with clean code in Java, Python, and C++.


Move Zeroes LeetCode 283, Reader Writer Two Pointer Pattern, Move Zeroes In Place O1 Space, LeetCode 283 Solution Java Python Cpp


leetcode 283, move zeroes, reader writer pattern, two pointers same direction, dsa roadmap, dsa interview questions, coding interview preparation, data structures and algorithms, leetcode solutions, two pointers pattern, leetcode easy, faang interview preparation, mnc coding questions, amazon coding interview, google coding interview, microsoft interview questions, meta coding interview, adobe coding questions, apple interview questions, leetcode 283 java, leetcode 283 python, leetcode 283 cpp, java dsa, python dsa, cpp dsa, time complexity o n, space complexity o 1, array interview questions, inplace algorithms, array partition, array compaction, top dsa patterns, software engineer jobs, campus placement preparation, competitive programming, vs coding academy, 180 days dsa, dsa cheat sheet, cracking the coding interview, tech interview prep, leetcode patterns, software development engineer, sde 1 preparation, array algorithms, single pass algorithm, coding questions for freshers, dsa placement series, engineering placements, leetcode practice, data structures roadmap

Follow our YouTube Channels:
Trendy VS Vlogs: https://youtube.com/@trendyvsvlogs?si=Xd3L31p5zPXggomY
WhatsApp Channel: https://whatsapp.com/channel/0029Vb9H4vC545v2HaoKk735