INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING
01
00/15
01 / COVER MODULE 5 · TWO POINTERS
INVARIANT · MODULE 5 · TWO POINTERS
EVERY MOVE RULES SOMETHING OUT

Two indices walk an array, and each step throws away a value that can never be in the answer. Sorted order, a shorter wall or a stalled stream says which one. n² pairs become n steps. Ten moves, fifteen problems.

15Problems
5Families
10Units
10Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

CONVERGE ON A SORTED ARRAY · 04
WORK FROM THE ENDS · 05
TWO STREAMS · 04
A WRITE POINTER · 01
TWO RUNNING MAXIMA · 01
SOLVED HAS A JUDGE LINK
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
03 / MECHANISM UNIT 01 · CONVERGE ON A SORTED ARRAY

EACH SUM SAYS WHICH END TO MOVE

Too small: a[l] fails even with the largest value left, so l moves right. Too big: a[r] fails even with the smallest, so r moves left.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
04 / DRILL UNIT 01 · Converge on a Sorted Array · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

numbers = [2, 3, 5, 9, 12], target = 17. What does twoSum return?

2 + 12 and 3 + 12 fall short, so l moves twice. Then 5 + 12 = 17, at positions 3 and 5.

DRILL 02 · RECALL

s < target, so l moves right. Why can that never skip the answer?

Every r still in play is at most a[r], so every sum with a[l] is at most s. None of them reaches the target.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
05 / PROBLEM #01 · CONVERGE · MED

Two Sum II - Input Array Is Sorted

MED converge ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Two values that add up to a target, in an array that is already sorted, using O(1) extra space. Positions count from 1.

INTUITION

Start at both ends. A sum that is too small can only grow by moving l right; a sum that is too big can only shrink by moving r left. Each move throws away a value that can never be in the answer.

STEPS
  1. l = 0, r = n − 1
  2. s = a[l] + a[r]; equal to the target: return [l + 1, r + 1]
  3. s too small: a[l] fails even with the largest value left, so l++
  4. s too big: a[r] fails even with the smallest value left, so move r left
BRUTEO(n²) trying every pair
→
OPTIMALO(n)
↕ SCROLL
vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = numbers.size() - 1;
    while (l < r) {
        int s = numbers[l] + numbers[r];
        if (s == target) return {l + 1, r + 1};
        if (s < target) l++;               // numbers[l] is too small for every r left
        else r--;                          // numbers[r] is too big for every l left
    }
    return {};                             // not reached: one answer is promised
}
TIMEO(n)each step moves one pointer, and they meet after n − 1 steps
SPACEO(1)two indices
TRAP

Reaching for a hash map. It passes, but it uses O(n) space, which the problem rules out, and it ignores the one thing the input gives you for free: the order.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
06 / PROBLEM #02 · CONVERGE · EASY

Sum of Two Values

EASY converge ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Two values at different positions that sum to x, and the positions are printed. The array is not sorted.

INTUITION

Sort, and the scan of row 1 finds the pair. Sorting loses the positions, so sort (value, position) pairs and print the positions they carry.

STEPS
  1. Read the values and pair each with its position (1-based)
  2. Sort the pairs by value
  3. Run row 1's scan on the values
  4. Print the two carried positions, or IMPOSSIBLE
BRUTEO(n²) trying every pair, too slow for n = 2·10⁵
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; long long x;
    scanf("%d %lld", &n, &x);
    vector<pair<long long, int> > a(n);    // (value, position)
    for (int i = 0; i < n; i++) { scanf("%lld", &a[i].first); a[i].second = i + 1; }
    sort(a.begin(), a.end());
    int l = 0, r = n - 1;
    while (l < r) {
        long long s = a[l].first + a[r].first;
        if (s == x) { printf("%d %d\n", a[l].second, a[r].second); return 0; }
        if (s < x) l++; else r--;
    }
    puts("IMPOSSIBLE");
}
TIMEO(n log n)the sort; the scan after it is O(n)
SPACEO(n)the (value, position) pairs
TRAP

Sorting the bare values. The scan then finds the right values and prints where they sit after sorting. Carry each value's original position through the sort.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
07 / DRILL UNIT 01 · Converge on a Sorted Array · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Sum of Two Values with x = 6 and values 3 1 3. What does the program print?

