0
Challenge · 20Cost: Time and Space
Reading constraints to choose your target
Complexityused in ~90% of apps
This is the professional move, and it takes ten seconds. The line most people skip at the bottom of the statement tells you which solution to write, before you have written anything at all.
Core idea. The input size in the constraints tells you which rung of the ladder you can afford. That decides your approach up front, so you never spend twenty minutes writing something that was never going to finish.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
read n, get your target
n ≤ 20O(2ⁿ) is finetry every combination. Recursion, backtracking
n ≤ 500O(n³) is finethree nested loops still finish
n ≤ 5,000O(n²) is finea nested loop is acceptable
n ≤ 1,000,000O(n log n)sorting, or a single pass
n ≤ 100,000,000O(n) or O(log n)one pass at most, or halving
Small n is permission to be simple. Large n is an instruction to be clever.
↑ play a little first, then dig in