Deciding whether O(n²) can be improved
“Your first solution is O(n²). How would you determine whether it can be improved?”
What this tests
- Whether the candidate has a repeatable optimization procedure rather than a bag of tricks.
- Whether they can locate the bottleneck (the inner loop) and characterize what it computes.
- Whether they know lower-bound reasoning: some problems are genuinely quadratic in output size.
- Whether they reason about redundant work: recomputation, repeated scans, repeated lookups.
Strong answer
A strong candidate starts by asking two things: what is the lower bound and where is the redundant work. The lower bound is usually output size or the need to read the input once — if the problem asks for all pairs, O(n^2) is optimal and the discussion is over. Otherwise, at least O(n) is needed to read the input, so the gap between n and n^2 is the room for improvement.
Then they open the inner loop and name what it does. Nearly every O(n^2) inner loop is one of a few things: searching for a value (replace with a Hash Map or, on sorted data, Binary Search), recomputing a sum or count over a range (replace with Prefix Sum or a maintained running window), looking for the nearest greater/smaller element (replace with a Monotonic Stack), or re-solving an overlapping subproblem (replace with Memoization (Top-Down DP)). Each replacement turns an O(n) inner step into O(1) or O(log n).
They also check whether order can be exploited: sorting costs O(n log n) once and often enables two pointers or binary search afterward. And they check for wasted recomputation between adjacent iterations — if iteration i+1 recomputes most of what iteration i computed, a sliding window or incremental update is available.
Finally they verify the new complexity honestly, including the cost of the new structure (hash map space, sort time), and confirm that the constraint (n ≤ 10^5 implies roughly 10^5 log 10^5 ≈ 1.7 × 10^6 operations) is actually satisfied.
Green flags · Red flags
- Asks what the output size is before assuming a speedup exists.
- Isolates the inner loop and describes it as a *question* ("for each
i, does there exist ajsuch that…"). - Lists the standard replacements: hash map for lookup, prefix sums for range sums, monotonic stack for nearest greater, memo for overlapping subproblems.
- Considers whether sorting is allowed and whether it unlocks two pointers.
- Recomputes the complexity after the change including the new structure's cost.
- Mentions when
O(n^2)is acceptable (n ≤ 3000) and is not worth the complexity of optimizing.
- Says "use a hash map" without saying which lookup it replaces.
- Claims a problem can always be made linear.
- Ignores the space cost of the new structure.
- Cannot explain why the brute force is
O(n^2)in the first place. - Proposes micro-optimizations (fewer allocations, early breaks) as the answer to an asymptotic question.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
a[i] to its left. What replaces it?O(n log n) with sorting and O(n) with a hash map?