After sorting the pairs, the two 3s carry positions 1 and 3. The pointers never share a cell, so position 1 is not used twice.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
08 / MECHANISM UNIT 02 · CONVERGE INSIDE A LOOP

ONE TEST, MANY PAIRS

With a[k] the longest side, a passing a[l] + a[r] passes for every l' up to r − 1 as well. Count r − l at once and move r.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
09 / DRILL UNIT 02 · Converge Inside a Loop · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

triangleNumber([2, 2, 3, 4])?

(2, 3, 4) works with either 2, and (2, 2, 3) works. (2, 2, 4) does not: 2 + 2 is not more than 4.

DRILL 02 · RECALL

3Sum Closest runs unit 1's scan once per first value. What does the whole run cost?

n first values, and an O(n) scan for each. The sort, O(n log n), is smaller.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
10 / PROBLEM #03 · CONVERGE · MED

3Sum Closest

MED converge ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Three values whose sum is closest to a target. Not equal to it: closest, and the sum itself is returned.

INTUITION

Sort. Fix the first value, then run unit 1's scan on everything after it, keeping the sum that has come closest. A sum equal to the target cannot be beaten, so return it at once.

STEPS
  1. Sort; best = the sum of the first three
  2. For each first value i: l = i + 1, r = n − 1
  3. s = nums[i] + nums[l] + nums[r]; keep it if it is closer than best
  4. s too small: move l right; too big: move r left; equal: return s
BRUTEO(n³) trying every triple
→
OPTIMALO(n²)
↕ SCROLL
int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size(), best = nums[0] + nums[1] + nums[2];
    for (int i = 0; i + 2 < n; i++) {
        int l = i + 1, r = n - 1;              // unit 1's scan, for each first value
        while (l < r) {
            int s = nums[i] + nums[l] + nums[r];
            if (abs(s - target) < abs(best - target)) best = s;
            if (s < target) l++;
            else if (s > target) r--;
            else return s;                     // distance 0 cannot be beaten
        }
    }
    return best;
}
TIMEO(n²)n first values, each with an O(n) scan
SPACEO(1)beyond the sort
TRAP

Starting best at a huge number. best − target then overflows in C++ and Java. Start from a real sum, the first three values.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
11 / DRILL UNIT 02 · Converge Inside a Loop · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

threeSumClosest([−1, 2, 1, −4], 1)?

−1 + 2 + 1 = 2, at distance 1. No triple sums to exactly 1.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
12 / PROBLEM #04 · CONVERGE · MED

Valid Triangle Number

MED converge ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Count the triples that can be the sides of a triangle. Counting, so a scan that finds one pair at a time is too slow.

INTUITION

Sort, and take a[k] as the longest side. A pair works when a[l] + a[r] > a[k]. When it does, every l' from l to r − 1 works with r too, because those values are at least a[l]: add r − l in one step.

STEPS
  1. Sort; for k from n − 1 down to 2, a[k] is the longest side
  2. l = 0, r = k − 1
  3. a[l] + a[r] > a[k]: count += r − l, then move r left
  4. Otherwise a[l] is too short for every r left: l++
BRUTEO(n³) testing every triple
→
OPTIMALO(n²)
↕ SCROLL
int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int count = 0;
    for (int k = nums.size() - 1; k >= 2; k--) {   // nums[k]: the longest side
        int l = 0, r = k - 1;
        while (l < r) {
            if (nums[l] + nums[r] > nums[k]) {
                count += r - l;            // nums[l..r-1] each work with nums[r]
                r--;
            } else l++;                    // nums[l] is too short for every r left
        }
    }
    return count;
}
TIMEO(n²)n longest sides, each with an O(n) scan
SPACEO(1)beyond the sort
TRAP

Fixing the shortest side instead of the longest. With a[i] fixed first, a passing test says nothing about the pairs beside it, and the scan cannot count them at once. The longest side has to be the fixed one.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
13 / MECHANISM UNIT 03 · FILL FROM THE ENDS

THE LARGEST SQUARE IS AT AN END

Compare the sizes at the two ends and write the larger square at the back of the output. The smallest can be anywhere; the largest cannot.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
14 / DRILL UNIT 03 · Fill from the Ends

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

sortedSquares([−7, −3, 2, 3, 11])?

