Brute Force
Brute force means trying every possible solution until you find one that works. It is not elegant, but it is correct — and correct is the baseline every optimization must match. Before writing a clever algorithm, write the brute force first. It gives you something to test against and often reveals the structure that makes a faster approach possible.
What Brute Force Really Means
Brute force algorithms explore the entire search space without pruning or shortcutting. The defining traits are:
- No intelligence about which candidates to skip — every possibility is examined
- Guaranteed correctness — if a solution exists in the space, brute force will find it
- Poor scalability — time complexity grows exponentially or polynomially with input size
Brute force is not "bad code." It is a deliberate choice to prioritize clarity over performance, usually as a first step toward a real solution.
Nested Loops — All Pairs O(n²)
The simplest brute force pattern is checking every pair of elements. This covers problems like "find two elements that sum to a target."
// Two Sum — Brute Force O(n²) time, O(1) space
function twoSumBrute(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
console.log(twoSumBrute([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSumBrute([3, 2, 4], 6)); // [1, 2]Nested Loops — All Triples O(n³)
For problems involving three elements (like 3Sum), the brute force uses three nested loops:
// 3Sum — Brute Force O(n³) time
function threeSumBrute(nums) {
const result = [];
const seen = new Set();
const n = nums.length;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triple = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
const key = triple.join(',');
if (!seen.has(key)) {
seen.add(key);
result.push(triple);
}
}
}
}
}
return result;
}
console.log(threeSumBrute([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]Generating All Subsets O(n · 2ⁿ)
To brute-force subset problems, generate all 2^n subsets. Use a bitmask: for n elements, integers from 0 to 2^n - 1 each represent a unique subset by their binary digits. If bit i is set, include element i.
// Generate all subsets using bitmask — O(n · 2^n)
function allSubsets(nums) {
const n = nums.length;
const result = [];
for (let mask = 0; mask < (1 << n); mask++) {
const subset = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) { // bit i is set → include nums[i]
subset.push(nums[i]);
}
}
result.push(subset);
}
return result;
}
// [1,2,3] produces 8 subsets: [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]
console.log(allSubsets([1, 2, 3]));
// Subset sum brute force — O(n · 2^n)
function subsetSumExists(nums, target) {
const n = nums.length;
for (let mask = 0; mask < (1 << n); mask++) {
let sum = 0;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) sum += nums[i];
}
if (sum === target) return true;
}
return false;
}
console.log(subsetSumExists([3, 1, 4, 2], 5)); // true (3+2 or 1+4)Generating All Permutations O(n!)
When order matters (traveling salesman, anagram checking), you need all n! permutations.
The recursive swap approach fixes element at position start one at a time:
// All permutations — O(n! · n)
function permutations(nums) {
const result = [];
function backtrack(start) {
if (start === nums.length) {
result.push([...nums]);
return;
}
for (let i = start; i < nums.length; i++) {
[nums[start], nums[i]] = [nums[i], nums[start]]; // choose
backtrack(start + 1);
[nums[start], nums[i]] = [nums[i], nums[start]]; // unchoose
}
}
backtrack(0);
return result;
}
console.log(permutations([1, 2, 3]));
// [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]When Brute Force Is the Right Answer
Brute force is not always wrong. There are legitimate scenarios where it is the correct choice:
Input size is provably small and bounded (n ≤ 20 for bitmask, n ≤ 12 for permutations)
You need a reference implementation to validate a faster algorithm
The problem is solved once and performance is irrelevant
In a coding interview, establish correctness before optimizing
Edge cases are numerous and a clever approach risks missing them
Constraints say n ≤ 1000 and O(n²) fits within the time limit
The Optimization Workflow
The standard workflow in competitive programming and interviews is:
- Write the brute force — get it working and passing test cases
- Identify the bottleneck — which loop runs the most iterations?
- Find redundant work — are you recomputing the same thing repeatedly?
- Apply the right technique — hash map, sorting, two pointers, DP, binary search
The brute force reveals what you are computing. The optimization asks whether you can compute the same thing faster.
Two Sum: O(n²) → O(n)
The brute force checks every pair. The bottleneck: for each element x,
we scan all remaining elements to find target - x.
Insight: Instead of scanning, store elements in a hash map. Then look up the complement in O(1).
// Two Sum — Optimized O(n) time, O(n) space
function twoSumOptimal(nums, target) {
const seen = new Map(); // value → index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(nums[i], i);
}
return [];
}
const nums = [2, 7, 11, 15];
console.log(twoSumOptimal(nums, 9)); // [0, 1] — same result, 4x fewer ops on large inputsApproach | Time | Space | Key Idea |
|---|---|---|---|
Brute force | O(n²) | O(1) | Check every pair |
Hash map | O(n) | O(n) | Store seen values for O(1) lookup |
Sorted + two pointers | O(n log n) | O(1) | Move pointers inward on sorted array |
3Sum: O(n³) → O(n²)
The brute force uses three nested loops. The optimization fixes one element and uses the two-pointer technique on the remaining sorted subarray. This reduces one O(n) scan to a linear sweep, saving one full dimension.
// 3Sum — Optimized O(n²) time, O(1) extra space
function threeSum(nums) {
nums.sort((a, b) => a - b); // O(n log n) — dominated by O(n²) below
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicates
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++; // need a larger sum
} else {
right--; // need a smaller sum
}
}
}
return result;
}
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]Complexity Comparison Across Problems
Problem | Brute Force | Optimized | Technique |
|---|---|---|---|
Two Sum | O(n²) | O(n) | Hash map |
3Sum | O(n³) | O(n²) | Sort + two pointers |
Subset Sum | O(n · 2^n) | O(n · W) | Dynamic programming |
String search | O(n · m) | O(n + m) | KMP / Rabin-Karp |
Shortest path | O(V!) | O(V² or E log V) | Dijkstra / BFS |
Brute Force Checklist
Write the brute force — what is the simplest possible solution?
Verify it passes all provided examples and edge cases
Determine its time complexity — does it fit within constraints?
Identify the inner loop — what is it computing that could be pre-computed?
Choose the optimization technique that eliminates the redundant work
Implement the optimization and verify it produces identical output
Common Brute Force Patterns
Pattern | When to Use | Complexity |
|---|---|---|
Nested loops — pairs | Find two elements satisfying a condition | O(n²) |
Nested loops — triples | Find three elements satisfying a condition | O(n³) |
Bitmask enumeration | Try all subsets of n ≤ 20 elements | O(n · 2^n) |
Recursive permutation | Try all orderings of n ≤ 12 elements | O(n!) |
Exhaustive DFS/BFS | Explore all paths in a graph or grid | O(V + E) |
All subarrays | Check every subarray of length 1 to n | O(n²) |