Custom Keys and Restricted Ops

What is this?

An election is being counted. Candidates are ranked by how many first-preference votes they received; ties are broken by second preferences, then third, and if two candidates are identical all the way down, alphabetically. Written as prose it sounds like a page of conditionals. Written as a key — the vector of vote counts by position, with the name on the end — it is one sort call.

The last problem in the chapter takes the opposite position: you may not define a comparison at all. The only thing you can do is flip a prefix of the stack.

💡 Fun fact: in Rank Teams by Votes the key is a vector of counts, one entry per ranking position, and comparing two vectors lexicographically reproduces the entire tie-break chain automatically. It is the same principle behind how library catalogues and dictionaries order entries: make the comparison positional, and arbitrarily deep tie-breaking costs nothing extra to express.

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

The one-line idea: turn the rule into a key and let an ordinary sort apply it. When the rule cannot be turned into a key — because the only legal operation is a prefix reversal — build the order one permanently placed element at a time.

1. Count vectors as keys

For each candidate, build an array where index i holds how many voters placed them i-th:

votes = ["ABC", "ACB", "ABC", "ACB", "ACB"]

        pos0  pos1  pos2
   A      5     0     0
   B      0     2     3
   C      0     3     2

key(x) = (-count[0], -count[1], -count[2], x)      ← negate to rank high counts first
sorted → A, C, B

C beats B because they tie at position 0 and C has more second-place votes. The name comes last in the tuple so that identical vectors fall back to alphabetical order — and it is not negated, because alphabetical means ascending while the counts mean descending. Mixing directions inside one key is exactly what the negation trick is for; reversing the whole sort would flip the name ordering too.

2. Derived indices as buckets

Every cell on the same matrix diagonal satisfies r − c = constant. So bucket cells by that value, sort each bucket, and write them back in order:

matrix          r-c for each cell        buckets (cells along each diagonal)
3 3 1 1          0 -1 -2 -3              -3: [1]
2 2 1 2          1  0 -1 -2              -2: [1,2]    → sorted → [1,2]
1 1 1 2          2  1  0 -1              -1: [3,1,2]  → sorted → [1,2,3]
                                          0: [3,2,1]  → sorted → [1,2,3]
                                          1: [2,1]    → sorted → [1,2]
                                          2: [1]

The two-dimensional problem never needed a two-dimensional algorithm — only the right index.

3. Building order with one move

Pancake sorting places the largest unplaced value each round, in two flips:

[3, 2, 4, 1]        target: place 4 at the end
flip(3)  → [4, 2, 3, 1]     bring 4 to the front
flip(4)  → [1, 3, 2, 4]     flip it down to its final slot ✓

[1, 3, 2 | 4]       target: place 3
flip(2)  → [3, 1, 2 | 4]
flip(3)  → [2, 1, 3 | 4] ✓

[2, 1 | 3, 4]       target: place 2
                    2 is already at the front — skip the first flip
flip(2)  → [1, 2 | 3, 4] ✓  sorted

Two flips per element gives 2n operations, comfortably inside the 10n the problem allows. The invariant is that the sorted suffix never moves again — every flip is confined to the shrinking prefix.

4. Where you'll actually meet this

• Ranking and leaderboards. Multi-criteria ordering with deterministic tie-breaks, where an inconsistent comparator causes real bugs.
• Query engines. ORDER BY with mixed directions is the tuple key with per-component negation.
• Image processing. Diagonal, anti-diagonal and band operations all bucket by a derived index.
• Version and identifier ordering. Semantic versions sort as tuples of integers, not as strings — the classic reason 1.10.0 sorts before 1.9.0 when someone forgets.
• Constrained manipulation. Robotics and genome-rearrangement problems where only a restricted operation is available.

5. Problems in this chapter

▶ Rank Teams by Votes

Rank candidates by positional vote counts with alphabetical tie-breaking. Build a count vector per candidate and sort on (-counts…, name).
Pattern: count-vector key. Target: O(n·m + m log m · m) for m candidates and n votes.

▶ Sort the Matrix Diagonally

Sort each top-left-to-bottom-right diagonal independently. Bucket cells by r − c, sort each bucket, write back.
Pattern: derived bucket index. Target: O(mn log(min(m,n))) time, O(mn) space.

▶ Pancake Sorting

Sort using only prefix reversals, within 10n flips. Place the largest unplaced value each round with at most two flips.
Pattern: greedy placement under a restricted operation. Target: at most 2n flips, O(n²) time.

6. Common pitfalls 🚫

• Reversing the whole sort instead of negating one component. That flips the alphabetical tie-break as well and produces a subtly wrong ranking.
• Comparing strings when you mean numbers. Count vectors must be numeric; "10" < "9" lexicographically.
• Forgetting the final tie-break. Two candidates with identical vectors need a deterministic order, or results vary between runs.
• Allocating a full matrix of buckets. Index by r − c offset into a dictionary; most diagonals are short.
• Flipping the already-placed suffix. Every flip must be confined to the unsorted prefix, or you undo finished work.
• Flipping when the element is already in place. Check first — the problem counts flips, and unnecessary ones can push you over the limit on the margin.
• Sorting when bucketing would do. With bounded values, counting is O(n) and worth mentioning even if you then use sort().

7. Key takeaways

1. Design the key and the sort becomes trivial. That design is the problem.
2. Tuples express arbitrary tie-break chains, and per-component negation handles mixed directions.
3. A derived index is a bucket. r − c turns diagonals into independent one-dimensional sorts.
4. When comparison is unavailable, place elements permanently — one at a time, from the extreme inward.
5. Protect the finished region. Restricted-operation sorts depend on never disturbing what is already placed.
6. Know when not to sort. Bounded values mean counting; top-k means a heap.
7. Why interviewers like it: anyone can call sort(). Translating a messy specification into a comparator that is consistent and total is the actual skill being measured.

Order: Rank Teams by Votes → Sort the Matrix Diagonally → Pancake Sorting.