11 has the largest size, then −7, then −3 and 3, then 2. Written from the back, the output comes out sorted.

DRILL 02 · RECALL

Why does out fill from the back, not the front?

The smallest square sits where the sign changes, which can be the middle. The largest is always at one of the two ends.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
15 / PROBLEM #05 · ENDS · EASY

Squares of a Sorted Array

EASY ends ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Square every value of a sorted array and return the squares sorted. Negatives are allowed, so squaring breaks the order.

INTUITION

The largest square belongs to whichever end has the larger absolute value. Compare the two ends, write the larger square at the back of the output, and move that end in.

STEPS
  1. l = 0, r = n − 1
  2. For w from n − 1 down to 0
  3. |a[l]| > |a[r]|: out[w] = a[l]², l++
  4. Otherwise out[w] = a[r]², and r moves left
BRUTEO(n log n) squaring, then sorting
→
OPTIMALO(n)
↕ SCROLL
vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size(), l = 0, r = n - 1;
    vector<int> out(n);
    for (int w = n - 1; w >= 0; w--) {     // the largest square goes last
        if (abs(nums[l]) > abs(nums[r])) {
            out[w] = nums[l] * nums[l]; l++;
        } else {
            out[w] = nums[r] * nums[r]; r--;
        }
    }
    return out;
}
TIMEO(n)one comparison per output cell
SPACEO(n)the output array
TRAP

Filling from the front. The smallest square can sit anywhere in the middle, where the sign changes. Only the largest is guaranteed to be at an end.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
16 / MECHANISM UNIT 04 · THE CONTAINER

THE SHORTER WALL CANNOT DO BETTER

Every other container with the shorter wall is narrower and no taller. Measure, keep the best, and move the shorter wall in.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
17 / DRILL UNIT 04 · Move the Shorter Side · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

maxArea([4, 3, 2, 1, 4])?

The two 4s at the ends hold 4 × 4 = 16 between them, and no narrower pair beats it.

DRILL 02 · BUG

A solution moves the taller wall each time. What does it return on [1, 2, 4, 3]?

It drops the 3, then the 4, then the 2, keeping the 1 every time. The pair 2 and 3, which holds 4, is never measured.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
18 / PROBLEM #06 · ENDS · MED

Container With Most Water

MED ends ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Pick two walls; the water between them is min(h[l], h[r]) · (r − l). Maximise it over every pair.

INTUITION

Start with the widest pair. The shorter wall caps every container it is still part of, and each of those is narrower, so none can beat the one just measured. Drop the shorter wall and measure again.

STEPS
  1. l = 0, r = n − 1, best = 0
  2. area = min(h[l], h[r]) · (r − l); keep the best
  3. Move the pointer at the shorter wall inward
  4. Stop when l meets r
BRUTEO(n²) measuring every pair
→
OPTIMALO(n)
↕ SCROLL
int maxArea(vector<int>& height) {
    int l = 0, r = height.size() - 1, best = 0;
    while (l < r) {
        int area = min(height[l], height[r]) * (r - l);
        best = max(best, area);
        if (height[l] < height[r]) l++;    // the shorter wall cannot do better
        else r--;
    }
    return best;
}
TIMEO(n)one pointer moves per step
SPACEO(1)three numbers
TRAP

Moving the taller wall. The width shrinks and the height is still capped by the shorter wall, so it can only lose, and it may step past the answer.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
19 / PROBLEM #07 · ENDS · EASY

Alice, Bob and Chocolate

EASY ends ▶ SOLVE ON CODEFORCESCodeforces 6C, rated 1200.
SIGNAL — WHAT GIVES IT AWAY

Alice eats bars from the left, Bob from the right, at the same speed. Who gets each bar? On a tie for the last bar, Alice.

INTUITION

Keep how long each has been eating. Whoever has eaten for less time finishes first and takes the next bar from their end; on a tie it is Alice. Stop when the two ends cross.

STEPS
  1. l = 0, r = n − 1, ta = tb = 0
  2. ta ≤ tb: Alice takes bar l, ta += t[l], l++
  3. Otherwise Bob takes bar r, tb += t[r], and r moves left
  4. Print l and n − l
