From brute force to optimal: the usual moves

A brute force tells you what to compute. Making it fast is usually a matter of noticing what it computes more than once, and then computing that only once. This lesson works one problem from a brute force to a single pass, checks the fast version against the slow one, and then gathers the moves that remove repeated work into one place, each shown on the same data with a count of the steps it saves. The DSA track’s lesson on the brute-force-to-optimal method follows one problem through these steps; this one is the kit for a round: the usual moves, and what to say about each.

Start with a brute force you trust

The brute force tries every buy day with every later sell day. It is short, and it is right by construction, because it checks every possibility:

def best_profit_brute(prices):
    """Try every buy day and every later sell day: O(n^2)."""
    best = 0
    for buy in range(len(prices)):
        for sell in range(buy + 1, len(prices)):
            best = max(best, prices[sell] - prices[buy])
    return best


def best_profit(prices):
    """One pass, O(n): only the lowest earlier price can be the best day to buy."""
    best, lowest = 0, float("inf")
    for price in prices:
        best = max(best, price - lowest)  # sell today, having bought at the lowest price so far
        lowest = min(lowest, price)
    return best


if __name__ == "__main__":
    for prices in ([31, 24, 27, 22, 29, 26], [40, 35, 33, 30], [18, 23, 15, 28]):
        print(prices, best_profit_brute(prices), best_profit(prices))

[31, 24, 27, 22, 29, 26] 7 7
[40, 35, 33, 30] 0 0
[18, 23, 15, 28] 13 13

Both functions give the same answers on the three lists. The brute force does about n²/2 subtractions, which is five billion at the upper limit: correct, and far too slow. Write it anyway, quickly, and keep it. It will check the fast version for you.

Find the work it repeats

Look at the brute force from the point of view of one sell day. To find the best buy, its inner loop looks at every earlier day and so, in effect, searches for the lowest earlier price. On the next day it searches again, over the same days plus one more. That repeated search is the waste.

So carry the answer along: keep the lowest price seen so far, update it after each day, and compare each new price with it. That is best_profit above, one pass and O(n). The reason it is still correct is worth saying: for every later sell day, an earlier price that is higher than the lowest one so far can never be the best day to buy. It is dominated, so dropping it loses nothing.

Check the fast version against the brute force

The brute force is now a specification you can run. A stress test feeds both versions many small random inputs and stops at the first disagreement:

import random

from profit import best_profit, best_profit_brute


def random_lists(rng):
    """1,000 short price lists, the shortest first, so that a first failure is a small one."""
    for length in range(10):
        for _ in range(100):
            yield [rng.randint(1, 50) for _ in range(length)]


if __name__ == "__main__":
    agreed = 0
    for prices in random_lists(random.Random(7)):  # a fixed seed: every run checks the same lists
        if best_profit(prices) != best_profit_brute(prices):
            print("mismatch:", prices)  # the first failing list, and so one of the shortest
            break
        agreed += 1
    print(f"{agreed:,} random price lists: both versions agree")

1,000 random price lists: both versions agree

The fixed seed means every run checks the same 1,000 lists, so a failure can be reproduced. The lists are short, so the brute force stays quick, and the shortest come first, so that the first failure is a small one.

A plausible shortcut that the stress test catches

The best profit looks as if it should be the highest price minus the lowest. That version is also O(n), and it passes some hand examples. The stress test finds the flaw in moments:

import random

from profit import best_profit_brute
from stress import random_lists


def best_profit_wrong(prices):
    """Looks O(n) and plausible, but it may sell before it buys."""
    return max(prices) - min(prices) if prices else 0


for count, prices in enumerate(random_lists(random.Random(7)), start=1):
    if best_profit_wrong(prices) != best_profit_brute(prices):
        print(f"Failed on list {count}: {prices}")
        print(f"brute force {best_profit_brute(prices)}, max minus min {best_profit_wrong(prices)}")
        break

Failed on list 204: [45, 23]
brute force 0, max minus min 22

In the list [45, 23] the price only falls, so the right answer is 0. Taking the highest minus the lowest sells at 45 on the first day and buys at 23 on the second: it sells before it buys. The printed input is the whole bug report, and it is small enough to trace by hand, because the test tried short lists first. Keep it as a test case. The next lesson of this module shows how to shrink a failing input that is not small.

The usual moves

Each move removes one kind of repeated work. Learn to name the waste first; the move follows from it.

• Carry a running value (precompute). The waste: recomputing a minimum, a maximum or a sum over a prefix that only grew by one item. The cue: “best so far” or “total so far” questions.
• Hash lookup. The waste: an inner loop that searches for a partner value. The cue: pairs that add up to a target, or “have I seen this before?”. A Python set or dict answers a lookup in O(1) time on average, according to the documentation’s table of time complexity.
• Prefix sums. The waste: adding up the same stretch of days again for every question about it. The cue: many queries for totals over ranges.
• Sort first. The waste: comparing every pair to find the ones that are close. The cue: closest values, repeats, or an answer that does not depend on the original order. Sorting costs O(n log n). If the answer needs the original positions, sort pairs of (value, position) instead of the values.
• Two pointers. On sorted data, one comparison can settle a whole group of pairs at once. The cue: pairs or triples with a condition on their sum, once the data is sorted.
• Binary search. The waste: scanning for the first place where a yes-or-no condition flips. The cue: sorted data, or a condition that only ever changes from no to yes as you move along (it is monotonic).
• Drop dominated options. The waste: re-checking candidates that can never win again. The cue: “next higher” or “best in a window” questions, solved with a stack or a queue that keeps only the candidates still in the running.

