10 million booking times fall in only 1,440 minute-of-day slots — what does that value bound buy you?
answer
- Two numbers in the block, not one
- The range of the values, not just the count
- You can index by value instead of comparing
- Cost has both an n term and a k term
- The classic lower bound covers comparisons only
basics
~20 sA bounded value range is a second constraint axis: with only 1,440 distinct values you can tally occurrences per value instead of comparing elements, costing about O(n + k) time and O(k) space rather than n log n.
solid answer
~50 sTwo numbers matter in a constraint block, not one: the count n and the range of values k. Here n is 10^7 but k is only 1,440, so ordering the data by comparison would cost about 10^7 × 24 ≈ 2.4 × 10^8 operations, while a single pass that tallies how many bookings land in each slot is about 10^7 + 1,440 — linear, and with a tiny fixed table. That escapes the Ω(n log n) comparison lower bound legitimately, because the bound only constrains algorithms whose only tool is comparing pairs; tallying by value is not one of them. The cue has a hard precondition, though: it pays only while k stays small. The same trick against values spread over 10^9 would need a table of a billion slots, so I check k before reaching for it.
go deeper
Notice that a stated range on the values is a hint, not filler. Recall that when values fall into a small fixed set of slots you can count occurrences per slot in a single pass.
Explain the O(n + k) formula and why the classic n log n lower bound does not apply — it constrains algorithms that only compare pairs, and indexing by value is not comparing.
Show judgment about k: state the memory cost alongside the time cost, name the k at which the approach stops paying, and treat a stated range as an assumption that must survive a schema change.
Own the risk that a whole design rests on a value range someone may widen later. Decide whether that range is contractually enforced and what the fallback path costs if it is relaxed.
## The constraint block has more than one number Candidates read the size bound and stop. A constraint block usually states two independent things: **how many items there are (n)** and **what values those items may take (a range of size k)**. The first tells you the time budget. The second sometimes tells you that you can leave the comparison world entirely. Here n = 10^7 and k = 1,440. Those two numbers are four orders of magnitude apart, and that gap is the whole hint. ## Why the value bound changes the achievable class The famous Ω(n log n) lower bound is a statement about **comparison-based** algorithms — those whose only way to learn about the data is to ask "is a before b?". Such an algorithm is a decision tree whose leaves must cover all n! possible orderings, so its height is at least log2(n!) ≈ n log n. That argument is airtight, and it is also narrow: it says nothing about an algorithm that uses a value *as an address*. With k known and small, you never have to compare. You allocate k counters, make one pass incrementing the counter for each item's value, and you now know the full distribution — and, by walking the counters in order, the sorted order too. The cost is O(n + k) time and O(k) extra space. At n = 10^7, k = 1,440 that is about 10^7 operations against roughly 2.4 × 10^8 for a comparison ordering: not a different constant, a different class. (The mechanics of that family of algorithms — how a stable counting pass computes output positions from a prefix sum, how digit-wise passes extend it to larger ranges — belong to the non-comparison sorting material. What matters at the estimate level is recognising the cue and knowing the cost formula.) ## Recognising the cue in the wild Value-range hints show up phrased in ways that do not mention algorithms at all: - "times are minute-of-day" — k = 1,440 - "room numbers are between 1 and 10,000" — k = 10^4 - "a rating from 1 to 5" — k = 5 - "all values are distinct and lie in 1..n" — k = n, and the array can be its own index space - "lowercase letters only" — k = 26 Each of these licenses tallying, bucketing, or direct indexing, and each turns a sort-shaped problem into a single pass. The tell is that the author bothered to state a range at all. If any value were allowed, why say it? ## The precondition, and the failure it prevents The cost is O(n + k), and both terms are real. The approach is a win only when **k is comparable to n or smaller**. Some concrete consequences: - n = 10^7, k = 1,440 → about 10^7 work, a table of 1,440 counters. Excellent. - n = 1,000, k = 10^9 → about 10^9 work and a billion-slot table for a thousand items. Absurd; sort them. - Values are floating-point durations with no stated bound → there is no k. The cue does not apply. - Values are 64-bit identifiers → k is astronomically larger than n; direct tallying is out, though hashing by value remains available for grouping (just not for ordering). So the honest rule is not "bounded values mean tally" but "compare k against n, and remember k costs memory as well as time". ## Space is a constraint too A memory ceiling is part of the constraint block just as much as a time limit, and this technique trades one for the other explicitly: it buys a factor of log n in time by spending O(k) in space. On a fleet where each process is capped, a k of 10^8 counters may be infeasible even though the arithmetic fits the time budget. Say the space cost out loud when you propose it; a candidate who quotes only the time half has not finished the analysis. ## Mainstream reality Worth knowing that the general-purpose ordering routines shipped by mainstream platforms are comparison-based hybrids — that is the right default when nothing is known about the values. The non-comparison approaches are specialist tools you reach for *because* the constraint told you something extra. That is the mental model to carry: the value range is information, and information is what buys you a lower complexity class. ## How to say it "n is 10^7, but the values only span 1,440 slots, so I do not need to compare anything — one pass tallying per slot is O(n + k), roughly linear here, and it costs me a 1,440-entry table. If the range were wide I would fall back to an n log n ordering." Stating the precondition alongside the trick is what makes the answer senior rather than a memorised trivia line.
- Doesn't that violate the Ω(n log n) lower bound for sorting?No, because the bound is scoped to comparison-based algorithms. Its proof counts the leaves of a decision tree whose only operation is asking whether one element precedes another; an algorithm that uses a value directly as an index is outside that model. The bound is not a law about ordering data, it is a law about ordering data blindly.
- The same field is later widened to arbitrary timestamps in seconds since an epoch. What changes?k explodes from 1,440 to something around 10^9, so the tally table becomes the dominant cost in both time and space and the approach dies. Either recover a small k by bucketing at a coarser granularity — second-of-day, or day-of-year — or fall back to an n log n ordering. The lesson is that the design was resting on a stated range, which makes that range a documented assumption.
- How do you check whether the value bound is worth using before you write anything?Compare k with n and with your memory ceiling. If k is at or below n, the O(n + k) pass wins and the table is affordable. If k is orders of magnitude above n, the k term dominates and you sort instead. And if no range is stated at all, treat that silence as k being unbounded rather than assuming a convenient one.
Sorting mail by comparing envelopes two at a time is one job; having 1,440 labelled pigeonholes on the wall is another. The labels are information the comparer never had.
saying these in an interview costs you the question
- Claims n log n is a universal lower bound for all sorting
- Reaches for a per-value tally when values span 10^9
- Quotes the time cost and omits the O(k) space
- Treats the count as the only constraint that matters
- Assumes a stated range without checking values are discrete