BRUTEO(n) per bar replaying the clock, O(n²) overall
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<int> t(n);
    for (int i = 0; i < n; i++) scanf("%d", &t[i]);
    int l = 0, r = n - 1;
    long long ta = 0, tb = 0;              // how long each has been eating
    while (l <= r) {
        if (ta <= tb) ta += t[l++];        // Alice is free first; a tie is hers
        else tb += t[r--];
    }
    printf("%d %d\n", l, n - l);
}
TIMEO(n)each bar is taken once
SPACEO(1)two times and two indices
TRAP

ta < tb instead of ta ≤ tb. On a tie Bob would take the bar, and the statement gives it to Alice. On 1 1 1 that prints 1 2 instead of 2 1.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
20 / DRILL UNIT 04 · Move the Shorter Side · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Alice, Bob and Chocolate with bars 1 1 1. What is printed?

Alice and Bob each eat one bar. Both finish at time 1 and reach the middle bar together, so it goes to Alice.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
21 / MECHANISM UNIT 05 · SORT, THEN PAIR THE ENDS

THE HEAVIEST GOES NOW

The heaviest person left needs a boat. The lightest rides along if they fit; if the lightest cannot, nobody can.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
22 / DRILL UNIT 05 · Sort, Then Pair the Ends

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

numRescueBoats([3, 2, 2, 1], 3)?

Sorted: 1 2 2 3. The 3 goes alone, 1 and 2 share, and the other 2 goes alone.

DRILL 02 · RECALL

Why does the heaviest person ride with the lightest, and not with the heaviest partner that fits?

Anyone who could share with the heaviest is at least as heavy as the lightest. Taking the lightest leaves the heavier people, who are harder to pair, no worse off.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
23 / PROBLEM #08 · ENDS · MED

Boats to Save People

MED ends ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Each boat holds at most two people and at most limit in weight. The fewest boats for everyone.

INTUITION

Sort. The heaviest person left needs a boat now. If even the lightest cannot share it, nobody can, so they go alone; if the lightest can, they ride along, and no other choice would do better.

STEPS
  1. Sort; l = 0, r = n − 1
  2. If p[l] + p[r] ≤ limit, the lightest rides along: l++
  3. The heaviest always goes, so r moves left
  4. One more boat; repeat while l ≤ r
BRUTEO(n²) pairing each heaviest with the heaviest partner that fits
→
OPTIMALO(n log n)
↕ SCROLL
int numRescueBoats(vector<int>& people, int limit) {
    sort(people.begin(), people.end());
    int l = 0, r = people.size() - 1, boats = 0;
    while (l <= r) {
        if (people[l] + people[r] <= limit) l++;   // the lightest rides along
        r--;                               // the heaviest always goes
        boats++;
    }
    return boats;
}
TIMEO(n log n)the sort; the pairing is O(n)
SPACEO(1)beyond the sort
TRAP

while (l < r). The last person, alone in the middle, never gets a boat. With l ≤ r they do, and the test adding them to themselves only moves l.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
24 / MECHANISM UNIT 06 · SWAP FROM BOTH ENDS

TWO ZONES GROW INWARD

Evens collect on the left and odds on the right. A misplaced pair, odd on the left and even on the right, is fixed by one swap.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
25 / DRILL UNIT 06 · Swap from Both Ends

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

sortArrayByParity([1, 2, 3, 4]), with the two-pointer code?

1 and 4 are both misplaced and swap. Then 2 is already even, l reaches r, and the scan stops.

DRILL 02 · RECALL

At most how many swaps does the scan make on n values?

Each swap moves both pointers in by one, and they start n − 1 apart.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
26 / PROBLEM #09 · ENDS · EASY

Sort Array By Parity

EASY ends ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Move every even value before every odd value, in place. Any order inside each group is accepted.

INTUITION

Grow an even zone from the left and an odd zone from the right. A value already on its side just extends its zone. When the left holds an odd and the right an even, one swap fixes both.

STEPS
  1. l = 0, r = n − 1
  2. a[l] even: l++
  3. Else a[r] odd: r--
  4. Else swap a[l] and a[r], then move both pointers in
BRUTEO(n) with a second array: evens, then odds
→
OPTIMALO(n)
↕ SCROLL
vector<int> sortArrayByParity(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        if (nums[l] % 2 == 0) l++;         // already on the even side
        else if (nums[r] % 2 == 1) r--;    // already on the odd side
        else swap(nums[l++], nums[r--]);   // both misplaced: trade them
    }
    return nums;
}
TIMEO(n)each step settles at least one cell
SPACEO(1)in place
TRAP

