DSA sheet · Arrays · Two Pointers pattern

Sort Colors (Dutch National Flag)

This is the third two-pointer question in the sheet. The array holds only three kinds of values, 0, 1 and 2, and we must sort it without the built-in sort. The teacher first solves it the easy way: count how many 0s, 1s and 2s there are, then write them back. That takes two passes. Then she answers the follow-up ("one pass, constant extra space") with the Dutch National Flag algorithm, which uses three pointers: low, mid and high.

Why it matters: the Dutch National Flag idea is "split the array into regions and keep each region's promise at every step". The same thinking appears in quicksort's three-way partition and in many "group these values in place" questions.

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 · What you must know before starting (two pointers from scratch)
• Part A · Counting: two passes
• Part B · Dutch National Flag: one pass with low, mid, high
• Part C · Revision page

Part 0 · Before starting

What is a pointer here?

In array questions, a pointer is just a variable that holds an index (a position) in the array. It isn't a memory address like in C. If low = 2, then "low points to index 2", and nums[low] is the value sitting there.

The brute force over all pairs, and why we can often skip pairs

Many array questions look at pairs of positions (i, j). Two nested loops can try every pair: about n·(n−1)/2 of them, which is O(n²). The two-pointer idea is that the shape of the array (it's sorted, or the values are limited, or we only care about the ends) lets us throw away many pairs without checking them. Then each pointer moves only forward (or only backward), and the total work is O(n).

The kinds of two-pointer movement

Why two pointers here and not the other array patterns?

The teacher's sheet has four array patterns: two pointers, sliding window, prefix sum and Kadane's algorithm. The last three are all about a contiguous subarray (a piece of the array with no gaps): its sum, its product, its best value. Sort Colors has no window or subarray at all. We only look at particular positions and swap values between them. So she picks two pointers straight away.

What does "in place" mean?

In place means we change the given list itself. We don't build a new list and return it. LeetCode's sortColors returns nothing (None); it checks the same list afterwards. Swapping two positions, nums[a], nums[b] = nums[b], nums[a], is the main in-place tool.

Part A · Counting: two passes

LeetCode 75

1The question in simple words

You get a list nums of n objects. Each one is coloured red, white or blue, written as numbers: 0 = red, 1 = white, 2 = blue. Rearrange the list in place so that all 0s come first, then all 1s, then all 2s. You are not allowed to call the library sort.

The teacher's example has nine values, three of each colour:

(The video's dry run starts from this list. LeetCode's own example is [2,0,2,1,1,0] → [0,0,1,1,2,2].)

2What the constraints tell us

• 1 ≤ n ≤ 300. Tiny. The built-in sort (O(n log n)) would easily pass, which is exactly why the question bans it. The point is to use the special fact that there are only three values.
• nums[i] is 0, 1 or 2. Only three possible values. This is the key: we never need to compare two numbers in general, we only need to know which of three groups each one belongs to.
• n ≥ 1, so the list is never empty. (Our code still works on an empty list.)
• Follow-up: can you do it in one pass with constant extra space? Part A is two passes; Part B answers the follow-up.

3Intuition: count, then repaint

How would you sort this by hand? You'd count: "three 0s, three 1s, three 2s". Then you'd write three 0s, then three 1s, then three 2s over the old list. The order of the original values doesn't matter at all, because every 0 looks the same as every other 0.

So the plan is two passes: pass 1 counts, pass 2 overwrites.

4Building the logic from the example

Pass 1: three counters

Keep count0, count1, count2, all starting at 0. Walk through the list once. If the value is 0, add one to count0; if it's 1, add one to count1; otherwise (it must be 2) add one to count2. For the example we get 3, 3, 3.

Pass 2: one write pointer, three while loops

Now keep a pointer i that starts at index 0. It marks the next position to overwrite, and it travels through the whole list across all three loops.

• While count0 is still above 0: write 0 at nums[i], move i forward, take one off count0. In the example this fills indexes 0, 1, 2 and count0 goes 3 → 2 → 1 → 0.
• When count0 hits 0, all the zeros are placed. i stays where it is (index 3) and the next loop does the same with 1s for count1 rounds, filling 3, 4, 5.
• The third loop writes 2s for count2 rounds, filling 6, 7, 8.

5Approach steps

1. Count the 0s, 1s and 2s in one loop.
2. Set i = 0.
3. Write count0 zeros starting at i, moving i each time.
4. Write count1 ones from where i is now.
5. Write count2 twos from where i is now.

6Code (Python)

class Solution:
    def sortColors(self, nums):
        count0 = count1 = count2 = 0
        for x in nums:                 # pass 1: count each colour
            if x == 0:
                count0 += 1
            elif x == 1:
                count1 += 1
            else:
                count2 += 1

        i = 0                          # next position to overwrite
        while count0 > 0:              # pass 2: write the 0s
            nums[i] = 0
            i += 1
            count0 -= 1
        while count1 > 0:              # then the 1s
            nums[i] = 1
            i += 1
            count1 -= 1
        while count2 > 0:              # then the 2s
            nums[i] = 2
            i += 1
            count2 -= 1

7Code line by line

8Dry run (hand table)

nums = [1, 1, 0, 2, 0, 1, 2, 0, 2]. After pass 1: count0 = 3, count1 = 3, count2 = 3.

9Complexity & remember

• Time O(n): pass 1 is n steps. In pass 2, the three while loops together run count0 + count1 + count2 = n times (3 + 3 + 3 = 9 in the example). Total about 2n, which is still O(n). But it is two passes over the list, and the follow-up asks for one.
• Space O(1): three counters and one index.

Part B · Dutch National Flag: one pass with low, mid, high

LeetCode 75 · follow-up

1The question again, with the new goal

Same question, but now: one pass over the list and constant extra space. No counting first. Each value must be put in the right place as we meet it.

The name comes from the Dutch flag, which has three horizontal stripes. We're building three "stripes": 0s, 1s, 2s.

2What the constraints tell us

• Only three values → every value goes to one of three groups: the left group (0), the middle group (1) or the right group (2).
• Constant space → we can't use a second list. We must swap values inside nums.
• n ≤ 300 → speed isn't the issue; the challenge is doing it in one pass.

3Intuition: three pointers hold a meeting

The teacher tells it as a story. Three pointers, low, mid and high, sit in a meeting and divide the work. low and mid start at index 0; high starts at the last index, n − 1. Each one makes a promise:

  index:   0 .. low-1 | low .. mid-1 | mid .. high | high+1 .. n-1
  holds:     0 0 0    |    1 1 1     |  ? ? ? ?    |    2 2 2
             zeros    |    ones      |  UNKNOWN    |    twos

At the start, low = mid = 0 and high = n − 1, so the zeros, ones and twos regions are all empty and the whole list is "unknown". That's true, so every promise holds from the beginning.

mid is the one doing the work. It looks at the first unknown value and asks "what are you?"

• 0 → hand it to low (it belongs in the left stripe).
• 1 → keep it; it's already in the right place (just after the 1s).
• 2 → hand it to high (it belongs in the right stripe).

Each step shrinks the unknown region by one. When the unknown region is empty, the list is sorted.

4Building the logic from the example

Where do the pointers end up when it's sorted?

The teacher first draws the finished list [0,0,0,1,1,1,2,2,2] and asks where each pointer must be for its promise to be true. "0..low−1 is all zeros" → low points at index 3 (the first 1). "low..mid−1 is all ones" → mid points just past the last 1, index 6. "high+1..n−1 is all twos" → high points at index 5, just before the first 2. So at the end, mid = high + 1: mid has walked from the left, high has walked from the right, and they have crossed.

The loop condition: while mid <= high

The unknown region is mid … high. It still has a value in it as long as mid ≤ high. When mid = high there's one unknown value left, and it must still be checked. So the loop runs while mid <= high and stops the moment mid passes high.

Case 1: nums[mid] is 1 → just move mid

In the example, mid starts at index 0 and sees a 1. A 1 belongs in the middle stripe, which ends at mid − 1. If mid moves forward by one, this 1 becomes the last cell of the middle stripe. No swap needed: mid += 1. Index 1 is also 1, so mid moves again.

Case 2: nums[mid] is 0 → swap with low, move both

Now mid is at index 2 and sees a 0. It belongs at the end of the left stripe, which is exactly index low. So swap nums[low] and nums[mid]: [1,1,0,…] becomes [0,1,1,…].

Now the 0 is at index low, so the zeros region has grown by one: low += 1 keeps "0..low−1 are zeros" true. The value that came to mid is a 1 (it used to sit at the start of the 1s), so the ones region also grows: mid += 1. Both move.

Case 3: nums[mid] is 2 → swap with high, move only high

mid is at index 3 and sees a 2. It belongs in the right stripe, whose last free spot is index high. Swap nums[mid] and nums[high], then high -= 1 so that "high+1..n−1 are twos" stays true.

But mid does NOT move. Look at what happens in the example: index 8 (high) held a 2. After the swap, mid still sees a 2! It has to send that one right as well: swap with the new high (index 7), which holds a 0. Now mid sees a 0, which must still go to the left. If mid had moved forward after the first swap, that 2, and then that 0, would have been left in the wrong place.

The last value: mid and high on the same index

Near the end of the example, mid and high meet at index 6, which holds a 2. Swapping it with itself changes nothing, then high -= 1 makes high = 5 < mid = 6. They have crossed, the loop stops, and the list is sorted.

5Approach steps

1. low = 0, mid = 0, high = n − 1.
2. While mid <= high (the unknown region isn't empty):
3. If nums[mid] is 0: swap nums[low] and nums[mid], then low += 1 and mid += 1.
4. If nums[mid] is 1: mid += 1.
5. If nums[mid] is 2: swap nums[mid] and nums[high], then high -= 1 only. Don't move mid.

6Code (Python)

class Solution:
    def sortColors(self, nums):
        low, mid, high = 0, 0, len(nums) - 1
        while mid <= high:                     # unknown region mid..high not empty
            if nums[mid] == 0:                 # belongs in the left stripe
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:               # already in the middle stripe
                mid += 1
            else:                              # a 2: belongs in the right stripe
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1                      # mid stays: the new value is unchecked

The teacher writes the swaps as "put nums[low] at mid, then put a 0 at low" (and "put nums[high] at mid, then a 2 at high"), since we already know the value at mid. A plain Python swap does the same thing.

7Code line by line

8Dry run

nums = [1, 1, 0, 2, 0, 1, 2, 0, 2], n = 9. Start: low = 0, mid = 0, high = 8.

The list at three key moments. Yellow = where the pointers are, grey = a finished stripe.

Check the promises after step 6 (now low = 2, mid = 4, high = 6): indexes 0..1 = [0, 0] zeros ✓, 2..3 = [1, 1] ones ✓, 4..6 still unknown, 7..8 = [2, 2] twos ✓. Every step keeps all four regions honest.

9Complexity & remember

• Time O(n), one pass. Each loop round does O(1) work (one comparison, maybe one swap) and shrinks the unknown region by exactly one: either mid moves right or high moves left. The teacher puts it as: if mid travels x steps, high travels the other n − x, so the loop runs x + (n − x) = n times in total.
• Space O(1): three index variables.

Part C · Revision page

s = Solution()
for nums in ([1, 1, 0, 2, 0, 1, 2, 0, 2], [2, 0, 2, 1, 1, 0], [2, 0, 1], [1, 0], [0], [2, 2, 2]):
    s.sortColors(nums)          # changes nums in place, returns None
    print(nums)
# [0, 0, 0, 1, 1, 1, 2, 2, 2]
# [0, 0, 1, 1, 2, 2]
# [0, 1, 2]
# [0, 1]
# [0]
# [2, 2, 2]

Based on this video: Sort Colors | Dutch National Flag Algorithm