</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Three uses of a frequency map: match a multiset, count around a pivot, tier by frequency

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 is the number of ordered pairs you can pick from k items.

🔓 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)?

Counting ordered pairs around each pivot, answer 2

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 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, and 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.
  • 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

  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.

Substring with Concatenation of All Words

Core idea: Every word has the same length L, so stop thinking in characters and think in L-sized chunks. A valid match is a run of exactly len(words) chunks whose multiset equals Counter(words). Slide a window of chunks across the string, keeping a running Counter. When a word overflows its needed count, shrink from the left until it is legal again; when a word is unknown, restart past it. Matches start on L-aligned boundaries, so you need L passes, one per phase offset 0 … L-1.


Problem, rephrased

You run a log-analysis console. Every request fingerprint is a fixed-width token of exactly L characters, and traces are stored as one long string of tokens run together. You're given the trace s and an array words of required tokens, all of length L, duplicates allowed (a token can be required twice).

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.