cf.completefrontend
FOUNDATIONS · FOUNDATION

Brute force

Try every possible answer, check each one, and keep the best.

Time O(n^2)Space O(1)3 practice problemsStep-through picture

The idea

Brute force means trying every possibility. If the answer is one of the pairs in a list, check every pair. If it is a subset, check every subset. It is the most direct way to solve a problem: you don't need a clever idea, only a way to list all the candidates and a way to check one.

Brute force is slow when there are many candidates, but it is almost always correct, and it is usually the first solution to write. It shows that you understand the problem, it gives you a baseline to test faster ideas against, and when the input is small it is often the best answer.

The code here finds the pair of numbers whose sum is closest to a target. It checks every pair i < j, works out the sum, and keeps the sum closest to target.

An everyday example

Trying every key on the key ring

You have a ring of 12 keys and one locked door. You don't know which key fits. So you try the first key, then the second, then the third, until one turns. You never skip a key and you never try the same key twice, so you are sure to find the right one. With 12 keys that is fine. With 10,000 keys you would want a better plan, like reading the labels.

How the example maps to the code
In the exampleIn the code
The key ringAll candidates: every pair (i, j)
Trying one key in the lockChecking one pair: sum = nums[i] + nums[j]
Remembering the key that worked bestbest
Going through the ring in orderThe two nested for loops

From the slow way to brute force

  1. Start with no idea at all. You could guess a few pairs, add them, and keep the one closest to target. But guessing can't tell you when to stop, and it can't prove that some pair you didn't try isn't closer. To be sure, every candidate has to be checked.
  2. So list every candidate in an order that can't skip or repeat one. For pairs, pick the first index i, then every later index j with j > i. Starting j at i + 1 means each pair is listed once and an item is never paired with itself.
  3. Next, give each candidate a score and keep only the best one so far. Here the score is Math.abs(sum - target), the distance from the target. You don't need to store all the sums: one variable, best, is enough, because a candidate that loses to best can never win later.
  4. Finally, count the candidates before you write the code. With n numbers there are n * (n - 1) / 2 pairs, so this is fine for a few thousand numbers and too slow for a few hundred thousand. Listing every candidate, scoring it, and keeping the best: that loop is brute force.

How it works

  1. Decide what one candidate looks like. Here it is a pair of indexes i and j with i < j.
  2. List every candidate with loops: i from 0, and j from i + 1, so each pair is seen exactly once.
  3. For each candidate, compute its value: sum = nums[i] + nums[j].
  4. Compare it with the best so far, best. Here, closer to target means better.
  5. If it is better, replace best.
  6. After every candidate has been checked, return best.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function closestPairSum(nums, target) {
  2. let best = null;
  3. for (let i = 0; i < nums.length; i++) {
  4. for (let j = i + 1; j < nums.length; j++) {
  5. const sum = nums[i] + nums[j];
  6. if (best === null || Math.abs(sum - target) < Math.abs(best - target)) {
  7. best = sum;
  8. }
  9. }
  10. }
  11. return best;
  12. }

How fast it is

TimeO(n^2)
Extra memoryO(1)

The two loops check n * (n - 1) / 2 pairs, which grows like n^2. Only best and a few counters are stored.

  • Best caseO(n^2)

    Every input of size n: even if the very first pair equals target exactly, this code keeps checking all n * (n - 1) / 2 pairs. An early return would make the best case O(1).

  • Average caseO(n^2)

    Any list of numbers: the number of pairs depends only on n, about 500,000 for 1,000 numbers.

  • Worst caseO(n^2)

    Same as every other case. For 100,000 numbers that is about 5 billion pairs, which is far too slow.

Common mistakes

  • Starting j at 0 instead of i + 1. Each pair is checked twice and an item is paired with itself.
  • Using brute force when n is 100,000. Check the limits first: about 10^8 simple steps is the most you can afford.
  • Starting best at 0, which looks like a real answer. Use null or Infinity for "nothing yet".
  • Changing the input while looping over it, which makes some candidates get skipped or checked twice.

When to use it

Look for these clues in a problem:

  • The input is small: n <= 20 for subsets, n <= 1000 for pairs, n <= 100 for triples.
  • You can't see a pattern yet and need a correct answer first.
  • You want a slow but surely correct version to test a faster solution against.
  • The problem asks for the best of a small number of choices, like every way to pick 2 or 3 items.

Check yourself

Answer each one in your head first, then open it.

How many pairs does the code check for 10 numbers?

45, which is 10 * 9 / 2. Each of the 10 items pairs with every later item.

Why does j start at i + 1 instead of 0?

Starting at 0 would check each pair twice, as (i, j) and (j, i), and would pair an item with itself when j === i.

Why is best started at null instead of 0?

0 looks like a real sum, and if every real sum is farther from target than 0 is, the code would return a sum that no pair makes.

If the time limit allows about 10^8 steps, roughly how big can n be for an O(n^2) brute force?

About 10,000 to 14,000, because n * n / 2 reaches 10^8 near n = 14,000. Past that, you need a faster idea.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loops keep one promise: after any number of pairs have been checked, best is the closest sum among those pairs, and the earliest one if several tie. Before the first pair, nothing has been checked and best is null, so the promise holds with nothing to promise.

Each check keeps the promise. If the new sum is strictly closer, it beats every earlier pair, so it becomes best. If it is farther or equally close, the old best is still at least as close as everything seen, so leaving it alone is correct.

