Brute force first
Overview
Before reaching for any clever technique, stating the obvious, always-correct, usually-slow solution first — such as nested loops or try-everything recursion.
It establishes a correctness baseline to test faster solutions against. Furthermore, its structure often reveals exactly which optimization applies; for example, a brute force that recomputes the same subproblem repeatedly signals the need for dynamic programming.
Where used: Property-based testing: running complex algorithms alongside slow, trivially correct brute-force ones on restricted datasets to verify correctness., Cryptographic security relies on brute-force limits, ensuring exhaustive key-space traversal is computationally impossible.
Why learn this
- It establishes the theoretical ceiling of time complexity and the baseline for absolute correctness.
- Stating the brute force's complexity first allows you to ask 'what is this complexity wasting?' — the exact question that leads to the optimal pattern.
Common mistakes
- Skipping straight to a 'clever trick': If you cannot state why the brute force is too slow for the given constraints, you cannot mathematically justify the optimization either. Interviewers look for this baseline.
Recall questions
- Why is it valuable to define the brute-force solution before optimizing?
- What is the critical question to ask after stating the brute-force complexity?
Understanding checks
A candidate immediately starts writing an O(n log n) divide and conquer approach for a novel problem. What critical step did they skip, and why is it dangerous?
They skipped establishing the brute-force baseline. Without it, they cannot prove their optimization is necessary, nor do they have a simple, trivially correct oracle to test their complex logic against.
Jumping to optimizations without a baseline often leads to over-engineering or solving the wrong problem, as the candidate hasn't fully explored the search space.
You are asked to find if two numbers in an array sum to a target K. Should you instantly write the O(n) hash map solution, or first describe the O(n^2) nested loops?
First describe the O(n^2) nested loops. This establishes the theoretical ceiling and explicitly identifies the wasted work (scanning the rest of the array repeatedly), which perfectly justifies introducing the hash map.
Interviewers evaluate the problem-solving journey, not just the final code. Proving *why* the hash map is needed by showing the flaws of brute force is a stronger signal of engineering maturity.
Practice tasks
Identify the wasted work
Given a naive O(n^2) function that finds duplicates by comparing every element to every other element, modify the code structure to return the *number of redundant comparisons* made, rather than the duplicates themselves, to quantify the waste.
Continue learning
Previous: What is an Algorithm?
Previous: Big-O Notation
Next: Precomputation
Next: Recognizing divide & conquer
Next: Recognizing two pointers
Next: Recognizing sliding window
Next: Recognizing greedy vs DP