MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns  Module 4 – Two pointers

Dutch national flag: three-way partitioning

Group a list into values below, equal to and above a pivot in one pass with O(1) memory: the problem, its examples and what the obvious answers cost.

  • Intermediate
  • 20 minutes
  • Examples run with Python 3.14.8 and Pyodide 314.0.7
  • By MySmartCoPilot
Free: The problem: three groups around a pivot, in one pass · Sorting or two passes: correct, but more work than one pass. With a pass: the other 9 sections and 3 interview answers, about 16 minutes.

What you will learn

  • Partition an array into three groups in one pass with three pointers
  • Prove that each swap keeps the four regions of the invariant intact
  • Explain every pointer move of the one-pass partition from its invariant
  • Use the three-way partition inside quicksort and quickselect
  • Measure how equal keys slow down a two-way quicksort

Before you start

What you’ll learn · Before you start

What you will learn

  • Partition an array into three groups in one pass with three pointers
  • Prove that each swap keeps the four regions of the invariant intact
  • Explain every pointer move of the one-pass partition from its invariant
  • Use the three-way partition inside quicksort and quickselect
  • Measure how equal keys slow down a two-way quicksort

Before you start

On this page

The Dutch national flag problem asks you to rearrange a list into three groups, the values below a pivot: The value a partition compares every item with: items below it go to one side and items above it to the other. Quicksort takes its pivot from the part of the list it is partitioning., the values equal to it and the values above it, in one pass with O(1) extra memory: for 1,000,000 parcel levels, one look at each. Dijkstra used it as an exercise in deriving and proving programs, with items in the three colours of the Dutch flag.

The standard answer keeps three indices and moves each value into its group with at most one swap, so the pass takes n steps. The same step, a three-way partition: Rearranging a list around a pivot value into three groups: the values below it, the values equal to it and the values above it, with the order inside each group left free., keeps quicksort fast when many keys are equal.

The problem: three groups around a pivot, in one pass

The problem

A sorting hub scans parcels into a list, and levels holds each parcel’s priority level as an integer. Given a level p, rearrange levels in place so that every level below p comes first, then every level equal to p, then every level above it, and return the pair (i, j) with levels[:i] below p, levels[i:j] equal to it and levels[j:] above it. The order inside a group does not matter. Use one pass and O(1) extra memory. Limits: 1 ≤ n ≤ 1,000,000, and the levels and p are 32-bit integers.

  1. levels = [2, 0, 2, 1, 1, 0] with p = 1 becomes [0, 0, 1, 1, 2, 2] and gives (2, 4).
  2. levels = [5, 9, 5, 1, 7] with p = 5 gives (1, 3): 1 first, the two 5s next, then 9 and 7 in either order.
  3. levels = [6, 8, 7] with p = 4 gives (0, 0): the pivot need not be in the list, and here every level is above it.

The first example, before and after:

The levels 2, 0, 2, 1, 1, 0 with p = 1, and after the call 0, 0 below p, 1, 1 equal to p and 2, 2 above p, split at i = 2 and j = 4.levels = [2, 0, 2, 1, 1, 0], p = 1Before the call202110After: three groups, returns (2, 4)001122i = 2j = 4below pequalabove p[:i] below p, [i:j] equal to p, [j:] above p

What the call must do to the first example, with p = 1

Text description of the diagram

The figure has two rows of six slots.

  1. Before the call, the levels are 2, 0, 2, 1, 1 and 0, and the pivot p is 1.
  2. After the call, the same levels form three groups: 0 and 0 below p in slots 0 and 1, 1 and 1 equal to p in slots 2 and 3, and 2 and 2 above p in slots 4 and 5. A line before slot 2 marks i = 2 and a line before slot 4 marks j = 4, so the call returns (2, 4): levels[:i] is below p, levels[i:j] is equal to p and levels[j:] is above p.

Checkpoint

