Brute-force baselines

How do you choose an approach?

Choosing an approach means connecting the problem’s required operations to the structures and algorithms you have learned. Start with the input, the requested output, and the constraints. Build a simple correct solution, identify its expensive work, and look for a structure that avoids repeating it.

Example: If a solution repeatedly scans earlier values to ask “have I seen this before?”, consider a set. If it repeatedly sums fixed ranges in unchanged data, consider prefix sums. Explain why the chosen approach fits before writing code.

Understand the idea

A brute-force baseline makes the specification executable. Keep it simple and independent of the optimized implementation. Reuse partial arithmetic without hiding the enumeration logic; this can reduce a cubic baseline to quadratic.

Work through an example

The lab fixes left and extends right with a running sum. It checks every nonempty subarray once in O(n²), rather than summing each slice in O(n³).

Time and space complexity

Θ(n²) time/O(1) auxiliary state for brute_count, under bounded arithmetic.

Why it works

Every boundary pair left≤right is visited exactly once.

Common mistakes

An overly complicated oracle can share the optimized bug.
Empty subarrays are excluded here.

Chapter lab · Python implementation

Interview readiness means selecting an approach without a chapter label. The lab compares an obvious quadratic subarray-sum baseline with prefix hashing on exhaustive small inputs. Work from a contract, articulate why the optimized state is sufficient, then use counterexamples and delayed review to expose fragile reasoning.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from itertools import product

def brute_count(values,target):
    count=0
    for left in range(len(values)):
        total=0
        for right in range(left,len(values)):
            total+=values[right]
            count+=total==target
    return count

def fast_count(values,target):
    frequencies={0:1}; prefix=answer=0
    for x in values:
        prefix+=x
        answer+=frequencies.get(prefix-target,0)
        frequencies[prefix]=frequencies.get(prefix,0)+1
    return answer

def verify_small():
    cases=0
    for length in range(5):
        for values in product([-1,0,1],repeat=length):
            for target in range(-2,3):
                assert brute_count(values,target)==fast_count(values,target)
                cases+=1
    return cases

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert verify_small()==605
assert fast_count([1,-1,1],1)==3
assert brute_count([],0)==0

CHECK YOUR UNDERSTANDING