What is brute force, and when is it acceptable?

Question

Accepted Answer

**Brute force** means trying every possible candidate until you find the answer. It is simple and guaranteed correct, but often slow — frequently exponential or O(n²).

## The idea

Exhaustively enumerate the solution space without clever shortcuts.

## Example: find a pair that sums to a target (brute force)

```python
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):  # check every pair
            if nums[i] + nums[j] == target:
                return (i, j)
    return None
# O(n^2) time, O(1) space
```

A hash map turns this into O(n), but the brute-force version is the obvious starting point.

## When it is acceptable

- **Small inputs** where the constant factor and n are tiny.
- As a **correctness baseline** to validate a faster algorithm against.
- When the problem is run rarely and clarity beats speed.
- During interviews, state it first, then optimize.

## Pitfalls

Brute force on large inputs causes timeouts. Always estimate the size of the solution space before committing.

## Why it matters

Brute force is the honest first solution: it proves the problem is solvable and clarifies exactly what "correct" means.

It gives you a reference implementation to test optimizations against.

Knowing when O(n²) or worse is *good enough* is a real engineering skill — not every problem deserves a clever algorithm.