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.

python
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

---

*Continue reading the full article on [TildAlice](https://tildalice.io/brute-force-vs-optimized-array-sum-3-ways/)*