Testing x % 2 == 1 for odd in a language with negative remainders. In C++ and Java, −3 % 2 is −1. The values here are never negative, but on a variant that allows them, test x % 2 != 0.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
27 / MECHANISM UNIT 07 · TWO SORTED STREAMS

THE SMALLER HEAD LEAVES

Two sorted streams. The smaller head can never meet its equal, so it leaves; equal heads are a match and both move.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
28 / DRILL UNIT 07 · Two Sorted Streams · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

intersect([1, 2, 2, 1], [2, 2])?

Both arrays hold two 2s, so 2 is output twice. The 1s have no partner.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
29 / PROBLEM #10 · STREAMS · EASY

Intersection of Two Arrays II

EASY streams ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Every value that appears in both arrays, as many times as it appears in both. Any order.

INTUITION

Sort both and read them as two rising streams. The smaller head can never meet its equal in the other stream, so it leaves. Equal heads are a match: take one copy and advance both.

STEPS
  1. Sort a and b; i = j = 0
  2. a[i] < b[j]: i++
  3. a[i] > b[j]: j++
  4. Equal: output it, i++ and j++
BRUTEO(n · m) searching b for each value of a and crossing it out
→
OPTIMALO(n log n + m log m)
↕ SCROLL
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    int i = 0, j = 0;
    vector<int> out;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j]) i++;          // no partner left in nums2
        else if (nums1[i] > nums2[j]) j++;     // no partner left in nums1
        else { out.push_back(nums1[i]); i++; j++; }
    }
    return out;
}
TIMEO(n log n + m log m)the sorts; the merge is O(n + m)
SPACEO(1)beyond the output
TRAP

A set instead of a count. A set keeps one copy of each value, but a value appearing twice in both arrays must be output twice. The merge, or a counter, keeps the copies.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
30 / PROBLEM #11 · STREAMS · MED

Apartments

MED streams ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Give apartments to applicants; applicant i accepts any size within k of a[i]. The most applicants housed.

INTUITION

Sort both. Take the smallest applicant and the smallest apartment. An apartment too small for this applicant is too small for every later one; an applicant for whom every apartment left is too big gets none. Otherwise the match is safe: take it.

STEPS
  1. Sort a and b; i = j = got = 0
  2. b[j] < a[i] − k: the apartment is too small for everyone left, j++
  3. b[j] > a[i] + k: applicant i gets nothing, i++
  4. Otherwise match them: got++, i++, j++
BRUTEa bipartite matching over every acceptable pair, O(n · m) edges
→
OPTIMALO(n log n + m log m)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; long long k;
    scanf("%d %d %lld", &n, &m, &k);
    vector<long long> a(n), b(m);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for (int j = 0; j < m; j++) scanf("%lld", &b[j]);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int i = 0, j = 0, got = 0;
    while (i < n && j < m) {
        if (b[j] < a[i] - k) j++;          // too small for everyone left
        else if (b[j] > a[i] + k) i++;     // every apartment left is too big
        else { got++; i++; j++; }
    }
    printf("%d\n", got);
}
TIMEO(n log n + m log m)the sorts; the merge is O(n + m)
SPACEO(1)beyond the input
TRAP

int for a[i] + k. Both can be 10⁹, and the sum overflows a 32-bit int. Use 64-bit values for the comparison.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
31 / DRILL UNIT 07 · Two Sorted Streams · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Apartments with k = 0, desired sizes 5 5 and apartments 5 6. What is printed?

One applicant gets the 5. The 6 is outside 5 ± 0, so the other gets nothing.

DRILL 02 · RECALL

An apartment with b[j] < a[i] − k is skipped for good. Why is that safe?

The applicants are sorted, so a[i] − k only rises. An apartment below it now stays below it.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
32 / MECHANISM UNIT 08 · ONE STREAM MAY STALL

ONE STREAM STALLS

t always moves. s moves only when its wanted letter turns up, so the order of s is kept and the gaps in t are skipped.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
33 / DRILL UNIT 08 · One Stream May Stall · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

isSubsequence("axc", "ahbgdc"). What is i when the scan ends?