Check: Three groups around a pivot, in one pass

  1. One question levels = [3, 7, 3, 9, 1, 3] with p = 3. What pair (i, j) does the call return?

    Choose one answer.

    Show the answer

    Answer: (1, 4)

    levels[:i] holds the values below p, here just the 1, so i = 1. The three 3s follow, so j = 1 + 3 = 4, and the 7 and the 9 fill levels[4:].

Sorting or two passes: correct, but more work than one pass

Two correct answers come first:

  • Sort the list. Sorted values are grouped, so (i, j) follows by counting. But a sort also orders the values inside each group, which nobody asked for, and pays for it with O(n log n) comparisons instead of one look per value.
  • Two reader–writer passes. First swap every level below p to the front, the way the writer of the previous lesson keeps items, then swap every level equal to p right behind them. That is O(n) time and O(1) memory, but it reads part of the list twice.
Sorting and two passes, with their work counted Python · brute/sort_or_two_passes.py 
"""Two correct answers that do not meet the brief: sorting, and two reader-writer passes.
Each counts its work: comparisons for the sort; items read and swaps for the two passes."""
import functools
import random


def by_sorting(levels, p):
    compares = 0

    def compare(x, y):
        nonlocal compares
        compares += 1
        return (x > y) - (x < y)

    levels.sort(key=functools.cmp_to_key(compare))
    i = sum(1 for v in levels if v < p)
    j = i + sum(1 for v in levels if v == p)
    return (i, j), compares


def by_two_passes(levels, p):
    reads = swaps = 0
    w = 0
    for r in range(len(levels)):  # pass 1: every level below p to the front
        reads += 1
        if levels[r] < p:
            levels[w], levels[r] = levels[r], levels[w]
            swaps += 1
            w += 1
    i = w
    for r in range(i, len(levels)):  # pass 2: every level equal to p right after them
        reads += 1
        if levels[r] == p:
            levels[w], levels[r] = levels[r], levels[w]
            swaps += 1
            w += 1
    return (i, w), reads, swaps


for levels, p in [([2, 0, 2, 1, 1, 0], 1), ([5, 9, 5, 1, 7], 5), ([6, 8, 7], 4)]:
    a, b = list(levels), list(levels)
    (i, j), _ = by_sorting(a, p)
    two, _, _ = by_two_passes(b, p)
    print(f"p = {p}: {levels} -> sorted {a}, ({i}, {j}); two passes {b}, {two}")

rng = random.Random(7)
n = 100_000
levels = [rng.randint(0, 9) for _ in range(n)]
_, compares = by_sorting(list(levels), 5)
_, reads, swaps = by_two_passes(list(levels), 5)
print()
print(f"{n:,} random levels from 0 to 9, p = 5:")
print(f"  sorting:    {compares:,} comparisons")
print(f"  two passes: {reads:,} items read, {swaps:,} swaps")
print(f"  one pass reads each level once: {n:,} items read")

Output

p = 1: [2, 0, 2, 1, 1, 0] -> sorted [0, 0, 1, 1, 2, 2], (2, 4); two passes [0, 0, 1, 1, 2, 2], (2, 4)
p = 5: [5, 9, 5, 1, 7] -> sorted [1, 5, 5, 7, 9], (1, 3); two passes [1, 5, 5, 9, 7], (1, 3)
p = 4: [6, 8, 7] -> sorted [6, 7, 8], (0, 0); two passes [6, 8, 7], (0, 0)

100,000 random levels from 0 to 9, p = 5:
  sorting:    714,264 comparisons
  two passes: 150,034 items read, 60,036 swaps
  one pass reads each level once: 100,000 items read

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 sort_or_two_passes.py

Python Online Compiler Try both answers on levels of your own and compare their counts.

On 100,000 random levels the sort made about seven comparisons per level and the two passes read one and a half levels per level, where a single pass reads each level once. Neither meets the brief, and the gap grows where the step repeats, as in quicksort. Step through the two passes:

Interactive · line by line Two reader–writer passes on the first example Step through both passes with p = 1. The first moves every level below p to the front; watch where the second pass starts reading.

