Brute Force Algorithm: Write It First, Then Optimize
Another entry in the series where I break down coding-interview ideas that took me too long to understand. This one is a habit I resisted for years: writing the dumbest possible solution first, on purpose.
I used to treat the brute force approach like something to be ashamed of. I would spot the naive answer in ten seconds and refuse to say it out loud because it felt too obvious. That instinct cost me more interviews than any gap in my data-structure knowledge ever did. The brute force solution is not the thing you apologize for. It is the thing you build on.
What a brute force solution actually is
A brute force algorithm is a brute force method of solving a problem the most direct way possible: try every option, check every pair, walk every path, and do not worry about repeated work. It maps straight from the problem statement to code with no cleverness in between.
Take the classic Two Sum problem. Given an array and a target, you need the indices of two numbers that add up to the target. The brute force approach is exactly what the problem says: check every pair and see if any pair hits the target.
# two_sum_brute.py
def two_sum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []Two loops, one comparison. The brute force time complexity here is O(n squared), because for every element you scan every element after it. Nobody hands you an offer for this code, but it works, it is correct, and you wrote it in under a minute.
Why interviewers want to see it first
A brute force approach that returns the right answer proves you translated the problem correctly. It also gives you a baseline to optimize against: once you can say "this is O(n squared) because of the nested scan," optimization becomes a concrete question instead of a staring contest. And it keeps you talking, which matters because interviewers grade your thought process, not just your final code. I covered that part in a separate post on how to communicate your thought process during a coding interview.
Crucially, a working naive solution means you are never empty-handed. If you run out of time, you still have correct code on the board, and partial credit is real.
From brute force to optimal
Once you have the naive version, optimizing is usually about spotting wasted work and trading time for space. The Two Sum brute force rechecks pairs over and over. For each number I am really asking "is there another number equal to target minus this one?" A hash map answers that in one step.
# two_sum_optimal.py
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
need = target - n
if need in seen:
return [seen[need], i]
seen[n] = i
return []Same problem, one pass, O(n) time and O(n) space. That is the brute force vs optimal solution story in miniature: I noticed the inner loop was really a lookup and replaced repeated scanning with a structure built for lookups. The optimal version grew directly out of the naive one.
Not every optimization is a hash map. Some collapse repeated subproblems with dynamic programming, others sort first or slide a window. The common thread is that you start naive so you have something concrete to improve, in the same spirit as the twelve core patterns Levelop teaches instead of grinding 2500 problems.
Mistakes I made while learning this
I stayed silent until I had the optimal answer, which left long nervous gaps. I optimized before anything worked, then had no correct baseline to fall back on. And I forgot to state the complexity out loud, which is half the signal an interviewer wants. Saying "this is O(n squared), let me see if I can do better" shows the improvement is a deliberate choice, not luck. Brute force and optimal are the same problem at two levels of polish.
What to practice next
For each problem, force yourself to write the brute force solution first, state its time complexity, then optimize. Two Sum then Three Sum teach the "remove the inner loop" move. Longest Substring Without Repeating Characters is the cleanest O(n squared) to O(n) sliding-window jump. Maximum Subarray shows Kadane's algorithm as the brute force with redundant work removed. For a structured path, I have been working through Levelop's coding interview preparation guide.
FAQ
Is it bad to use a brute force approach in a coding interview?
No. Leading with a brute force solution is a strong move as long as you recognize it as the starting point and say you plan to optimize. What hurts you is presenting the naive answer as final with no attempt to improve it.
When is a brute force algorithm the right final answer?
When the input is small enough that the brute force time complexity does not matter, or the constraints guarantee the naive bound is fine. If the array is at most a few hundred elements, an O(n squared) solution may be perfectly acceptable and clearer than a clever alternative.
How do I go from a brute force solution to an optimal one?
Find the repeated work. Nested loops that recompute the same thing are usually replaceable with a hash map, sorting, two pointers, a sliding window, or dynamic programming. The optimal is almost always the brute force with one piece of redundant computation removed.
What is the time complexity of a typical brute force algorithm?
Often O(n squared), O(n cubed), or exponential, because it tries every pair, triple, or combination. Optimizing brings that down, commonly to O(n log n) or O(n) by trading time for a bit of extra space.
Should I mention the brute force idea even if I already see the optimal solution?
Yes, briefly. Naming the naive bound before you improve it signals range and costs you only a few seconds.
Wrapping up
The brute force approach stopped being my embarrassing secret when I realized every optimal solution I admired was a naive one with the wasted work stripped out. Start intentionally naive, get something correct on the board, then hunt the redundancy. That sequence has done more for my interview performance than any algorithm I ever memorized.