a is found at once. x never turns up, so s stalls at i = 1 and the answer is false.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
34 / PROBLEM #12 · STREAMS · EASY

Is Subsequence

EASY streams ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Can s be read out of t left to right, skipping letters of t? The order matters; the gaps do not.

INTUITION

Walk t once. i is the next letter of s still wanted. A letter of t that matches it is used, and i moves on; any other letter is skipped. s stalls while t keeps moving.

STEPS
  1. i = 0
  2. For each letter of t, while i < |s|
  3. If it equals s[i], i++
  4. Return i == |s|
BRUTEexponential, trying every subset of t's letters
→
OPTIMALO(|t|)
↕ SCROLL
bool isSubsequence(string s, string t) {
    int i = 0;                             // the next letter of s to find
    for (int j = 0; j < t.size() && i < s.size(); j++)
        if (s[i] == t[j]) i++;             // found it; look for the next
    return i == s.size();
}
TIMEO(|t|)one look at each letter of t
SPACEO(1)one index
TRAP

Reading s[i] after i reaches the end. Once every letter is found, s[i] is past the end of s. Test i < |s| first.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
35 / PROBLEM #13 · STREAMS · EASY

Backspace String Compare

EASY streams ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Two strings typed into an editor where # is backspace. Are the results equal? Follow-up: O(1) extra space.

INTUITION

A # erases the letter before it, so read both strings from the back. Count the #s seen; a letter met while the count is positive is erased. Compare the surviving letters one pair at a time.

STEPS
  1. i, j at the ends of s and t
  2. Move each back to its next surviving letter, skipping erased ones
  3. If one string has run out, equal only if both have
  4. Different letters: false. Otherwise step i and j back
BRUTEO(n + m) time and space, building both results on a stack
→
OPTIMALO(n + m)
↕ SCROLL
int survivor(const string& x, int k) {    // the next letter that survives, or -1
    int skip = 0;
    for (; k >= 0; k--) {
        if (x[k] == '#') skip++;
        else if (skip > 0) skip--;         // erased by a later #
        else break;
    }
    return k;
}
bool backspaceCompare(string s, string t) {
    int i = (int)s.size() - 1, j = (int)t.size() - 1;
    while (true) {
        i = survivor(s, i); j = survivor(t, j);
        if (i < 0 || j < 0) return i < 0 && j < 0;
        if (s[i] != t[j]) return false;
        i--; j--;
    }
}
TIMEO(n + m)each character is looked at once
SPACEO(1)two indices and two counters
TRAP

Reading from the front. A letter's fate depends on #s that come after it, so the front cannot decide it without a stack. From the back, the #s arrive first.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
36 / DRILL UNIT 08 · One Stream May Stall · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

What does "a##c" become once its backspaces are applied?

The first # erases a, and the second has nothing to erase. Then c is typed.

DRILL 02 · RECALL

Why does Backspace String Compare read from the back?

From the back, each # is counted before the letter it erases, so one counter decides every letter.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
37 / MECHANISM UNIT 09 · A WRITE POINTER WITH A RULE

READ AHEAD, WRITE BEHIND

i reads every value; k writes the kept ones. A value is kept unless the answer already ends in two copies of it: compare with a[k − 2].

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
38 / DRILL UNIT 09 · A Write Pointer with a Rule

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

removeDuplicates([0, 0, 1, 1, 1, 1, 2, 3, 3])?

Two 0s, two 1s, one 2 and two 3s are kept: 0 0 1 1 2 3 3.

DRILL 02 · BUG

A solution keeps a[i] when k < 2 || a[i] != a[i − 2], in place. What does it return on [1, 1, 1, 2, 2, 3]?

Writing the first 2 overwrites a[2]. The second 2 then matches a[2] and looks like a third copy, so it is dropped.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
39 / PROBLEM #14 · WRITE · MED

Remove Duplicates from Sorted Array II

MED write ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A sorted array; keep at most two copies of each value, in place, and return how many are kept.

INTUITION

a[0..k) is the answer so far. A value can join it unless the answer already ends in two copies of it, and because the array is sorted, that shows in one place: a[k − 2].

STEPS
  1. k = 0
  2. For each i
  3. If k < 2 or a[i] ≠ a[k − 2], write a[k] = a[i] and k++
  4. Return k
