Lesson 1 of 6

How to think about complexity and approach any problem

2 min read

Big-O in one page

Big-O describes how time or memory grows as the input size n grows, ignoring constants.

Complexity	Name	Typical example	n = 10⁵ feasible?
O(1)	constant	hash map lookup	yes
O(log n)	logarithmic	binary search	yes
O(n)	linear	one pass over an array	yes
O(n log n)	linearithmic	sorting	yes
O(n²)	quadratic	nested loops over the array	borderline (10¹⁰ is too slow)
O(2ⁿ)	exponential	all subsets	only for n ≈ 20

Rule of thumb: about 10⁸ simple operations per second. Read the constraints first: n ≤ 10⁵ means you need O(n log n) or better; n ≤ 20 invites backtracking.

Space complexity counts extra memory: a hash set of all elements is O(n); recursion uses O(depth) stack space.

The interview process that works

Clarify: input size, ranges, negatives, duplicates, empty input, sorted or not, what to return.
Examples: walk through one normal and one edge case by hand.
Brute force: state it and its complexity. It shows you can solve it at all.
Optimise: which pattern removes the repeated work? (hashing, sorting, two pointers, prefix sums, a heap, DP).
Code cleanly, with good names, talking as you go.
Test: dry-run your examples and edge cases; fix bugs calmly.
Analyse the final time and space complexity.

Interviewers grade communication and process, not just the final answer. Silence is the most common reason good coders fail.

Recognising patterns from the wording

Clue in the problem	Try
"pairs/triplets", sorted array	two pointers
"contiguous subarray/substring", "longest/shortest window"	sliding window
"have we seen this before?", counts, duplicates	hash map / set
"sorted", "minimum value that works"	binary search (also on the answer)
"next greater", matching brackets	stack
"k largest/smallest", "merge k"	heap
tree or graph, "levels", "shortest path in steps"	BFS
"all combinations/permutations"	backtracking
"number of ways", "min/max cost", overlapping choices	dynamic programming