From Brute Force to a Better Solution
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Most problems have a slow, obvious solution and a faster one that avoids repeated work. Write the slow one first, find what it repeats, then remove that.
Start with brute force
Brute force is solving a problem by trying every possibility and keeping the ones that fit. It is simple and usually correct, but often too slow for large input.
Try every possibility first. A brute-force solution is easy to get right, and it becomes your answer key for checking faster versions. Here: do two orders add up to a target?
def has_pair(amounts, target): for i in range(len(amounts)): for j in range(i + 1, len(amounts)): if amounts[i] + amounts[j] == target: return True return False
print(has_pair([8, 3, 11, 5], 14))print(has_pair([8, 3, 11, 5], 100))The inner loop starts at i + 1, so each pair is checked once and no order is paired with itself.
Count the steps
Time complexity is how the number of steps grows as the input size n grows, written O(n), O(n log n) or O(n^2). Small constants are ignored.
To compare solutions, count how the work grows as n grows. Ignore small constants and keep the shape. Two nested loops over n items do about n squared checks.
for n in [10, 100, 1000]: print(n, n * (n - 1) // 2)Example 1 · Count the work of brute force
def pair_checks(amounts, target): checks = 0 for i in range(len(amounts)): for j in range(i + 1, len(amounts)): checks += 1 if amounts[i] + amounts[j] == target: return True, checks return False, checks
print(pair_checks([8, 3, 11, 5, 9, 2], 14))print(pair_checks([8, 3, 11, 5, 9, 2], 100))(True, 6) (False, 15)
What this code does
- The first call stops early at the pair (3, 11), after 6 checks.
- When there is no answer the loop checks all 15 pairs, which is the worst case.
Ten times more items gives about a hundred times more pair checks. That growth is what time complexity describes.
Remember what you have seen
The nested loop asks one question per pair. Instead, ask one question per item: has the partner I need already appeared? A set answers that in one step.
def has_pair(amounts, target): seen = set() for amount in amounts: if target - amount in seen: return True seen.add(amount) return False
print(has_pair([8, 3, 11, 5], 14))Example 2 · Count the work of the set version
def lookups(amounts, target): seen = set() steps = 0 for amount in amounts: steps += 1 if target - amount in seen: return True, steps seen.add(amount) return False, steps
print(lookups([8, 3, 11, 5, 9, 2], 14))print(lookups([8, 3, 11, 5, 9, 2], 100))(True, 3) (False, 6)
What this code does
- The worst case is 6 steps for 6 items, one per item.
- For 1,000 items that is 1,000 steps against 499,500 pair checks.
Example 3 · Check the fast version against brute force
import random
def slow(values, target): return any(values[i] + values[j] == target for i in range(len(values)) for j in range(i + 1, len(values)))
def fast(values, target): seen = set() for v in values: if target - v in seen: return True seen.add(v) return False
rng = random.Random(7)for _ in range(200): values = [rng.randint(-5, 5) for _ in range(rng.randint(0, 6))] target = rng.randint(-8, 8) assert slow(values, target) == fast(values, target), (values, target)print("200 random cases match")200 random cases match
What this code does
- Small random inputs are cheap for brute force and cover edge cases such as empty lists and repeated values.
- If the two ever differ, assert prints the input that broke the fast version.
Each item is checked once and the lookup in a set takes about one step, so the work is about n steps instead of n squared.
Trade memory for speed, or sort first
Space complexity is how much extra memory a solution needs as the input size n grows. A set of n items needs O(n) extra space, a few variables need O(1).
The set is faster but stores the items. Space complexity counts that memory. If memory matters, sorting puts equal values next to each other, so one pass over neighbours is enough.
orders = [41, 7, 19, 7, 30]print(len(set(orders)) != len(orders))ordered = sorted(orders)print(any(a == b for a, b in zip(ordered, ordered[1:])))Example 4 · Most frequent product id
from collections import Counter
ids = [5, 3, 5, 3, 9, 5]print(max(set(ids), key=ids.count))print(Counter(ids).most_common(1)[0][0])5 5
What this code does
ids.countscans the whole list for every distinct id, so the first line is a hidden double loop.Countercounts everything in one pass. Both print 5, but only the second stays fast for large lists.
Example 5 · Many range sums with prefix sums
from itertools import accumulate
sales = [4, 2, 7, 1, 6]prefix = [0, *accumulate(sales)]print(prefix)print(prefix[4] - prefix[1])print(sum(sales[1:4]))[0, 4, 6, 13, 14, 20] 10 10
What this code does
prefix[i]is the total of the first i sales, so the sum from position 1 to 3 isprefix[4] - prefix[1].- Building the prefix list costs n steps once. After that every range sum costs one subtraction, not a new loop.
Both lines find a repeated order. The set uses extra memory for n items. Sorting costs n log n steps but can work in place with .sort().
Brute force is sometimes the answer
When n is tiny, trying everything is the right choice. With about 20 items you can check every group of items and the code stays short and safe.
from itertools import combinations
def can_make(amounts, target): for size in range(1, len(amounts) + 1): for group in combinations(amounts, size): if sum(group) == target: return True return False
print(can_make([7, 3, 9, 4], 16))print(can_make([7, 3, 9, 4], 5))Example 6 · Two sum with positions
def two_sum(amounts, target): position = {} for i, amount in enumerate(amounts): if target - amount in position: return position[target - amount], i position[amount] = i return None
print(two_sum([8, 3, 11, 5], 14))print(two_sum([8, 3, 11, 5], 100))(1, 2) None
What this code does
- A dictionary stores each value with its position, so the answer can name the two indexes.
- The function returns None when no pair exists. Decide that answer from the statement.
combinations builds every group of a given size. For 20 items that is about a million groups, which Python handles.
Next step
Check your understanding
10 quick questions