Pairs and Design
What is this?
A frequency map is usually introduced as bookkeeping: how many of each thing do I have? These three problems use it as something sharper: a way to avoid ever looking at a pair. If you want to know how many pairs of people in a room share a birthday, you do not compare everyone with everyone. You count birthdays and do arithmetic on the counts. Every pairwise comparison becomes one pass and a formula.
Fun fact: Number of Boomerangs is a small lesson in why counting beats enumerating. There are up to n² ordered pairs to consider, but for each pivot you only need how many points sit at each distance, and
kpoints at one distance contribute exactlyk × (k − 1)ordered pairs. That is the number of ordered pairs you can pick fromkitems.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
The short version: when a problem is about pairs, groups or arrangements, count first and reason about the counts. Comparing two multisets settles "is this an anagram of that" in one step. A tally around a pivot replaces a quadratic scan with a formula. Sorted counts turn an assignment problem into a greedy walk.
1. Three uses of one structure
Match a multiset. Two collections are permutations of each other exactly when their frequency maps are equal. That turns "does this window contain all these words, in any order?" into "does this window's count map equal the target's?" You update that map incrementally, adding the entering item and removing the leaving one, rather than rebuilding it at every position.
Count around a pivot. Fix one element and tally a property of everything else relative to it. Anything you would have found by examining pairs is now recoverable from the tally with arithmetic. The saving is one order of magnitude: n pivots × one pass each, instead of n × n × a comparison.
Tier by frequency. When items have costs that come in tiers and you may choose the assignment, sort the frequencies descending and hand the cheapest tier to the most frequent item. The exchange argument is short (swapping any two assignments that violate this order cannot improve the total) and it is what makes the greedy provable rather than plausible.
2. Where you'll actually meet this
- Search and text matching. Bag-of-words models compare multisets of words rather than sequences.
- Spatial data. "How many points are at each distance from this one" is a naive building block for neighbour queries. Real systems use spatial indexes such as k-d trees instead of a full scan.
- Keyboard layout. Minimum Number of Keypresses is the same idea as putting frequent letters on the cheapest positions of a multi-tap keypad.
- Compression. Huffman coding follows the same principle: the more frequent a symbol, the shorter its code. It uses a tree rather than fixed tiers, but the frequency-first instinct is the same.
- Rate limiting. Counting events per key and acting on the counts, rather than comparing events pairwise, is the standard shape.
3. A 30-second worked example (count around a pivot)
Points [(0,0), (1,0), (2,0)]. How many ordered triples (i, j, k) of distinct points have dist(i,j) == dist(i,k)?
Note two things: the tally is rebuilt per pivot (so the map is cleared each time), and distances are compared squared, because taking square roots introduces floating-point error for no benefit.
4. Problems in this chapter
Substring with Concatenation of All Words
Find every start index where a concatenation of all the given words (each once, any order) appears. All words share a length, so the string can be read as a sequence of fixed-size tokens, so it becomes a sliding window over tokens comparing count maps.
Pattern: multiset match over a windowed sequence. Target: O(n · L), where L is the word length, down from the O(n · k · L) recount-every-start brute force (k = number of words).
Number of Boomerangs
Count ordered triples where the first point is equidistant from the other two. Fix each pivot, tally squared distances, and add k × (k − 1) for every distance seen k times.
Pattern: count around a pivot, then arithmetic. Target: O(n²) time, O(n) space, down from the O(n³) triple loop.
Minimum Number of Keypresses
Assign 26 letters to 9 keys, up to 3 letters per key, minimising total presses. Count letter frequencies, sort descending, and give the first 9 letters one press, the next 9 two presses, the rest three.
Pattern: frequency tiers + greedy assignment. Target: O(n + 26 log 26) time, O(26) space.
5. Common pitfalls
- Rebuilding the count map every window. In the concatenation problem, the window must slide by one word with incremental updates; rebuilding from scratch turns an acceptable solution into a timeout.
- Starting only at index 0. Because words have length
L, there areLindependent alignments to sweep, starting at offsets0..L-1. Missing this is the most common wrong answer. - Comparing distances with square roots. Compare
dx² + dy²as integers; floats will eventually call two equal distances unequal. - Forgetting the tally resets per pivot. The map is about distances from this pivot, and carrying it over silently merges unrelated counts.
- Using
k choose 2instead ofk × (k − 1). Boomerangs are ordered, so it is permutations, not combinations. A factor-of-two error that passes on symmetric inputs. - Hand-waving the greedy. For the keypress tiers, the exchange argument is two sentences; give it rather than hand-waving "greedy works here."
6. Key takeaways
- Count, then reason about counts. Every problem here replaces pair enumeration with a tally plus arithmetic.
- Equal frequency maps mean permutation, the cheapest possible anagram test, and the basis of window matching.
- Slide incrementally. Add the entrant, remove the leaver; never rebuild the map inside the loop.
kitems at one key givek × (k − 1)ordered pairs. Know whether the problem wants ordered or unordered before you write the formula.- Sorted frequencies drive provable greedy assignments, and the exchange argument is what makes it an answer rather than a guess.
- Why interviewers like it: the brute force is obvious and quadratic or worse, so all the signal is in whether you spot that counting makes the pairs unnecessary.
Order: Substring with Concatenation of All Words → Number of Boomerangs → Minimum Number of Keypresses.