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 people in a room share a birthday, you do not compare everyone with everyone; you count birthdays and do arithmetic on the counts. Fifty comparisons become 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 k points at one distance contribute exactly k × (k − 1) ordered pairs. That formula is the number of ways to pick an ordered pair from k items, a fact combinatorics settled long before anyone needed it in an interview.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: 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?" — with the refinement that you should compare incrementally, adding the entering item and removing the leaving one, rather than rebuilding the map 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 matching, plagiarism detection and shingling all compare multisets rather than sequences.
• Spatial indexing and clustering. "How many points are equidistant from this one" is the naive core of nearest-neighbour work; production systems replace the tally with a k-d tree, but the counting instinct is the same.
• Keyboard and input design. Minimum Number of Keypresses is literally how T9 and modern keypad layouts were optimised — frequent letters get the shortest press sequence.
• Compression. Huffman coding is this exact greedy: the most frequent symbol gets the shortest code. If you can explain the keypress problem, you can explain Huffman.
• Rate limiting and abuse scoring. Counting events per key and acting on the tiers, rather than inspecting each event pair, is the difference between a service that scales and one that does not.

3. A 30-second worked example (count around a pivot)

Points [(0,0), (1,0), (2,0)]. How many ordered triples (i, j, k) have dist(i,j) == dist(i,k)?

pivot (0,0):  distances² to others → {1: 1, 4: 1}
              no distance has k ≥ 2 → 0 pairs

pivot (1,0):  distances² to others → {1: 2}          ← both neighbours are 1 away
              k = 2 → 2 × 1 = 2 ordered pairs

pivot (2,0):  distances² to others → {4: 1, 1: 1}
              → 0 pairs
                                          answer = 2

Note two things: the tally is rebuilt per pivot (so the map is cleared each time), and distances are compared squared — 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 — then it is 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, not O(n · m).

▶ 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 are L independent alignments to sweep — starting at offsets 0..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 — carrying it over silently merges unrelated counts.
• Using k choose 2 instead of k × (k − 1). Boomerangs are ordered, so it is permutations, not combinations — a factor-of-two error that passes on symmetric inputs.
• Assuming the greedy needs proof by exhaustion. For the keypress tiers, the exchange argument is two sentences; give it rather than hand-waving "greedy works here."

6. Key takeaways

1. Count, then reason about counts. Every problem here replaces pair enumeration with a tally plus arithmetic.
2. Equal frequency maps mean permutation — the cheapest possible anagram test, and the basis of window matching.
3. Slide incrementally. Add the entrant, remove the leaver; never rebuild the map inside the loop.
4. k items at one key give k × (k − 1) ordered pairs — know whether the problem wants ordered or unordered before you write the formula.
5. Sorted frequencies drive provable greedy assignments, and the exchange argument is what makes it an answer rather than a guess.
6. 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.