Every interview problem comes with limits: 1 ≤ n ≤ 10⁵, values up to 10⁹, sometimes a memory limit, sometimes "the
data arrives as a stream". Most candidates skim them. Strong candidates read them first, because the limits
quietly tell you which algorithms are allowed and which are doomed.
This lesson gives you a table that converts n into an affordable complexity, then takes one problem, find the k-th smallest value, through four different best solutions as the constraints change. Every solution is written, tested against a brute force, and costed.
1. The budget: about a second, in rough operations
Coding platforms usually allow around 1 to 2 seconds. Interviewers have the same instinct: "would this finish quickly for the largest input?" So estimate:
- Python manages roughly 10⁷ simple operations per second (an addition, a comparison, a dict lookup).
- Compiled languages manage roughly 10⁸ to 10⁹. That's why the same limits feel tighter in Python.
These are orders of magnitude, not benchmarks. They're accurate enough to rule algorithms in or out, which is all we need.
| Largest n | Affordable in Python | What it usually means |
|---|---|---|
| ≤ 10 | O(n!) | try every ordering (permutations) |
| ≤ 20 | O(2ⁿ · n) | try every subset (backtracking, bitmasks) |
| ≤ 500 | O(n³) | three nested loops, small dynamic programming tables |
| ≤ 5,000 | O(n²) | every pair; 2-D dynamic programming |
| ≤ 10⁶ | O(n log n) or O(n) | sort, hash maps, two pointers, sliding windows, heaps |
| ≥ 10⁹ | O(log n) or O(1) | binary search, maths; you can't even read n items |
Read it backwards in interviews: "n is up to 10⁵, so O(n²) is 10¹⁰, too slow; I'm aiming for O(n log n) or better." That one sentence tells the interviewer you know where you're heading before you've written anything.
Quick check
A problem says n ≤ 18. What does that strongly suggest?
Show the answer
B. An exponential approach over subsets, around 2¹⁸ ≈ 260,000 states, is affordable and probably intended — Small limits like 18 or 20 are a hint: they're chosen so that 2ⁿ fits in the budget.
2. The other constraints
n is only one number. The others matter as much:
| Constraint | Question it answers | What it can unlock or rule out |
|---|---|---|
| Value range | How big can the numbers be? | Small range → index by value (counting) instead of hashing or sorting |
| Sorted input? | Is order given for free? | Two pointers, binary search, no sort needed |
| Distinct values? | Can duplicates exist? | Simpler logic, fewer edge cases |
| Number of queries q | One answer or many? | Many queries → precompute once (lesson 0.2) |
| Memory limit | How much can I store? | Can rule out a hash set even when time allows it |
| Stream or in memory? | Can I see all the data at once? | Streams need small, incremental state (heaps, counters) |
| Read-only input? | May I modify it? | Rules out sorting or marking in place |
Memory in Python is bigger than you think. A list of ints costs about 36 bytes per value (an 8-byte pointer plus
a 28-byte int object). A NumPy int64 array or array('q') costs 8 bytes. A 256 MB limit holds roughly 7 million
Python ints, not 32 million. Lesson 0.4 goes deeper.
import sys
from array import array
n = 100_000
as_list = list(range(1_000_000, 1_000_000 + n)) # large ints are separate objects
per_value_list = (sys.getsizeof(as_list) + sum(sys.getsizeof(x) for x in as_list)) / n
as_array = array("q", as_list) # 8-byte signed integers, packed
per_value_array = sys.getsizeof(as_array) / n
print(f"list: ~{per_value_list:.0f} bytes per value, array('q'): ~{per_value_array:.1f} bytes per value")
assert per_value_list > 30 and per_value_array < 9
3. One problem, four best answers
Problem. Given n integers and an integer k (1-based), return the k-th smallest value.
For [7, 2, 9, 4, 1] and k = 2, the answer is 2.
ML context. Picking a threshold so that the bottom 1% of scores are flagged; finding the median latency; choosing the k-th nearest neighbour's distance; selecting top-k scores from millions of candidates (the same problem with the order flipped).
Constraint set A: n ≤ 10⁵, one query. Start with brute force.
The simplest correct answer: sort, then index.
def kth_smallest_sort(nums, k):
return sorted(nums)[k - 1] # O(n log n) time, O(n) for the sorted copy
assert kth_smallest_sort([7, 2, 9, 4, 1], 2) == 2
assert kth_smallest_sort([5], 1) == 5
assert kth_smallest_sort([3, 3, 1], 3) == 3
print("sort works")
- Time: O(n log n). At n = 10⁵: about 1.7 × 10⁶ comparisons, instant.
- Space: O(n) for the sorted copy.
- Verdict: under these constraints, this is the right answer. Don't optimise what doesn't need it. Say so: "sort is O(n log n), fine for 10⁵; if n or memory grew I'd switch."
Constraint set B: the data is a stream, k is small (say 10)
Now we can't sort: the values arrive one at a time and there may be billions. What do we actually need to remember? Only the k smallest seen so far. Everything larger than the current k-th smallest can be forgotten.
Keep those k values in a max-heap (the largest of the k on top). For each new value: if it's smaller than the top,
it replaces the top. Python's heapq is a min-heap, so store negated values.
import heapq
def kth_smallest_stream(stream, k):
heap = [] # max-heap of the k smallest, stored as negatives
for x in stream:
if len(heap) < k:
heapq.heappush(heap, -x)
elif x < -heap[0]: # smaller than the largest of our k
heapq.heapreplace(heap, -x) # pop the top and push x: O(log k)
return -heap[0]
assert kth_smallest_stream(iter([7, 2, 9, 4, 1]), 2) == 2
assert kth_smallest_stream(iter(range(1_000_000, 0, -1)), 3) == 3
print("streaming heap works")
- Time: O(n log k). With k = 10, log k ≈ 3.3, so this is close to linear.
- Space: O(k), independent of n. That's the property the stream constraint demanded.
- What changed and why: the constraint "can't hold all the data" removed sorting; "k is small" made a size-k heap cheap.
Constraint set C: n up to 10⁷, all in memory, any k
Sorting 10⁷ values in Python is slow (seconds), and a heap of size k is no help when k = n/2 (the median). We need the k-th value without fully sorting.
First principles: sorting puts every value in place, but we need only one position. Quickselect partitions around a pivot like quicksort, then recurses into only the side that contains position k. Each step discards a large fraction of the data on average.
import random
def kth_smallest_quickselect(nums, k):
"""Average O(n), worst O(n²). Works on a copy; three-way partition handles duplicates."""
items = list(nums)
target = k - 1 # 0-based position we want
rng = random.Random(42)
while True:
pivot = items[rng.randrange(len(items))] # random pivot avoids bad inputs
lows = [x for x in items if x < pivot]
pivots = [x for x in items if x == pivot]
highs = [x for x in items if x > pivot]
if target < len(lows):
items = lows # answer is among the smaller values
elif target < len(lows) + len(pivots):
return pivot # answer equals the pivot
else:
target -= len(lows) + len(pivots) # skip the smaller values and pivots
items = highs
assert kth_smallest_quickselect([7, 2, 9, 4, 1], 2) == 2
assert kth_smallest_quickselect([5, 5, 5, 5], 3) == 5
assert kth_smallest_quickselect(list(range(100, 0, -1)), 50) == 50
print("quickselect works")
- Time: on average each round keeps about half, so n + n/2 + n/4 + … ≈ 2n: O(n) average. A terrible pivot every time gives O(n²) worst case; a random pivot makes that vanishingly unlikely.
- Space: this readable version builds new lists, O(n) extra. The classic in-place version (partitioning inside the array) uses O(1) extra; we'll write it in module 05.
Constraint set D: values are small, in 0..1000
A constraint on values unlocks a different idea entirely: if values are small integers, count how many times each appears, then walk the counts until you've passed k values. No comparisons between values at all.
def kth_smallest_counting(nums, k, max_value):
counts = [0] * (max_value + 1) # O(V) memory
for x in nums:
counts[x] += 1 # O(n)
seen = 0
for value, c in enumerate(counts): # O(V)
seen += c
if seen >= k:
return value
raise ValueError("k is larger than the number of values")
assert kth_smallest_counting([7, 2, 9, 4, 1], 2, max_value=10) == 2
assert kth_smallest_counting([0, 0, 1000], 3, max_value=1000) == 1000
print("counting works")
- Time: O(n + V), where V is the value range. Linear in n and no worst case.
- Space: O(V). With V = 1,000 that's nothing; with V = 10⁹ it's impossible. The constraint makes or breaks it.
Constraint set E: many queries for different k on the same data
Sort once (O(n log n)), then answer each query in O(1) by indexing. Precomputation wins when the same data is asked about many times, exactly as with prefix sums in lesson 0.2.
4. Cross-check everything against the brute force
Every optimised version must agree with the simple sort on random inputs, including duplicates, k = 1 and k = n.
import heapq
import random
def by_sort(nums, k):
return sorted(nums)[k - 1]
def by_heap(nums, k):
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, -x)
elif x < -heap[0]:
heapq.heapreplace(heap, -x)
return -heap[0]
def by_quickselect(nums, k):
items, target, rng = list(nums), k - 1, random.Random(7)
while True:
p = items[rng.randrange(len(items))]
lows = [x for x in items if x < p]
eq = sum(1 for x in items if x == p)
if target < len(lows):
items = lows
elif target < len(lows) + eq:
return p
else:
target -= len(lows) + eq
items = [x for x in items if x > p]
def by_counting(nums, k, max_value):
counts = [0] * (max_value + 1)
for x in nums:
counts[x] += 1
seen = 0
for value, c in enumerate(counts):
seen += c
if seen >= k:
return value
rng = random.Random(3)
for _ in range(500):
n = rng.randint(1, 40)
nums = [rng.randint(0, 50) for _ in range(n)]
k = rng.randint(1, n)
want = by_sort(nums, k)
assert by_heap(nums, k) == want
assert by_quickselect(nums, k) == want
assert by_counting(nums, k, max_value=50) == want
print("all four agree on 500 random cases")
5. The comparison, in numbers
| Constraints | Best approach | Time | Extra space | Why it wins here |
|---|---|---|---|---|
| n ≤ 10⁵, one query | Sort and index | O(n log n) | O(n) | Simplest, fast enough |
| Stream, small k | Max-heap of size k | O(n log k) | O(k) | Memory independent of n |
| Large n in memory, any k | Quickselect | O(n) average | O(1) in place | Avoids sorting everything |
| Small value range V | Counting | O(n + V) | O(V) | No comparisons, no worst case |
| Many queries, fixed data | Sort once | O(n log n + q) | O(n) | Precomputation pays off |
| Data across many machines | Approximate quantile sketch | ≈ O(n) | small | Exact answers need moving all data |
Notice that no single algorithm is "the best". Each constraint either removes an option (a stream removes sorting; a huge V removes counting) or unlocks one (small k unlocks a tiny heap; small V unlocks counting).
Quick check
You must find the median of 10⁹ values arriving as a stream, using only a few MB of memory. Which statement is right?
Show the answer
C. Exact answers need memory proportional to n in the worst case; with a few MB you'd use an approximate quantile sketch and state the error bound — The median of a stream needs to remember about half the values exactly. Under a tight memory limit, the honest answer is an approximation with a known error.
6. A constraint-reading checklist
Before writing code, run through these and say the conclusions out loud:
- n (and m, q, k): which complexity class fits the budget?
- Value range: can I index by value? Do I need to worry about overflow (in other languages)?
- Order and uniqueness: sorted? distinct? that's free structure to exploit.
- Memory: can I afford O(n) extra? In Python, at ~36 bytes per value?
- Access pattern: stream or random access? read-only or modifiable?
- Repetition: one answer, or many queries on the same data?
Quick check
Values are integers in 0..100 and n is up to 10⁷. Which approach to the k-th smallest is best, and why?
Show the answer
A. Counting into 101 buckets: O(n + 101) time and tiny memory, with no worst case — A tiny value range unlocks counting, which is linear, deterministic and uses almost no memory.
Check yourself
- Roughly how many simple operations per second can Python do, and why does that matter?
- What complexity fits n ≤ 5,000? n ≤ 10⁶? n ≤ 20?
- Which constraints besides n can change the algorithm? Give an example of each unlocking or removing an option.
- Why does a stream rule out sorting for the k-th smallest, and what replaces it?
- When does counting beat every comparison-based method, and when is it impossible?
- Why is quickselect O(n) on average but O(n²) in the worst case?
Answers
- About 10⁷; it converts the limit on n into an affordable complexity.
- O(n²); O(n log n) or O(n); O(2ⁿ · n).
- Value range (small → counting), sortedness (→ two pointers, no sort), memory (rules out large hash sets), streaming (rules out sorting), query count (many → precompute), read-only (rules out in-place tricks).
- You can't hold or reorder all values; keep only the k smallest in a max-heap of size k: O(n log k) time, O(k) space.
- When values lie in a small range V: O(n + V) with no worst case. Impossible when V is huge (like 10⁹).
- On average each partition discards about half the data (n + n/2 + … ≈ 2n); with consistently bad pivots it discards only one element per round, giving about n²/2.