Program · trace/two_passes_steps.py

levels = [2, 0, 2, 1, 1, 0]
p = 1
w = 0
for r in range(len(levels)):
    if levels[r] < p:
        levels[w], levels[r] = levels[r], levels[w]
        w += 1
i = w
for r in range(i, len(levels)):
    if levels[r] == p:
        levels[w], levels[r] = levels[r], levels[w]
        w += 1
print(levels, (i, w))

Variables

After line 13: levels is [0, 0, 1, 1, 2, 2]; p is 1; w is 4; r is 5; i is 2.levels000112132425p1w4r5i2
  • just taken by the loop
  • changed in this step
  • passed by the loop
  • read next
  • where the loop stopped
  • the stop value, never given

Printed so far

[0, 0, 1, 1, 2, 2] (2, 4)

Every step was recorded from a run with Python 3.14.8 on macOS 26 arm64.

The drawing shows the variables when the program ends, and the program's 36 steps are listed below.

Line run 13
Next line end
Loop pass –
Every step as text
  1. Start. No line has run yet, so there are no variables. Python starts with line 1.
  2. Line 1. levels = [2, 0, 2, 1, 1, 0] makes levels a list of 6 items.
  3. Line 2. p = 1 sets p to 1.
  4. Line 3. w = 0 sets w to 0.
  5. Line 4. for r in range(len(levels)): gives its first number: r is 0.
  6. Line 5. levels[r] < p is false (p is 1, levels is [2, 0, 2, 1, 1, 0] and r is 0), so Python skips the block under if levels[r] < p:.
  7. Line 4. for r in range(len(levels)): gives the next number: r is 1.
  8. Line 5. levels[r] < p is true (p is 1, levels is [2, 0, 2, 1, 1, 0] and r is 1), so the block under if levels[r] < p: runs.
  9. Line 6. levels[w], levels[r] = levels[r], levels[w] sets levels to [0, 2, 2, 1, 1, 0] (it was [2, 0, 2, 1, 1, 0]).
  10. Line 7. w += 1 changes w from 0 to 1.
  11. Line 4. for r in range(len(levels)): gives the next number: r is 2.
  12. Line 5. levels[r] < p is false (p is 1, levels is [0, 2, 2, 1, 1, 0] and r is 2), so Python skips the block under if levels[r] < p:.
  13. Line 4. for r in range(len(levels)): gives the next number: r is 3.
  14. Line 5. levels[r] < p is false (p is 1, levels is [0, 2, 2, 1, 1, 0] and r is 3), so Python skips the block under if levels[r] < p:.
  15. Line 4. for r in range(len(levels)): gives the next number: r is 4.
  16. Line 5. levels[r] < p is false (p is 1, levels is [0, 2, 2, 1, 1, 0] and r is 4), so Python skips the block under if levels[r] < p:.
  17. Line 4. for r in range(len(levels)): gives the next number: r is 5.
  18. Line 5. levels[r] < p is true (p is 1, levels is [0, 2, 2, 1, 1, 0] and r is 5), so the block under if levels[r] < p: runs.
  19. Line 6. levels[w], levels[r] = levels[r], levels[w] sets levels to [0, 0, 2, 1, 1, 2] (it was [0, 2, 2, 1, 1, 0]).
  20. Line 7. w += 1 changes w from 1 to 2.
  21. Line 4. for r in range(len(levels)): has no number left: a range stops before its stop value, 6, so the loop ends.
  22. Line 8. i = w sets i to 2. Key point The first pass has read all six levels and moved the two 0s to the front. The second pass starts at position 2 and reads the four levels after them again.
  23. Line 9. for r in range(i, len(levels)): gives its first number: r is 2.
  24. Line 10. levels[r] == p is false (p is 1, levels is [0, 0, 2, 1, 1, 2] and r is 2), so Python skips the block under if levels[r] == p:.
  25. Line 9. for r in range(i, len(levels)): gives the next number: r is 3.
  26. Line 10. levels[r] == p is true (p is 1, levels is [0, 0, 2, 1, 1, 2] and r is 3), so the block under if levels[r] == p: runs.
  27. Line 11. levels[w], levels[r] = levels[r], levels[w] sets levels to [0, 0, 1, 2, 1, 2] (it was [0, 0, 2, 1, 1, 2]).
  28. Line 12. w += 1 changes w from 2 to 3.
  29. Line 9. for r in range(i, len(levels)): gives the next number: r is 4.
  30. Line 10. levels[r] == p is true (p is 1, levels is [0, 0, 1, 2, 1, 2] and r is 4), so the block under if levels[r] == p: runs.
  31. Line 11. levels[w], levels[r] = levels[r], levels[w] sets levels to [0, 0, 1, 1, 2, 2] (it was [0, 0, 1, 2, 1, 2]).
  32. Line 12. w += 1 changes w from 3 to 4.
  33. Line 9. for r in range(i, len(levels)): gives the next number: r is 5.
  34. Line 10. levels[r] == p is false (p is 1, levels is [0, 0, 1, 1, 2, 2] and r is 5), so Python skips the block under if levels[r] == p:.
  35. Line 9. for r in range(i, len(levels)): has no number left: a range stops before its stop value, 6, so the loop ends.
  36. Line 13. print(levels, (i, w)) prints [0, 0, 1, 1, 2, 2] (2, 4). That was the last line, so the program ends. Ten reads for six levels. The two passes give the right groups and (2, 4), but a single pass would read each level once.

