How to approach any new DSA problem from scratch.
Don't try to remember 400 solutions. Follow the same six steps every time — from Brute → Better → Optimal — and use the decision tree to pick the pattern.
The 6-step thinking process (use this on every problem)
Recognise — read the input and the constraints
Before thinking about code, decide what kind of problem this is. The input shape and the limits already tell you which patterns are possible.
- •
Input shape: array / string (sorted or not?), linked list, tree, graph or grid, intervals, a stream.
- •
What is asked: count, min / max, exists?, return ALL answers, Kth item, or an order.
- •
Constraints → target complexity:
n ≤ 20→2^nis fine;n ≤ 10^3→O(n²);n ≤ 10^5→O(n log n)orO(n). - •
Keywords: "contiguous", "at most K", "sorted", "next greater", "all combinations", "minimum cost" — each is a pattern clue (see the tree below).
Brute force — say the obvious slow solution out loud
Always start with the simplest correct idea, even if it is too slow. It proves you understood the problem and becomes your reference answer for testing.
- •
Try every subarray / pair / subset / path that the question allows.
- •
State its time and space complexity, and compare with the target from step 1.
- •
Keep this code: later you will compare the optimal against it on random inputs.
Repeated work — find what brute force computes again and again
The optimal solution almost always comes from removing repeated work. Ask: which values does brute force recompute, and can I reuse them?
- •
Neighbouring windows overlap → Sliding Window. Range sums recomputed → Prefix Sum.
- •
Searching again for a complement / seen value → Hash Map. Searching in sorted data → Binary Search.
- •
Same sub-problem solved many times → DP (memo / table). Re-scanning for the next bigger value → Monotonic Stack.
- •
Repeatedly picking the smallest / largest → Heap.
State + validity — decide what to keep and when it is valid
Write down the smallest amount of information you carry while scanning, and the rule (invariant) that is true at every step.
- •
Examples of state: window counts,
dp[i], a heap of size K, a stack of candidates,parent[]in Union-Find. - •
Validity rule: "the window has at most K distinct", "the stack is decreasing", "
dp[i]is the best answer ending ati". - •
If you cannot say the invariant in one sentence, the state is probably wrong.
Transitions — when to move what, and why it is safe
Decide exactly how the state changes on each step, and argue why you never skip the answer.
- •
Pointers: when do you grow, when do you shrink, and why can a skipped position never be the answer?
- •
DP: which smaller states does
dp[i]depend on, and in what loop order? - •
Greedy: name the proof — exchange argument, stays ahead, or elimination.
Code + test — write it, dry-run it, compare
Write clean code, then trace it on the example by hand before running it.
- •
Dry-run the given example and check the state after every step.
- •
Edge cases: empty input, one element, all equal, negatives, duplicates,
intoverflow. - •
Compare the optimal with your brute force on small random inputs.
Clue → pattern decision tree
Start on the left with what the input looks like, follow the clue that matches your problem, and land on a pattern. Click a pattern to open its lesson.