A leaderboard keeps scores in a sorted array; how do you compute a new score's rank and insert it?
answer
- rank is a counting problem
- each bound counts something exact
- decide whether ties count against the player
- the search cost is not the update cost
- moving the tail dominates everything
basics
~20 sTake the upper bound of the score; n minus that index counts the players who strictly beat it, so the rank is one more. That index is also the insertion position, but the insert costs O(n) moves.
solid answer
~50 sWith scores sorted ascending, the upper bound of a new score `s` is the count of entries at or below `s`, so `n - upperBound(s)` players strictly beat it and the competition rank is `n - upperBound(s) + 1`. Choosing upper bound over lower bound is the substantive decision: lower bound counts tied players as beating you, silently inflating everyone's rank in a way no test catches unless someone wrote one for ties. The same index is also where the score belongs to sit after existing equals. The trap is the cost story: the search is O(log n), but placing the element in an array shifts every later entry, so the update is O(n) and the search was never the bottleneck. If a round submits thousands of scores at once, sort the batch and merge it in a single linear pass rather than doing thousands of individual O(n) insertions.
go deeper
Be able to say that the position found by the search is where the score belongs, and that a rank is derived from how many entries sit above it rather than from the index alone.
Explain which bound counts what, and derive the rank formula out loud including the tie case. Expect to be asked what changes when the array is sorted the other way.
Lead with the cost asymmetry: the search is logarithmic, the insert is linear because the tail moves, so batching a round's submissions into one merge is the change that matters.
Own the design split — a read path served from sorted snapshots versus a write path that pays maintenance — and be explicit that tie-breaking is a product rule encoded in the choice of bound.
## Rank is a counting question, and bounds are counters The useful reframe: the two boundary searches are not just position finders, they are exact counters over a sorted array. - `lowerBound(s)` = the number of scores **strictly below** `s`. - `upperBound(s)` = the number of scores **at or below** `s`. Both are exact whether or not `s` already appears. From there, with `n` entries sorted ascending: - Players scoring **strictly more** than `s`: `n - upperBound(s)`. - Competition rank of `s` (1 for the best, ties sharing a rank): `n - upperBound(s) + 1`. Worked example. Scores `[120, 340, 340, 500, 910]`, `n = 5`, and a new submission of `340`. - `upperBound(340) = 3` (index 3 holds 500, the first strictly greater score). - Strictly better players: `5 - 3 = 2` (500 and 910). - Rank: `3`. The two existing 340s share rank 3 as well, which is what a competition ranking means. Use `lowerBound(340) = 1` by mistake and you get `5 - 1 + 1 = 5`: rank 5 for a score that ties for third. The bug is not a crash and not an exception; it is a plausible number that is wrong only when ties exist — which on a leaderboard with a round-number scoring system is most of the time. This is the concrete reason the `>=` versus `>` distinction is worth being pedantic about. ## The insertion position, and where ties go The same two bounds answer "where does this row go?" and they answer it differently on purpose: - Insert at `lowerBound(s)` → the new entry goes **before** all existing equal scores. - Insert at `upperBound(s)` → the new entry goes **after** all existing equal scores. On a leaderboard the second is normally what you want: among equal scores, whoever got there first keeps the better position, so a newcomer joins the back of the tied group. That is a product rule, not an implementation detail, and the choice of bound is where it gets encoded. Writing it down in the code review as "upper bound, because ties break toward the earlier submission" is worth more than a comment saying "binary search". ## The cost trap Here is the answer that separates candidates. Asked for the cost of "find the rank and insert the score", a weak answer is "O(log n) — it's a binary search". The search is O(log n). The **insert** is not. Placing an element at index `k` in a contiguous array means moving every element from `k` to the end one slot along: O(n − k), and O(n) in the worst case. Locating the seat is logarithmic; seating the guest is linear, and the linear term dominates. So the honest complexity of one submission is: | Step | Cost | | --- | --- | | Find the rank / position | O(log n) | | Shift the tail and store | O(n) worst case | | Whole update | **O(n)** | The practical consequence: at a thousand entries this is invisible; at a few million and a high submission rate, the shifting is the entire CPU profile and the p99 of a "read your rank" endpoint that also writes will be dominated by memory movement, not by search. Optimising the search at that point is optimising 20 comparisons out of a million moves. ## What actually helps Once you have named the real cost, the fixes are about **write strategy**, not about a cleverer search: 1. **Batch and merge.** A tournament round produces `m` scores at once. Sorting that batch and merging it into the existing array in one pass is O(m log m + n + m), versus `m` separate insertions at O(n) each — a linear-versus-quadratic difference in `m`. This is by far the highest-leverage change when submissions arrive in bursts. 2. **Bound what you keep.** Most leaderboards only display a top-K window. Maintaining `K` entries instead of `n` makes the shift cost trivially small and bounded, and every rank outside the window can be reported approximately or not at all. 3. **Separate the read path from the write path.** Rank *queries* against a snapshot are pure boundary searches — O(log n), no shifting, and safely served from a read-only copy. Only the writes need the expensive maintenance, so the two should not share a cost budget. ## Preconditions worth stating out loud The boundary search requires random access and a genuinely sorted array under the same comparison. Two things break the invariant quietly: mutating scores in place (a player's score updated without re-positioning the row) and a comparison that disagrees with the stored order, for instance sorting on the raw score but computing bounds on a rounded one. Either produces a rank that is wrong and stable, which is the worst failure mode to debug. If instead the array is sorted **descending** — the display order for a leaderboard — the predicate flips: the first index whose score is strictly less than `s` counts the players at or above `s`, and the rank is that index plus one. Getting the sort direction and the strictness to agree is the single most error-prone line in this whole feature; write out one example with a tie before shipping it.
- Why upper bound rather than lower bound for a competition rank?The upper bound counts entries at or below the score, so subtracting it from n leaves exactly the strictly-better players. The lower bound counts only entries strictly below, so using it treats every tied player as beating this one and inflates the rank. The two agree exactly when no ties exist, which is why the bug survives testing.
- The array is sorted descending for display instead; what changes?The predicate flips strictness and direction: you want the first index whose score is strictly less than the new score, which counts the players at or above it, and the rank is that index plus one. The search structure is identical — a monotone predicate over a sorted range — but sort direction and strictness must be reasoned about together, with a tied example checked by hand.
- A round submits ten thousand scores at once; what do you do differently?Sort the batch and merge it into the existing array in a single pass: O(m log m + n + m) instead of m individual insertions at O(n) each, which is quadratic in m. The boundary search does not appear in the fast path at all — the win comes from doing the tail movement once rather than ten thousand times.
- How do you serve rank queries without paying the insertion cost?Split the paths. A rank query against an already-sorted snapshot is a pure boundary search: O(log n), no writes, safe to serve from a read-only copy that is republished periodically. Only submissions pay maintenance cost. Conflating the two budgets is what makes a read endpoint look slow when the real expense is on the write side.
saying these in an interview costs you the question
- Says the whole update is O(log n) because the search is
- Uses the lower bound and counts tied players as beating the newcomer
- Reports the raw index as the rank without accounting for sort direction
- Re-sorts the entire array after every submitted score
- Assumes ties must be broken before a rank can be computed
- Optimises the comparison count while ignoring the tail shifting