DSA sheet · Arrays · Two Pointers pattern

Move Zeroes

The fourth two-pointer problem, and the first where the two pointers move in the same direction instead of from opposite ends. The teacher starts by showing why sorting can't work (it breaks the order of the non-zero numbers). Then she gives a simple brute force with an extra array (O(n) time, but O(n) extra space), and finally the in-place two-pointer solution: a right pointer that reads every element and a left pointer that marks where the next non-zero number should go.

Why it matters: "one pointer reads, the other writes" is how you filter or compact an array in place. The same idea solves Remove Element, Remove Duplicates from Sorted Array, and the partition step of quicksort.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Two pointers from scratch (pairs, opposite ends, same direction)
• Part A · Brute force: collect the non-zeros in a new array
• Part B · Optimal: read pointer + write pointer, swap in place
• Part C · Revision page

Part 0 · Before starting

What is a "pointer"?

A pointer here is a variable holding an index of the array. "Moving" it means adding 1 (or subtracting 1). Two-pointer solutions keep two such indexes and move them by simple rules, so one pass over the array is enough.

The brute force over all pairs, and why some shape lets us skip work

Many array questions could be solved by trying every pair of positions (two nested loops, about n²/2 pairs, so O(n²)). Two pointers avoids that by using something we know about the array. In Two Sum II and 3Sum, that "something" was sorting: it told us which pointer to move. In Move Zeroes we don't need sorting at all. The useful fact is simpler: we only ever need to move each non-zero once, to the next free spot on the left. So one pointer can remember that spot while the other one scans.

Shape 1: opposite-end pointers (Problems 1–2)

left starts at index 0, right at n − 1, and they walk toward each other. On a sorted array, moving left raises the value and moving right lowers it, so each move discards pairs that can't be the answer. Used for "find a pair with a sum".

Shape 2: same-direction pointers (this problem)

Both pointers start at index 0 and only move forward.

• The fast / read pointer (here right) visits every element, one by one.
• The slow / write pointer (here left) moves only when we keep something. It marks the place where the next kept element must be written.

Everything before the slow pointer is the "finished" part. Because elements are written there in the order the fast pointer meets them, their relative order never changes.

The other shapes on this sheet

The teacher's 4 array patterns

Her reasoning: the last three are all about continuous pieces of the array. Here we just want to grab a zero and a non-zero and swap them, which needs two pointers at two different places.

Part A · Brute force: collect the non-zeros in a new array

LeetCode 283

1The question in simple words

You get an integer array nums. Move all the 0s to the end, while keeping the non-zero numbers in their original relative order ("relative order" = who comes before whom). Do it in place: change nums itself, don't return a new array (the function returns nothing).

Why sorting doesn't work

The teacher kills this idea first. Sorting ascending puts the zeros at the front (and negatives before them). To get zeros at the end you might try sorting descending, which gives [12, 3, 1, 0, 0]. The zeros are at the end, but 1, 3, 12 has become 12, 3, 1. The question forbids changing the order, so no sorting. We have to pick each element up and put it in the right place ourselves.

2What the constraints tell us

• 1 ≤ n ≤ 10⁴. At least one element. The teacher notes that even an O(n²) idea would pass at this size (10⁸ is about the limit).
• −2³¹ ≤ nums[i] ≤ 2³¹ − 1. Any 32-bit int, including negatives. Negatives are just "non-zero" here. We never add numbers, so there's no overflow to think about.
• Follow-up: "Could you minimize the total number of operations done?" This is the question telling us it wants something better than the basic approach, so after the brute force we'll optimise.

3Intuition: copy out the non-zeros, then fill with zeros

Walk through the array once. Every time you see a non-zero, append it to a new list. Because you visit them left to right, they land in the new list in the same order. Whatever is left over must be zeros, so pad the end with that many zeros.

4Building the logic from the example

[0, 1, 0, 3, 12]. Ask each element "are you non-zero?":

• 0 → no, skip.
• 1 → yes → new list [1].
• 0 → no.
• 3 → yes → [1, 3].
• 12 → yes → [1, 3, 12].

How many zeros to add?

We don't even need to count the zeros separately. The total length is 5 and we kept 3 non-zeros, so the number of zeros is 5 − 3 = 2. Append two zeros → [1, 3, 12, 0, 0].

5Approach steps

1. Make an empty list result.
2. For each number in nums: if it's not 0, append it.
3. Append len(nums) − len(result) zeros.
4. Copy result back into nums: nums[:] = result.

6Code (Python)

