Brute force to optimal - DSA Learning Guide

Overview

Brute force to optimal is the core problem-solving loop of coding interviews: start with any correct solution, state its complexity, identify the bottleneck (the repeated or wasted work), and remove it with the right technique. Interviewers want to see this reasoning, not just the final answer.

Most optimizations fall into a few moves: replace a nested search with a hash map, exploit sorted order with two pointers or binary search, reuse previous work with prefix sums or sliding windows, cache repeated subproblems with DP, or keep only the best candidates with a heap or monotonic stack.

Finding a book in a library

Brute force is checking every shelf. The first optimization is noticing books are sorted by title (binary search). The next is asking the librarian's catalog (a hash map). Each step removes a specific kind of wasted effort.

When to use it

Every coding interview problem, right after clarification.
When you do not immediately see the optimal approach.
When the interviewer asks 'can we do better?'.
To have a correct fallback if time runs out.

Problem patterns it solves

Nested search -> hash map

Recognize it when: for each element, search for a partner.

1. Two Sum
217. Contains Duplicate
128. Longest Consecutive Sequence

All subarrays -> sliding window / prefix sum

Recognize it when: recomputing sums or counts of overlapping ranges.

209. Minimum Size Subarray Sum
560. Subarray Sum Equals K
3. Longest Substring Without Repeating Characters

Unsorted search -> sort + two pointers / binary search

Recognize it when: pairs, triplets, or thresholds.

15. 3Sum
881. Boats to Save People
875. Koko Eating Bananas

Exponential recursion -> DP

Recognize it when: the same arguments recur in the recursion tree.

70. Climbing Stairs
322. Coin Change
139. Word Break

Scan for next greater -> monotonic stack

Recognize it when: for each element, scan forward for the next larger.

739. Daily Temperatures
84. Largest Rectangle in Histogram

Full sort -> heap

Recognize it when: only the top k items matter.

215. Kth Largest Element
347. Top K Frequent Elements

Where it is used in real software

Performance tuning

Engineers profile a slow endpoint, find the bottleneck (often an N+1 query or nested loop), and replace it with a join, index, or cache.

Incremental delivery

Teams ship a simple correct version first, measure, and optimize the proven hot spots.

Code review

Reviewers point out O(n^2) patterns like includes inside a loop and suggest Sets or Maps.

Key terms

Bottleneck: The part of the algorithm that dominates running time.
Repeated work: Recomputing something already known.
Unnecessary work: Checking candidates that can be ruled out.
BUD: Bottlenecks, Unnecessary work, Duplicated work: a checklist for optimization.

The optimization loop

1
State the brute force
Describe the simplest correct approach and its complexity out loud, even if you will not code it.
2
Find the bottleneck
Which loop dominates? What does the inner loop search for or recompute?
3
Ask what you could remember
Could a hash map, prefix sum, or DP table remove the inner work?
4
Ask what order would help
Would sorting enable two pointers, binary search, or greedy choices?
5
Confirm the new complexity fits
Compare with the constraints, then code the optimal version.

Optimizing 'count subarrays with sum k'

nums has n <= 2 x 10^4 values, including negatives

Version	Idea	Time	Space	Bottleneck removed
1. Brute force	Every (i, j), sum the range	O(n^3)	O(1)	-
2. Running sum	Extend j from each i, keep a running sum	O(n^2)	O(1)	recomputing range sums
3. Prefix sums	sum(i..j) = P[j + 1] - P[i]	O(n^2)	O(n)	same, with O(1) range sums
4. Prefix sum + hash map	Count earlier prefixes equal to P - k	O(n)	O(n)	searching earlier prefixes

NOWVersion: 1. Brute force | Idea: Every (i, j), sum the range | Time: O(n^3) | Space: O(1) | Bottleneck removed: -

Each step removed one specific waste. A sliding window was never an option because negatives break its shrinking rule, which is why clarifying 'can values be negative?' mattered.

Implementation

1// Step 1: brute force, O(n^2) - correct, easy to verify2function subarraySumBrute(nums, k) {3  let count = 0;4  for (let i = 0; i < nums.length; i++) {5    let sum = 0;6    for (let j = i; j < nums.length; j++) {7      sum += nums[j];8      if (sum === k) count++;9    }10  }11  return count;12}13 14// Step 2: remove the inner search with a hash map of prefix sums, O(n)15function subarraySum(nums, k) {16  const prefixCount = new Map([[0, 1]]);17  let prefix = 0, count = 0;18  for (const x of nums) {19    prefix += x;20    count += prefixCount.get(prefix - k) ?? 0;21    prefixCount.set(prefix, (prefixCount.get(prefix) ?? 0) + 1);22  }23  return count;24}25 26// Use the brute force as a test oracle for the optimized version27for (let trial = 0; trial < 200; trial++) {28  const nums = Array.from({ length: 12 }, () => Math.floor(Math.random() * 11) - 5);29  const k = Math.floor(Math.random() * 11) - 5;30  console.assert(subarraySum(nums, k) === subarraySumBrute(nums, k), nums, k);31}

Complexity and performance

Common brute forceO(n^2) / O(2^n)

All pairs / all subsets.

Common optimalO(n) / O(n log n)

Hash map, window, sort-based.

DP targetsO(states x transitions)

From exponential recursion.

Trade-offs

Time vs space

Many optimizations spend O(n) memory (hash maps, prefix arrays) to save a factor of n in time. Mention the trade explicitly.

Code the brute force or not

If the optimal idea is clear, describe the brute force briefly and code only the optimal. If you are stuck, coding the brute force secures partial credit.

Variants and related techniques

Simplify then generalize

Solve a special case first (sorted input, k = 1), then extend it.

Precompute

Move repeated work into a preprocessing pass (prefix sums, sparse tables).

Change the question

Binary search on the answer turns 'find the minimum' into 'is x feasible?'.

Common mistakes

Jumping to a clever solution you cannot justify.
Fix: Explain the path from brute force; interviewers score the reasoning.
Optimizing the wrong part.
Fix: Identify the dominant term first; improving an O(n) setup does not fix an O(n^2) loop.
Losing correctness while optimizing.
Fix: Keep the brute force as a mental or actual test oracle.

Interview questions

What do you say when you only see a brute force solution?

State it and its complexity, confirm it is correct with an example, then ask what work is repeated or unnecessary. Offer to code it as a baseline if the interviewer prefers.

How do you know when you have reached optimal?

Compare with a lower bound: you must read the input (Omega(n)), comparison sorting is Omega(n log n), and output size bounds generation problems. Also check that the complexity comfortably fits the constraints.

Practice problems

Problem	Difficulty	What it trains
1. Two Sum	Easy	O(n^2) to O(n).
560. Subarray Sum Equals K	Medium	Four optimization steps.
15. 3Sum	Medium	O(n^3) to O(n^2).
739. Daily Temperatures	Medium	O(n^2) to O(n) monotonic stack.
322. Coin Change	Medium	Exponential recursion to DP.