BRUTEO(n) with a second array and a run counter
→
OPTIMALO(n)
↕ SCROLL
int removeDuplicates(vector<int>& nums) {
    int k = 0;                             // nums[0..k) is the answer so far
    for (int i = 0; i < nums.size(); i++)
        if (k < 2 || nums[i] != nums[k - 2])   // at most two copies of each
            nums[k++] = nums[i];
    return k;
}
TIMEO(n)one look at each value
SPACEO(1)in place
TRAP

Comparing with nums[i − 2]. The write pointer may have overwritten that cell, so it no longer holds what was read. The rule is about the answer, so compare with nums[k − 2].

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
40 / MECHANISM UNIT 10 · THE RAIN WATER

SETTLE THE SIDE WITH THE LOWER WALL

When h[l] < h[r], the right already holds a wall of at least h[r], so lmax is the lower wall at l. Settle it and move l. Otherwise settle r with rmax.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
41 / DRILL UNIT 10 · Two Running Maxima · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

trap([4, 2, 0, 3, 2, 5])?

Every bar sits under the 4 on the left, the lower of the two end walls: 2 + 4 + 1 + 2 = 9.

DRILL 02 · RECALL

h[l] < h[r], so the water at l is settled with lmax alone. Why is rmax not needed?

Water at l is the lower of the two walls. The right wall is at least h[r], and lmax has never beaten a right wall so far, so lmax is the lower one.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
42 / DRILL UNIT 10 · Two Running Maxima · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

trap([2, 0, 2])?

The middle bar sits between two walls of 2, so 2 units of water stand on it.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
43 / PROBLEM #15 · WALLS · HARD

Trapping Rain Water

HARD walls ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Bars of width 1; how much rain is trapped between them? Water above a bar is the lower of the tallest walls on each side, minus the bar.

INTUITION

Walk in from both ends. When h[l] < h[r], the right side already has a wall at least h[r], so the lower wall at l is lmax, the tallest bar from the left. Settle l with lmax and move on. Otherwise settle r with rmax.

STEPS
  1. l = 0, r = n − 1, lmax = rmax = 0
  2. h[l] < h[r]: lmax = max(lmax, h[l]); water += lmax − h[l]; l++
  3. Otherwise: rmax = max(rmax, h[r]); water += rmax − h[r]; move r left
  4. Stop when l meets r
BRUTEO(n²) finding the tallest bar on each side of every bar
→
OPTIMALO(n)
↕ SCROLL
int trap(vector<int>& height) {
    int l = 0, r = height.size() - 1, lmax = 0, rmax = 0, water = 0;
    while (l < r) {
        if (height[l] < height[r]) {       // the right wall is at least height[r]
            lmax = max(lmax, height[l]);
            water += lmax - height[l]; l++;
        } else {
            rmax = max(rmax, height[r]);
            water += rmax - height[r]; r--;
        }
    }
    return water;
}
TIMEO(n)each bar is settled once
SPACEO(1)two maxima and two indices
TRAP

Using lmax on the side that is taller. The water at l is bounded by the lower wall, and lmax is only known to be the lower one when h[l] < h[r]. Move the side with the smaller bar, and settle it with its own maximum.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
44 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Ten moves, and each has a phrase in the statement that gives it away.

A PAIR WITH A GIVEN SUM IN A SORTED ARRAY

pointers at both ends; the sum says which one moves

CONVERGEO(n)
THREE VALUES, OR COUNT THE PAIRS

fix one value, converge on the rest; a passing test counts r − l pairs

CONVERGE IN A LOOPO(n²)
A SORTED ARRAY TRANSFORMED, THE ORDER BROKEN

the extremes sit at the ends; fill the output from the back

FILL FROM THE ENDSO(n)
THE BEST PAIR, WHERE THE SMALLER SIDE CAPS IT

measure the widest, then drop the side that limits it

MOVE THE SHORTER SIDEO(n)
PAIR THINGS UNDER A LIMIT, FEWEST GROUPS

sort; the heaviest goes now, the lightest rides along if it fits

PAIR THE ENDSO(n log n)
REARRANGE INTO TWO GROUPS, IN PLACE

two zones grow inward; swap a misplaced pair

SWAP FROM BOTH ENDSO(n)
TWO ARRAYS, MATCH THEIR VALUES

sort both; the smaller head leaves, equal heads match