class Solution:
    def moveZeroes(self, nums):
        result = []
        for x in nums:
            if x != 0:                          # keep non-zeros, in order
                result.append(x)
        zeros = len(nums) - len(result)         # whatever is missing were zeros
        result.extend([0] * zeros)
        nums[:] = result                        # write back into the SAME list

7Code line by line

8Dry run (hand table)

9Complexity & remember

• Time O(n): one pass to collect, one to pad, one to copy back.
• Space O(n): the extra result list. The teacher's question: what if we're asked to save space too? That leads to Part B.

Part B · Optimal: read pointer + write pointer, swap in place

LeetCode 283

1The question again, with the new goal

Same question. Now: one pass, no extra array (O(1) extra space).

2What the constraints tell us now

• n ≤ 10⁴ → O(n) is trivially fast. The goal here is space and fewer operations, not speed.
• n ≥ 1 → no empty-array case, but the code below handles it anyway (the loop just doesn't run).

3Intuition: left keeps a seat for the next non-zero

Two pointers, both starting at index 0:

• right walks over every element and asks: "are you zero or non-zero?"
• left is the seat where the next non-zero should sit.

When right finds a zero, it does nothing and moves on. When it finds a non-zero, that number swaps into left's seat, and left moves to the next seat. Zeros get pushed backward one swap at a time.

4Building the logic from the example

[0, 1, 0, 3, 12], left = 0, right = 0.

right on a zero → just move on

right = 0 sees 0. A zero is already "in the wrong half", but there's nothing to put in its place yet. No swap. Only right moves. left stays at 0, still keeping that seat free.

right on a non-zero → swap into left's seat, then move left

right = 1 sees 1. Swap nums[1] with nums[left] = nums[0] → [1, 0, 0, 3, 12]. Now seat 0 is taken, so left moves to 1.

right = 2 sees 0 → skip. right = 3 sees 3 → swap with nums[1] → [1, 3, 0, 0, 12], left = 2. right = 4 sees 12 → swap with nums[2] → [1, 3, 12, 0, 0], left = 3. right runs off the end, the loop stops. Done.

Writing the swap: why not just put 0 at nums[right]?

The swap uses a temporary variable:

1. temp = nums[right] (save the non-zero, we don't know its value in advance)
2. nums[right] = nums[left]
3. nums[left] = temp

Usually nums[left] is 0, so step 2 writes a 0. Why not write 0 directly? Because left and right can be the same index. Then the swap is "swap with itself", and writing 0 would erase a non-zero.

The loop: right moves by itself

right moves on every step, zero or not, so a for right in range(n) loop handles it. left moves only on a swap, so it lives outside the loop (left = 0) and we do left += 1 by hand.

The question says "do not return anything", so the function just ends after the loop.

5Approach steps

1. left = 0.
2. For right from 0 to n − 1:
3. If nums[right] != 0: swap nums[left] and nums[right], then left += 1.
4. (If it's 0: do nothing, the loop moves right.)

6Code (Python)

class Solution:
    def moveZeroes(self, nums):
        n = len(nums)
        left = 0                            # seat for the next non-zero
        for right in range(n):              # right reads every element
            if nums[right] != 0:            # a non-zero: seat it
                temp = nums[right]
                nums[right] = nums[left]    # NOT "= 0": left may equal right
                nums[left] = temp
                left += 1                   # that seat is taken, move on
        # nothing to return: nums was changed in place

The Pythonic swap nums[left], nums[right] = nums[right], nums[left] does the same three steps in one line.

7Code line by line

8Dry run

nums = [0, 1, 0, 3, 12].

The array at key moments (yellow = the pointer cells, grey = seats already filled with their final non-zero):

A case with self-swaps: [4, 5, 0, 6]. right = 0 and 1 swap with themselves (left == right), left becomes 2. right = 2 is 0 → skip. right = 3 swaps 6 into seat 2 → [4, 5, 6, 0] ✓.

9Complexity & remember

• Time O(n). The teacher's reasoning: right goes from 0 to n − 1, once. left never makes extra trips: it only moves at the same moment right moves (on a non-zero). Each swap is O(1). So the total work is the number of right moves = n. One single pass.
• Space O(1): just left, right and temp.

She submitted it and it passed (Java on screen, then the same logic in Python and C++).

Part C · Revision page

s = Solution()
for nums in ([0, 1, 0, 3, 12], [0], [4, 5, 0, 6], [0, 0, 1], [1, 2, 3], [-1, 0, -2]):
    s.moveZeroes(nums)
    print(nums)
# [1, 3, 12, 0, 0]
# [0]
# [4, 5, 6, 0]
# [1, 0, 0]
# [1, 2, 3]
# [-1, -2, 0]

Based on this video: Move Zeroes | Two Pointers