Checkpoint

Check: Sorting or two passes, and what they cost

  1. One question How many levels do the two reader–writer passes read on the first example, [2, 0, 2, 1, 1, 0] with p = 1?

    Type a number.

    A hint

    The second pass starts after the levels below p.

    Show the answer

    Answer: 10 reads

    The first pass reads all 6 levels and moves the two 0s to the front; the second starts at position 2 and reads the other 4. That is 6 + 4 = 10 reads, where one pass would read 6.

What to notice: four regions, one swap per value

Picture the list as four regions with fixed meanings: values below p, values equal to p, values not examined yet, and values above p. At the start the unexamined region is the whole list; at the end it is empty, and the other three regions are the answer. If every step examines one value and moves it into its region with at most one swap, the unexamined region shrinks by one value per step, and the pass ends after n steps.

Four regions while the pass runs, from left to right: below p, equal to p, not examined yet, and above p.During the pass< pbelow= pequalnot yetexamined> pabove

The four regions of the list while the pass runs

Text description of the diagram

The diagram shows the list split into four regions, from left to right: the values below p (marked < p), the values equal to p (marked = p), the values not examined yet (marked not yet), and the values above p (marked > p). At the start the region of values not examined yet is the whole list, and when it is empty the other three regions are the answer.

Checkpoint

Check: Four regions, one swap per value

  1. One question Each step examines one value and moves it into its region with at most one swap. Why does the pass then end after n steps?

    Choose one answer.

    Show the answer

    Answer: The unexamined region starts with n values and loses one per step

    The unexamined region is the whole list at the start and empty at the end. One value leaves it per step, so there are exactly n steps.

These questions start with your weakest idea.

Practice that adapts to you

Practise this lesson