Here they are side by side. One list of 2,000 prices, eight questions about it, each answered by a brute force and by the move that removes its waste. Every version counts its basic operations, so the counts are the same on every computer:

import moves as m
from shared import N, Steps, prices

falling = sorted(prices, reverse=True)  # the worst case for question 7's brute force
QUESTIONS = [  # (question, move, brute force, fast version)
    ("Best profit from one buy and a later sell", "carry the lowest price",
     m.profit_brute, m.profit_fast),
    (f"Pairs of days adding up to exactly {m.TARGET:,}", "hash lookup",
     m.pair_sum_brute, m.pair_sum_fast),
    ("Totals over 1,000 ranges of days", "prefix sums",
     m.totals_brute, m.totals_fast),
    ("Smallest difference between two prices", "sort first",
     m.closest_brute, m.closest_fast),
    (f"Pairs of days adding up to at most {m.BUDGET:,}", "sort, then two pointers",
     m.within_brute, m.within_fast),
    ("First day the running total reaches each of 1,000 levels", "binary search",
     m.first_day_brute, m.first_day_fast),
    ("Days until a higher price, for every day", "drop dominated days",
     m.wait_brute, m.wait_fast),
    ("The same, with the prices sorted from high to low", "drop dominated days",
     lambda: m.wait_brute(falling), lambda: m.wait_fast(falling)),
]


def counted(solve):
    Steps.count = 0
    answer = solve()
    return answer, Steps.count


print(f"{N:,} daily prices")
for number, (question, move, brute, fast) in enumerate(QUESTIONS, start=1):
    slow_answer, slow_steps = counted(brute)
    fast_answer, fast_steps = counted(fast)
    same = "same answer" if slow_answer == fast_answer else "DIFFERENT ANSWERS"
    print(f"{number}. {question}")
    print(f"   {move}: {slow_steps:,} steps -> {fast_steps:,} steps, {same}")

2,000 daily prices
1. Best profit from one buy and a later sell
   carry the lowest price: 1,999,000 steps -> 2,000 steps, same answer
2. Pairs of days adding up to exactly 11,000
   hash lookup: 1,999,000 steps -> 2,000 steps, same answer
3. Totals over 1,000 ranges of days
   prefix sums: 668,256 steps -> 3,000 steps, same answer
4. Smallest difference between two prices
   sort first: 1,999,000 steps -> 21,335 steps, same answer
5. Pairs of days adding up to at most 8,000
   sort, then two pointers: 1,999,000 steps -> 21,335 steps, same answer
6. First day the running total reaches each of 1,000 levels
   binary search: 1,018,500 steps -> 12,980 steps, same answer
7. Days until a higher price, for every day
   drop dominated days: 13,623 steps -> 3,991 steps, same answer
8. The same, with the prices sorted from high to low
   drop dominated days: 1,999,000 steps -> 2,000 steps, same answer

from shared import LEVELS, N, RANGES, every_pair, prices, sorted_counted, tick

TARGET, BUDGET = 11_000, 8_000


# 1. The best profit from one buy and a later sell.
def profit_brute():
    return max([0] + [later - earlier for earlier, later in every_pair()])


def profit_fast():  # carry a running value: the lowest price so far
    best, lowest = 0, float("inf")
    for price in prices:
        tick()
        best, lowest = max(best, price - lowest), min(lowest, price)
    return best


# 2. How many pairs of days have prices that add up to exactly TARGET?
def pair_sum_brute():
    return sum(a + b == TARGET for a, b in every_pair())


def pair_sum_fast():  # hash lookup: how many earlier days had the price that completes this one?
    seen, count = {}, 0
    for price in prices:
        tick()
        count += seen.get(TARGET - price, 0)
        seen[price] = seen.get(price, 0) + 1
    return count


# 3. The total of the prices over each of 1,000 ranges of days.
def totals_brute():
    tick(sum(last - first + 1 for first, last in RANGES))  # one addition per day of each range
    return [sum(prices[first : last + 1]) for first, last in RANGES]


def totals_fast():  # prefix sums: running totals once, then one subtraction per range
    running = [0]
    for price in prices:
        tick()
        running.append(running[-1] + price)
    tick(len(RANGES))
    return [running[last + 1] - running[first] for first, last in RANGES]


# 4. The smallest difference between the prices of two days.
def closest_brute():
    return min(abs(a - b) for a, b in every_pair())


def closest_fast():  # sort first: the closest prices are then neighbours
    ordered = sorted_counted(prices)
    tick(N - 1)
    return min(b - a for a, b in zip(ordered, ordered[1:]))


