VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 00: The method and Big-O

Lesson 0.3 of 6 in this moduleFree

What the constraints tell you about n

Turn the limits in a problem statement into the complexity you can afford, then watch one problem (the k-th smallest value) change its best solution four times as n, k, the value range, memory and the number of queries change.

about 15 min 6 Python examples 3 quick checks

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.

a ladder from the limit on n to the affordable complexity: n ≤ 10 allows O(n!), n ≤ 20 O(2ⁿ·n), n ≤ 500 O(n³), n ≤ 5,000 O(n²), n ≤ 10⁶ O(n log n) or O(n), n ≥ 10⁹ O(log n) or O(1).
Diagram— a ladder from the limit on n to the affordable complexity: n ≤ 10 allows O(n!), n ≤ 20 O(2ⁿ·n), n ≤ 500 O(n³), n ≤ 5,000 O(n²), n ≤ 10⁶ O(n log n) or O(n), n ≥ 10⁹ O(log n) or O(1).
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?

  1. An O(n log n) sort is expected
  2. An exponential approach over subsets, around 2¹⁸ ≈ 260,000 states, is affordable and probably intended
  3. The problem is impossible
  4. You must use O(1) memory
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
with 256 MB, about 7 million integers fit in a Python list, about 32 million in an 8-byte typed array, about 256 million as 1-byte values and about 2 billion as bits.
Chart— with 256 MB, about 7 million integers fit in a Python list, about 32 million in an 8-byte typed array, about 256 million as 1-byte values and about 2 billion as bits.

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.

python
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).

a decision map for the k-th smallest value: sort for small n, a heap of size k for streams with small k, quickselect for large in-memory arrays, counting for small value ranges, sort once for many queries, and approximate sketches across machines.
Diagram— a decision map for the k-th smallest value: sort for small n, a heap of size k for streams with small k, quickselect for large in-memory arrays, counting for small value ranges, sort once for many queries, and approximate sketches across machines.

Constraint set A: n ≤ 10⁵, one query. Start with brute force.

The simplest correct answer: sort, then index.

python
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.

python
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.

python
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.

python
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.

python
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

at n = 10⁶ and k = 10, rough operation counts: sorting about 2 × 10⁷, a size-k heap about 3.3 × 10⁶, quickselect about 2 × 10⁶ on average (worst case n²), counting about 10⁶ plus the value range.
Chart— at n = 10⁶ and k = 10, rough operation counts: sorting about 2 × 10⁷, a size-k heap about 3.3 × 10⁶, quickselect about 2 × 10⁶ on average (worst case n²), counting about 10⁶ plus the value range.
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?

  1. Sort them; O(n log n) is fine
  2. A size-k heap works, since k = n/2
  3. 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
  4. Counting always works
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:

  1. n (and m, q, k): which complexity class fits the budget?
  2. Value range: can I index by value? Do I need to worry about overflow (in other languages)?
  3. Order and uniqueness: sorted? distinct? that's free structure to exploit.
  4. Memory: can I afford O(n) extra? In Python, at ~36 bytes per value?
  5. Access pattern: stream or random access? read-only or modifiable?
  6. 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?

  1. Counting into 101 buckets: O(n + 101) time and tiny memory, with no worst case
  2. Quickselect: O(n) average
  3. Sort: O(n log n)
  4. A heap of size k
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

  1. Roughly how many simple operations per second can Python do, and why does that matter?
  2. What complexity fits n ≤ 5,000? n ≤ 10⁶? n ≤ 20?
  3. Which constraints besides n can change the algorithm? Give an example of each unlocking or removing an option.
  4. Why does a stream rule out sorting for the k-th smallest, and what replaces it?
  5. When does counting beat every comparison-based method, and when is it impossible?
  6. Why is quickselect O(n) on average but O(n²) in the worst case?
Answers
  1. About 10⁷; it converts the limit on n into an affordable complexity.
  2. O(n²); O(n log n) or O(n); O(2ⁿ · n).
  3. 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).
  4. 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.
  5. When values lie in a small range V: O(n + V) with no worst case. Impossible when V is huge (like 10⁹).
  6. 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.