9 questions about 9 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 9 What does the problem require of the order inside each group?

    Choose one answer.

    Show the answer

    Answer: Nothing; any order inside a group is fine

    Only the three groups and the pair (i, j) are specified. Any order inside a group is accepted, which lets a single pass with swaps meet the brief.

  2. Question 2 of 9 levels = [4, 4, 1, 9, 4] with p = 4. What pair (i, j) does the call return?

    Choose one answer.

    Show the answer

    Answer: (1, 4)

    levels[:1] holds the 1, levels[1:4] the three 4s and levels[4:] the 9, so the call returns (1, 4).

  3. Question 3 of 9 Every level of a list of n levels is below p. What pair does the call return?

    Choose one answer.

    Show the answer

    Answer: (n, n)

    levels[:i] must hold every level, so i = n, and the empty equal group means j = i. The pivot need not be in the list, as the third example shows from the other side.

  4. Question 4 of 9 What extra work does sorting do that the problem never asks for?

    Choose one answer.

    Show the answer

    Answer: It orders the values inside each group

    Sorting orders the values inside each group, which nobody asked for, and pays for it with O(n log n) comparisons instead of one look per value.

  5. Question 5 of 9 The two reader–writer passes take O(n) time and O(1) memory. Why do they still miss the brief?

    Choose one answer.

    Show the answer

    Answer: They read part of the list twice, and the brief asks for one pass

    Both passes are linear, but the second reads the part of the list after the levels below p again: 10 reads for the 6 levels of the first example, and one and a half reads per level on 100,000 random levels.

  6. Question 6 of 9 On 100,000 random levels from 0 to 9, which answer did the most work by the recorded counts?

    Choose one answer.

    Show the answer

    Answer: Sorting: 714,264 comparisons, about seven per level

    The recorded run counted 714,264 comparisons for the sort, 150,034 reads for the two passes and 100,000 reads for a single pass. The gap matters most where the step repeats, as inside quicksort.

  7. Question 7 of 9 Which four regions does the faster method keep in the list, from left to right?

    Choose one answer.

    Show the answer

    Answer: Below p, equal to p, not examined yet, above p

    The figure shows the regions in list order: values below p, values equal to p, values not examined yet and values above p. The unexamined region shrinks until only the three groups of the answer are left.

  8. Question 8 of 9 Before the first step on [2, 0, 2, 1, 1, 0], which region holds every level?

    Choose one answer.

    Show the answer

    Answer: The unexamined region

    At the start the unexamined region is the whole list, and at the end it is empty. Each step moves one value out of it, so six levels take six steps.

  9. Question 9 of 9 Sorting also forms the three groups. Why can the four-region picture do it with one look per value, where a sort needs O(n log n) comparisons?

    Choose one answer.

    Show the answer

    Answer: It only decides which of three groups each value joins, not where it ranks among all the others

    A sort answers a harder question, the order of every pair of values. The four regions need only one answer per value, below, equal or above p, so each value is looked at once.

Three pointers in one pass, step by step Pro

In this part:

  • A dry run on the first example, one row per step
  • The invariant, and a proof that each move keeps it
  • The code in 14 languages
  • Moving mid after the far swap: the bug, found by trying every small list
    • Edge cases and slips to check
  • Equal keys in quicksort, counted
  • Quickselect and other variants
  • Practise: partition around a value
    • Partition a list around a value in one pass
    • A practice set with sample answers
  • Interview questions
    • In the one-pass three-way partition, each swap sends a value to one end of the list. After which swaps may mid move on, and after which must it stay? Derive both rules from the invariant, and find a small input that breaks a version with the wrong rule.
    • Your hand-written quicksort sorts a million exam marks from 0 to 100 and is far slower than on a million distinct values. Explain why, estimate the comparisons, and fix it. What does your fix cost on distinct values?
    • You must group a million order records into overdue, due today and later, in place, keeping the original order inside each group. Can the one-pass swap partition do it? What are your options, and what does each cost?
  • Key takeaways

3 diagrams · 7 runnable examples (Python) · 1 exercise with sample tests · 3 interview answers · about 44 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Terms in this lesson

pivot
The value a partition compares every item with: items below it go to one side and items above it to the other. Quicksort takes its pivot from the part of the list it is partitioning.
three-way partition
Rearranging a list around a pivot value into three groups: the values below it, the values equal to it and the values above it, with the order inside each group left free.

References

Related tools

Python Online Compiler Real CPython in your browser — with stdin, files and a stop button. JavaScript & TypeScript Online Compiler Write, run and debug JS or TS snippets — safely sandboxed, nothing to install.

Report a problem with this lesson