# 5. How many pairs of days have prices adding up to at most BUDGET?
def within_brute():
    return sum(a + b <= BUDGET for a, b in every_pair())


def within_fast():  # sort, then two pointers: each step settles a whole group of pairs
    ordered = sorted_counted(prices)
    count, low, high = 0, 0, N - 1
    while low < high:
        tick()
        if ordered[low] + ordered[high] <= BUDGET:
            count += high - low  # ordered[low] fits with each of ordered[low + 1 .. high]
            low += 1
        else:
            high -= 1
    return count


# 6. For each of 1,000 levels, the first day on which the running total of prices reaches it.
def first_day_brute():
    days = []
    for level in LEVELS:
        total, day = prices[0], 0
        while total < level:
            tick()
            day += 1
            total += prices[day]
        days.append(day)
    return days


def first_day_fast():  # binary search: the running total only grows, so "reached yet?" flips once
    running, total = [], 0
    for price in prices:
        tick()
        total += price
        running.append(total)
    days = []
    for level in LEVELS:
        low, high = 0, N - 1  # the first day that reaches the level is in running[low..high]
        while low < high:
            tick()
            middle = (low + high) // 2
            if running[middle] >= level:
                high = middle
            else:
                low = middle + 1
        days.append(low)
    return days


# 7. For each day, how many days until a higher price (0 if none comes)?
def wait_brute(values=prices):
    waits = []
    for i in range(len(values)):
        wait = 0
        for j in range(i + 1, len(values)):
            tick()
            if values[j] > values[i]:
                wait = j - i
                break
        waits.append(wait)
    return waits


def wait_fast(values=prices):  # drop dominated days: the first higher price answers a waiting day
    waits, waiting = [0] * len(values), []  # waiting: the days still looking for a higher price
    for j, price in enumerate(values):
        while waiting and values[waiting[-1]] < price:
            tick()
            i = waiting.pop()
            waits[i] = j - i
        tick()
        waiting.append(j)
    return waits

"""The data every question uses, and the step counter.

One step is one basic operation: a comparison, a lookup or an addition."""
import random

rng = random.Random(42)
N = 2_000
prices = [rng.randint(1_000, 9_999) for _ in range(N)]
RANGES = [tuple(sorted(rng.sample(range(N), 2))) for _ in range(1_000)]  # (first, last) days
LEVELS = [rng.randint(1, sum(prices)) for _ in range(1_000)]


class Steps:
    count = 0


def tick(count=1):
    Steps.count += count


def every_pair(values=prices):
    """What most brute forces do: visit every pair of days, one step each."""
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            tick()
            yield values[i], values[j]


class _Counted:
    def __init__(self, value):
        self.value = value

    def __lt__(self, other):  # sorted() compares with < only, so this counts every comparison
        tick()
        return self.value < other.value


def sorted_counted(values):
    return [c.value for c in sorted(_Counted(v) for v in values)]

Each pair of lines is one question, then the move with the brute force’s steps and the fast version’s steps. Every row says “same answer”, so each fast version was checked against its brute force on these 2,000 prices. Three things are worth noticing:

• Most rows drop from between about 670,000 and 2,000,000 steps to between 2,000 and about 21,000. The four questions about pairs of days all start from the same every-pair loop, every_pair in shared.py, which is why their brute forces cost exactly n(n − 1)/2 = 1,999,000 steps.
• Sorting is not free. Rows 4 and 5 pay about 19,000 comparisons for the sort before they save anything. That is the O(n log n) the sort costs, and still nearly a hundred times fewer steps than the pairs.
• A brute force’s cost can depend on the data. In row 7 the brute force is quick, because on random prices a higher one usually comes within a few days. Row 8 asks the same question about the prices sorted from high to low, where it never comes: the brute force does all 1,999,000 comparisons, while the stack does at most two operations per day on any input.

This style of step-by-step improvement is old. In Jon Bentley’s book Programming Pearls, the column “Algorithm Design Techniques” takes one problem from a simple algorithm through two quadratic ones and a divide-and-conquer one to a single scan, and several of the faster versions get their speed by not recomputing what an earlier one already knew.

Say why each move is safe

In a live round, an optimisation is not finished when the code is faster; it is finished when you have said why the answer did not change. One sentence each is enough: the waste you removed, the move, the new cost, and why nothing was lost. For this lesson’s problem: “The inner loop searches all earlier days for the lowest price again for every sell day. I’ll carry the lowest price so far instead, which makes it one pass, O(n). It’s still right because a higher earlier price can never be a better day to buy.” Then run the stress test, if the round lets you run code.

Key takeaways

• Write the brute force first, quickly, and keep it: it is a specification you can run.
• To optimise, name the work the brute force repeats, then pick the move that does it once: a running value, a hash lookup, prefix sums, sorting, two pointers, binary search, or dropping dominated options.
• Check the fast version with a stress test: many small random inputs from a fixed seed, shortest first, compared with the brute force.
• Say why each move is safe, in one sentence: what you removed, the new cost, and why the answer is unchanged.