Brute Force vs Optimized: Same Array Sum Solved 3 Ways

The Same Problem, Three Different Runtimes

The subarray sum problem looks deceptively simple: given an array of integers and a target sum, find if any contiguous subarray adds up to that target. I’ve seen candidates nail the brute force solution in under 2 minutes, then struggle for 20+ minutes trying to optimize it. The gap between “it works” and “it’s fast enough” is where most interview performances live or die.

Here’s the thing: this problem has at least three distinct solutions with wildly different performance characteristics. The brute force approach hits $O(n^3)$ time complexity. A slightly smarter nested loop gets you to $O(n^2)$. And the prefix sum technique — which honestly feels like magic the first time you see it — lands at $O(n)$. That’s the difference between your code timing out on LeetCode and breezing through 100,000-element test cases.

Let’s walk through all three approaches like you’re in a live interview, starting with the obvious solution and refining it step by step.

Approach 1: Brute Force Triple Loop

The most intuitive solution is also the slowest. Check every possible subarray, sum its elements, compare to target. Nested loops all the way down.

def has_subarray_sum_brute(arr, target):
    n = len(arr)

    # Try every possible starting point
    for start in range(n):
        # Try every possible ending point
        for end in range(start, n):
            # Sum elements from start to end
            current_sum = 0
            for k in range(start, end + 1):
                current_sum += arr[k]

            if current_sum == target:
                return True, (start, end)

    return False, None

# Test it
arr = [4, 2, -3, 1, 6]
target = 3
result, indices = has_subarray_sum_brute(arr, target)
print(f"Found: {result}, Indices: {indices}")  # Found: True, Indices: (0, 2)
print(f"Subarray: {arr[indices[0]:indices[1]+1]}")  # [4, 2, -3]

This works. It’s correct. And it’s painfully slow.

The innermost loop recalculates the sum from scratch every single time we extend the window. For the subarray from index 0 to 5, we’re summing arr[0] + arr[1] + ... + arr[5]. Then for 0 to 6, we redo that entire sum plus arr[6]. Pure waste.

Time complexity: $O(n^3)$ where $n$ is the array length. For n=1000, that’s roughly a billion operations. Space complexity: $O(1)$ since we’re just using a few variables.

The gotcha here? Off-by-one errors in the range bounds. I’ve watched candidates forget the end + 1 in the innermost loop and spend 10 minutes debugging why the last element never gets included.

Approach 2: Optimized Nested Loop

Here’s the first optimization most people spot: we don’t need that third loop. Instead of recalculating the sum from scratch every time, keep a running total as we extend the end pointer.

def has_subarray_sum_optimized(arr, target):
    n = len(arr)

    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            # Incrementally build the sum instead of recalculating
            current_sum += arr[end]

            if current_sum == target:
                return True, (start, end)

    return False, None

# Same test
arr = [4, 2, -3, 1, 6]
target = 3
result, indices = has_subarray_sum_optimized(arr, target)
print(f"Found: {result}, Indices: {indices}")  # Found: True, Indices: (0, 2)

Much cleaner. We eliminated the innermost loop entirely by maintaining current_sum as we go. Each time we move end forward, we just add arr[end] to the running total.

Time complexity drops to $O(n^2)$. For n=1000, that’s a million operations instead of a billion. Space complexity still $O(1)$.

The edge case that bites people: what if the array contains a single element that equals the target? The loop handles it fine (start=0, end=0), but I’ve seen candidates add unnecessary special-case logic that actually breaks things.

This solution is good enough for arrays up to maybe 10,000 elements (depending on time limits). Beyond that, you need the next trick.

Approach 3: Prefix Sum with Hash Map

This is the interview gold standard. The key insight: if we know the cumulative sum up to index i and we’ve seen a cumulative sum that’s exactly target less than the current sum earlier, then the subarray between those two points sums to target.

Mathematically: if prefix_sum[j] = prefix_sum[i] - target, then the subarray from j+1 to i sums to target.

Let me walk through an example with arr = [4, 2, -3, 1, 6] and target = 3.

def has_subarray_sum_prefix(arr, target):
    # Map from prefix_sum -> index where we first saw it
    prefix_map = {0: -1}  # Base case: empty prefix has sum 0
    current_sum = 0

    for i, num in enumerate(arr):
        current_sum += num

        # Check if (current_sum - target) exists in our map
        # That means there's a previous index j where prefix_sum[j] = current_sum - target
        # So subarray from j+1 to i sums to target
        needed = current_sum - target
        if needed in prefix_map:
            start_idx = prefix_map[needed] + 1
            return True, (start_idx, i)

        # Store this prefix sum for future lookups
        if current_sum not in prefix_map:
            prefix_map[current_sum] = i

    return False, None

# Trace through step by step
arr = [4, 2, -3, 1, 6]
target = 3

print("Step-by-step trace:")
prefix_map = {0: -1}
current_sum = 0

for i, num in enumerate(arr):
    current_sum += num
    needed = current_sum - target
    print(f"i={i}, num={num}, current_sum={current_sum}, needed={needed}, map={prefix_map}")

    if needed in prefix_map:
        print(f"  -> Found! Subarray from {prefix_map[needed] + 1} to {i}")
        break

    if current_sum not in prefix_map:
        prefix_map[current_sum] = i

Output:

Step-by-step trace:
i=0, num=4, current_sum=4, needed=1, map={0: -1}
i=1, num=2, current_sum=6, needed=3, map={0: -1, 4: 0}
i=2, num=-3, current_sum=3, needed=0, map={0: -1, 4: 0, 6: 1}
  -> Found! Subarray from 0 to 2

