Two-pointer assignment after sorting

43 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four children have greed levels 1, 2, 3 and 7: a child is content only with a cookie at least that big. The cookies have sizes 1, 1, 3 and 4. Each child gets at most one cookie. How many children can be made content? By hand you would start matching: give a 1-cookie to the child who needs 1, the 3-cookie to the child who needs 2, the 4-cookie to the child who needs 3, and nobody can satisfy the child who needs 7. Three content children. You can also feel why giving the 4-cookie to the child who needs 1 would be a mistake: it wastes the biggest cookie on the easiest child.

Trying every way to hand out the cookies is a lot of ways; with n children and m cookies it grows like a factorial. The hand method found the answer by one principle: never spend a big cookie where a small one would do.

Build the structure, one piece at a time

Piece one: sort both lists. Children by greed: 1, 2, 3, 7. Cookies by size: 1, 1, 3, 4. Sorting is what turns the loose principle into a procedure.

Piece two: two pointers, one at the smallest child and one at the smallest cookie. Compare the pair at the pointers. If the cookie is big enough, assign it, and advance both. If it is too small, it is too small for every remaining child as well, because the children only get greedier from here; discard it and advance only the cookie pointer:

The same two sorted lists and two pointers solve the mirror problems: pairing players with trainers of at least their strength, or loading boats where the lightest and heaviest person are paired from the two ends of one sorted list.

Why it is correct

The invariant is that after each step, the assignments made so far are part of some best possible assignment of the whole input. The argument is an exchange. Consider the smallest child c and the smallest cookie s that fits c. In any best assignment, either c gets no cookie, or c gets some cookie s′ ≥ s, or s goes to some other child c′ ≥ c. In each case we can rearrange without losing a content child: give s to c, and give s′ (which is at least s) to c′ (whom s satisfied, so s′ does too). So there is a best assignment that makes the greedy choice, and the invariant survives. A cookie that does not fit the smallest remaining child fits no remaining child, so discarding it loses nothing. Since every step keeps us inside some optimal assignment, the final count is optimal.

Why it is fast

Sorting the two lists costs O(n log n + m log m). After that, each step advances at least one pointer and neither pointer ever moves backwards, so there are at most n + m steps:

time = O(n log n + m log m), extra memory O(1)

Against trying all assignments, which is exponential, the whole cost is the sort. If the sizes are small integers, a counting sort makes even that linear.

How to recognise it in an interview

Cues: two lists to be paired up, "each ... at most once", "at least as big as", "maximise the number of pairs", "minimum number of boats or rooms". Say: "sort both sides and walk them with two pointers, matching the least demanding item with the smallest supply that fits; an exchange argument shows the greedy choice is never worse".

Assign Cookies is the walk-through. Maximum Matching of Players With Trainers is the same code with players as children and trainers as cookies. Boats to Save People sorts one list and uses a pointer at each end: the heaviest person boards, and the lightest joins if the limit allows, which is the same exchange argument applied to pairs.

02The idea in one line

Sort both sides; match the smallest demand with the smallest supply that fits.

Reach for it when: Assign cookies, boats, advantage shuffle, max matching of pairs.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: Assign Cookies g=[1,2,3] s=[1,1]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort both; give the smallest cookie that fits to the least greedy child
2. cookie 1 ≥ greed 1: assign, advance both
3. now child 1 (greed 2) vs cookie 1 (size 1)
4. cookie 1 < greed 2: too small for anyone left, skip the cookie
5. now child 1 (greed 2) vs cookie 2 (size 3)
6. cookie 3 ≥ greed 2: assign, advance both
7. now child 2 (greed 3) vs cookie 3 (size 4)
8. cookie 4 ≥ greed 3: assign, advance both
9. Out of cookies: 3 content children (child with greed 7 gets none)
10. Exchange argument: a bigger cookie never helps a smaller child more
11. Sort O(n log n), then one linear two-pointer pass

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Greedy: Furthest reach (jump game), Sort, then take greedily, Reset-on-negative sweep, Last-occurrence partition, Two-pass neighbour constraints, Counting-based greedy (small alphabet).