The loops visit every pair exactly once: for each i, j runs over every later index, so the pair (i, j) with i < j appears when the outer loop is at i and at no other time. When both loops end, every pair has been checked, so the promise says best is the closest sum of all.

Going deeper

3 more ideas

Why it can't miss

The loops produce every pair i < j exactly once, and each pair is compared with best. So when the loops end, best has been compared with every possible sum, and no pair was skipped. That is the strength of brute force: its correctness is easy to see.

How fast it grows

With n numbers there are n * (n - 1) / 2 pairs, which is O(n^2). For 1,000 numbers that is about 500,000 checks: fast. For 100,000 numbers it is 5 billion: far too slow. Trying all subsets is worse, O(2^n): 20 items give about a million subsets, 40 items give a trillion. Read the input limits to know if brute force is enough.

Making brute force smarter

Two common improvements keep the brute-force shape. First, stop early: if a sum equals target exactly, nothing can beat it, so return right away. Second, prune: skip candidates that can't win. Many faster algorithms start from brute force: sorting plus two pointers, or a hash map, are ways to avoid checking pairs that can't matter.

Work it by hand

Every step in a table, with why

Find the pair sum closest to 18 in 4 numbers. Two pairs tie for closest, which shows how the strict < breaks the tie.

nums = [6, 13, 3, 11], target = 18

StepijsumDistancebestWhat happensWhy
10119119First pair: best was null6 + 13 = 19, one away from 18. Any first pair becomes best.
20299199 is farther: keep 196 + 3 = 9 is 9 away, much worse than 1.
30317119A tie: keep 196 + 11 = 17 is also 1 away. 1 < 1 is false, so the earlier pair stays.
4121621916 is farther: keep 19i moves to 1 and j restarts at i + 1 = 2. 13 + 3 = 16 is 2 away.
5132461924 is farther: keep 1913 + 11 = 24, 6 away.
62314419Last pair: keep 193 + 11 = 14, 4 away. This is the 6th pair, which is 4 * 3 / 2.

It returns 19 after checking all 6 pairs. The loops stop only when every pair has been tried; nothing in this code stops early.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Brute forceO(n^2)O(1)n is at most a few thousand, you need a correct answer that is quick to write, or you want a reference to test a faster version against.
Sort, then two pointersO(n log n)O(n)n is large. Sort a copy, then move left and right inward, keeping the closest sum: the walk takes O(n) after the sort.
Sort, then binary search each partnerO(n log n)O(n)You already have binary search code, or you need each item's best partner rather than just the overall best.

Extra memory: O(1): only best, sum, i, and j, whatever the size of nums.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Brute force and the other approaches, on a scale where each line up is 10 times more steps.
  • Brute force O(n^2)
  • Sort, then two pointers, Sort, then binary search each partner O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Brute force1001 million1 trillion
Sort, then two pointers339,96620 million
Sort, then binary search each partner339,96620 million

Inputs that need care

5 tricky inputs
Fewer than two numbers: nums = [] or nums = [7]
The inner loop never runs, so best stays null and the function returns null. The caller must treat null as "no pair exists".
Two pairs equally close, like 17 and 19 for target = 18
The strict < keeps the earlier pair. Use <= if the question wants the last one, or compare a second rule, such as the smaller sum, on a tie.
A pair that hits target exactly
This code keeps looking, which is correct but wasteful. Add if (sum === target) return sum; because nothing can be closer than 0 away.
Negative numbers: nums = [-4, 9, -6, 1], target = 0
Math.abs handles them: the sums are 5, -10, -3, 3, 10, -5, and -3 and 3 tie at 3 away, so the earlier -3 is returned.
Repeated values: nums = [2, 2], target = 5
The two 2s are different indexes, so the pair is allowed and best is 4. Brute force pairs positions, not values.

Variations and follow-ups

Twists interviewers add

Stop early

When a candidate can't be beaten, return it right away. Here, a sum equal to target ends the search. This doesn't change the worst case, but on many inputs it saves most of the work.

Every subset

When a candidate is any group of items, there are 2^n subsets. Count mask from 0 to 2^n - 1 and read each bit as "take this item or not". This is fine for n up to about 20 (about a million subsets) and hopeless for 40.

Prune with a bound

Skip candidates that can't win. If the numbers are sorted and even the biggest possible sum from here is too small, stop that branch. Backtracking is brute force with this kind of pruning built in.

Brute force as a test oracle

Write the slow, obviously correct version, then generate thousands of small random inputs and check that the fast version gives the same answers. When they differ, the random input is a ready-made failing test.

In an interview

Spot it, explain it, answer follow-ups
  • Say the brute-force idea first, with its cost: "I could check all n * (n - 1) / 2 pairs, which is O(n^2)." It proves you understand the problem, and it is the baseline your better idea must beat.
  • Check the limits before improving it. If n <= 1000, O(n^2) is about half a million steps, and the brute force may already be the expected answer.
  • When asked to improve it, ask what work is wasted. Here, most pairs can't be the closest; sorting lets two pointers skip them. Naming the waste is how you get from brute force to a better algorithm.
  • Test by hand on 3 or 4 numbers, including a tie and a negative number. Brute force is also your tool for checking the faster solution: run both on small random inputs and compare.

Where frontend code uses it

The same idea in real UI code
  • Collision checks in a small canvas game or a drag-and-drop editor often compare every pair of shapes, which is fine for a few dozen shapes.
  • Writing a slow, obviously correct version of a layout or diff function and comparing its output with the fast version in unit tests.
  • Trying every font size from largest to smallest until a headline fits its box is a brute-force search over a small range.

Related algorithms