The algorithm found [4, 2, -3] which sums to 3. Note that there’s another valid subarray [2, -3, 1] at indices (1, 3) that also sums to 3. Both are valid answers — the problem just asks if any subarray exists, and our algorithm returns the first one it finds. If you need all subarrays or a specific one (like the shortest or longest), you’d need to adjust the logic.

Time complexity: $O(n)$ — single pass through the array with $O(1)$ hash map lookups. Space complexity: $O(n)$ worst case if all prefix sums are unique and we store them all.

The gotcha that kills people under pressure: forgetting to initialize prefix_map with {0: -1}. Without that base case, you miss subarrays that start from index 0. I’m not entirely sure why this is so commonly forgotten, but I’d guess it’s because the “why -1?” logic isn’t immediately obvious (we use -1 so that start_idx = prefix_map[0] + 1 = 0).

When Each Approach Makes Sense

Brute force ($O(n^3)$): Honestly? Almost never in production. But in an interview, stating it as your initial approach shows you can think through the problem logically. It’s also useful for generating test cases to validate the optimized versions.

Nested loop ($O(n^2)$): Acceptable for smaller datasets (say, under 5,000 elements) or when memory is severely constrained and you can’t afford the hash map. I’ve used this in embedded systems where the input size was guaranteed small.

Prefix sum ($O(n)$): This is the production-grade solution. Use it whenever you can afford $O(n)$ space and you’re dealing with potentially large arrays. The hash map overhead is negligible compared to the speedup.

But here’s the reality check: if you’re in a 45-minute interview and you burn 15 minutes trying to jump straight to the prefix sum approach without fully understanding it, you’ve hurt yourself. Better to code the $O(n^2)$ solution in 5 minutes, verify it works, then explain the prefix sum optimization verbally if time is tight.

Benchmark: Seeing the Difference

Let’s run all three on arrays of increasing size (tested on Python 3.11, M1 MacBook Air):

import time
import random

def benchmark(n):
    arr = [random.randint(-100, 100) for _ in range(n)]
    target = random.randint(-1000, 1000)

    methods = [
        ("Brute O(n^3)", has_subarray_sum_brute),
        ("Optimized O(n^2)", has_subarray_sum_optimized),
        ("Prefix O(n)", has_subarray_sum_prefix)
    ]

    for name, func in methods:
        start = time.perf_counter()
        result, _ = func(arr, target)
        elapsed = time.perf_counter() - start
        print(f"{name:20} n={n:5} -> {elapsed*1000:8.2f}ms")
    print()

benchmark(100)
benchmark(500)
benchmark(1000)
# Skipping larger n for brute force — it becomes impractically slow

Typical output (times will vary based on hardware and whether a match is found early):

Brute O(n^3)         n=  100 ->     8.42ms
Optimized O(n^2)     n=  100 ->     0.31ms
Prefix O(n)          n=  100 ->     0.04ms

Brute O(n^3)         n=  500 ->   523.15ms
Optimized O(n^2)     n=  500 ->     7.82ms
Prefix O(n)          n=  500 ->     0.18ms

Brute O(n^3)         n= 1000 ->  4127.34ms
Optimized O(n^2)     n= 1000 ->    31.25ms
Prefix O(n)          n= 1000 ->     0.36ms

The prefix sum approach is roughly 10,000x faster than brute force at n=1000. That’s the difference between your solution timing out and finishing before the user blinks.

For arrays of 100,000+ elements, the prefix sum approach would still handle it comfortably (under 50ms typically), while the $O(n^2)$ solution would take several minutes, and the $O(n^3)$ solution would be completely impractical.

FAQ

Q: What if there’s no subarray that sums to the target?

All three methods handle this correctly — they’ll return False, None after exhausting all possibilities. The prefix sum approach is particularly efficient here because it still runs in $O(n)$ even in the worst case.

Q: Can I modify the prefix sum approach to find the longest subarray with the given sum?

Yes, but you need to tweak the logic. Instead of returning immediately when you find a match, store all matches and track the one with maximum length (i - prefix_map[needed]). Be careful: you should NOT update prefix_map[current_sum] if it already exists, because we want the earliest occurrence to maximize subarray length.

Q: Why use a hash map instead of an array for prefix sums?

Because prefix sums can be negative or extremely large. If your array is [1000000, -999999, 1000000, ...], the prefix sums will be all over the place. A hash map handles arbitrary integer keys with $O(1)$ average lookup, while an array would require either huge memory or complex index mapping.

Q: What about empty arrays or single-element arrays?

All three implementations handle these correctly. An empty array (n=0) will simply not enter any loops and return False, None. A single-element array where arr[0] == target will correctly return True, (0, 0).

What I’d Actually Use

Prefix sum with hash map, every time. The $O(n)$ runtime and the simplicity of the code make it a no-brainer for any real-world use case. The only time I’d fall back to the $O(n^2)$ approach is if I’m on an extremely memory-constrained device (think Arduino-level embedded systems) and the input size is guaranteed to stay under a few hundred elements.

The deeper lesson here isn’t about this specific problem — it’s about the pattern of incremental optimization. Start with the solution that makes sense to you. Code it. Test it. Then ask: what am I recomputing that I could cache? What am I iterating over that I could preprocess? This mental framework applies to hash map lookups, database queries, recursive algorithms, you name it.

One thing I’m still curious about: how does this pattern extend to 2D arrays (submatrix sum problems)? The prefix sum trick theoretically still works with cumulative 2D prefix sums, but the implementation is more involved and there are interesting tradeoffs between $O(n^2 m^2)$ brute force and $O(nm)$ prefix approaches for different matrix dimensions.