TWO SORTED STREAMSO(n log n)
ONE SEQUENCE INSIDE ANOTHER, IN ORDER

the long stream always moves; the short one only on a match

ONE STREAM STALLSO(n)
REMOVE IN PLACE, KEEP WHAT A RULE ALLOWS

read with i, write with k; compare with the answer, a[k − 1] or a[k − 2]

WRITE POINTERO(n)
WATER, OR ANYTHING BOUNDED BY THE LOWER OF TWO MAXIMA

two running maxima; settle the side whose wall is lower

TWO RUNNING MAXIMAO(n)
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
45 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

A sorted array and a target. Count the pairs whose sum is less than the target. Which move?

When a[l] + a[r] < target, every r' from l + 1 to r works with l too: add r − l and move l. It is unit 2's counting step, mirrored.

DRILL 02 · TRANSFER

Merge Sorted Array writes nums2 into the spare cells at the end of nums1. Which move fills nums1 without overwriting anything still unread?

Compare the largest unread value of each array and write it at the back. The back is empty, so nothing unread is overwritten.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
46 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Sort Colors puts the 0s, then the 1s, then the 2s, in one pass and in place. Which move does it grow from?

It is unit 6 with three zones: 0s grow from the left, 2s from the right, and a middle pointer swaps each value toward its zone.

DRILL 02 · RECALL

Why is converging on an array O(n)?

The gap between l and r shrinks by one per step, so the scan ends within n − 1 steps.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
47 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

SORTING AWAY THE POSITIONS

When the answer is positions, sort (value, position) pairs. Sorting the bare values finds the right values at the wrong places.

MOVING THE WRONG SIDE

In the container, the taller wall is never the limit. Moving it shrinks the width without raising the cap, and can skip the answer.

l < r WHERE l ≤ r BELONGS

When the middle value still needs handling, such as the last person waiting for a boat, the loop must run at l = r too.

COMPARING WITH A CELL ALREADY OVERWRITTEN

A write pointer changes cells behind the read pointer. Compare with the answer, a[k − 2], not with a[i − 2].

A SET WHERE COPIES COUNT

Intersection II wants each value as often as it is in both. A set keeps one copy; the merge keeps every match.

OVERFLOW IN THE SUM

Two values up to 10⁹ add up past a 32-bit int. CSES 1640 and 1084 need 64-bit sums and bounds.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
48 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Ten moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Converge
O(n)
O(1)
sorted; too small moves l, too big moves r
Converge in a loop
O(n²)
O(1)
fix one value; a passing test counts r − l
Fill from the ends
O(n)
O(n)
the largest is at an end; write the output backwards
Move the shorter side
O(n)
O(1)
the shorter wall caps every narrower container
Pair the ends
O(n log n)
O(1)
the heaviest goes; the lightest rides if it fits
Swap from both ends
O(n)
O(1)
two zones grow; one swap fixes a misplaced pair
Two sorted streams
O(n log n)
O(1)
the smaller head leaves; equal heads match
One stream stalls
O(n)
O(1)
the long stream always moves; the short one on a match
Write pointer
O(n)
O(1)
read with i, write with k, compare with a[k − 2]
Two running maxima
O(n)
O(1)
settle the side with the lower wall by its own max
INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
49 / CLOSE MODULE 5 · TWO POINTERS

MOVE IT YOURSELF

A sum said which end to move; one passing test counted many pairs; the largest square came from an end; the shorter wall stepped in; the heaviest took a boat; a misplaced pair swapped; two sorted streams met; one stream stalled while the other read on; a write pointer kept what its rule allowed; and the lower wall settled the water. 3Sum and 4Sum (arrays 2) run unit 2's loop with one and two values fixed, Valid Palindrome (strings) converges on letters, Merge Sorted Array (arrays 1) fills from the back, and Ferris Wheel (CSES 1090) is unit 5 with a different input.

00%
OF THIS DECK SOLVED
← ALL TOPICS← HASHING & PREFIX SUMSSLIDING WINDOW →

Module 5. Fifteen problems: twelve on LeetCode, two on CSES and one on Codeforces. Next: the sliding window, two pointers that move the same way.

INVARIANT · TWO POINTERS · CONVERGING, MERGING, WRITING · TWO POINTERS
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 5 · TWO POINTERS

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.