Find the Middle Index in Array: Prefix Sum in One Pass

LeetCode 1991: Find the Middle Index in Array asks you to find the leftmost index in a 0-indexed array where the sum of all elements to the left equals the sum of all elements to the right. The element at that index is not included in either sum. If no such index exists, return -1.

For example, given nums = [2, 3, -1, 8, 4], the answer is index 3. Elements to the left of index 3 are [2, 3, -1] with sum 4. Elements to the right are [4] with sum 4. They match.

This is an easy problem, but the technique behind it (prefix sums) is a building block you will use in dozens of harder problems. Getting it clean here means you will recognize it instantly later.

The brute force trap

The obvious approach is to check every index. For each candidate i, sum up everything to its left, then sum up everything to its right, and compare. That works but it is O(n^2) because you are recomputing sums from scratch at every index.

def find_middle_index_brute(nums):
    for i in range(len(nums)):
        left = sum(nums[:i])
        right = sum(nums[i + 1:])
        if left == right:
            return i
    return -1

For small inputs this is fine. But when the array has 1,000 elements, you are doing up to 500,000 additions. There is a much better way.

The key insight: you do not need to recompute

Here is the trick. Before you start scanning, compute the total sum of the array once. Then as you walk left to right, maintain a running left_sum. At each index i, the right sum is just:

right_sum = total - left_sum - nums[i]

You do not need to add anything up on the right side. You already know the total, you know what is on the left, and you know what is at index i. Subtraction gives you the rest.

If left_sum == right_sum, you found your middle index. Otherwise, add nums[i] to left_sum and move on.

The solution

def find_middle_index(nums):
    total = sum(nums)
    left_sum = 0

    for i in range(len(nums)):
        right_sum = total - left_sum - nums[i]
        if left_sum == right_sum:
            return i
        left_sum += nums[i]

    return -1

That is the entire solution. Let's break it down:

1. Compute total = sum(nums) in one pass.
2. Initialize left_sum = 0 (nothing to the left of index 0).
3. For each index i, calculate right_sum by subtracting left_sum and nums[i] from total.
4. If left_sum == right_sum, return i. This is the leftmost middle index because we scan left to right.
5. Otherwise, add nums[i] to left_sum and continue.
6. If the loop finishes without finding a match, return -1.

Step-by-step walkthrough

Let's trace through nums = [2, 3, -1, 8, 4] with total = 16. At each step we check whether left_sum equals right_sum.

At index 3, left_sum = 4 and right_sum = 16 - 4 - 8 = 4. They match, so we return 3. We never even need to check index 4.

Complexity analysis

Time: O(n). One pass to compute the total, one pass to find the middle index. Each pass does O(1) work per element. Total: O(n).

Space: O(1). Two variables (left_sum and total), no extra arrays.

This is optimal. You have to look at every element at least once to know the total, so O(n) is the floor.

The building blocks

This problem uses one core technique that shows up across many array problems:

Running prefix sum

The idea of maintaining a cumulative sum as you iterate through an array. At index i, left_sum holds the sum of nums[0..i-1]. You update it incrementally by adding nums[i] after each step. This avoids recomputing sums from scratch and turns O(n^2) brute force into O(n).

left_sum = 0
for i in range(len(nums)):
    # left_sum holds sum of nums[0..i-1]
    left_sum += nums[i]
    # now left_sum holds sum of nums[0..i]

This same brick powers problems like Maximum Subarray (Kadane's running sum), Product of Array Except Self (running product instead of sum), and subarray sum problems where you use a prefix sum with a hash map.

Deriving the complement from the total

Instead of computing both sides independently, you compute one side and derive the other from the total. This is the same idea behind Two Sum (looking for target - num instead of checking all pairs) and many partition problems. When you know the whole and one part, the other part is free.

Edge cases

Before you submit, make sure your solution handles these:

• Single element [5]: left_sum = 0, right_sum = 5 - 0 - 5 = 0. They match, so return 0. An array with one element always has a middle index at 0.
• All zeros [0, 0, 0]: every index is a valid middle index. Return 0 (the leftmost).
• No valid index [1, 2, 3]: no index where left sum equals right sum. Return -1.
• Middle index at the edges: for [3, 0], index 0 gives left_sum = 0 and right_sum = 3 - 0 - 3 = 0. Match. The middle index can be the first or last element.
• Negative numbers: the algorithm handles negatives naturally. No special cases needed.

From understanding to recall

You have just walked through a clean one-pass prefix sum solution. The logic is simple and the code is short. But "simple" does not mean "automatic." In an interview, you need to remember the exact formula for right_sum, the correct update order (check before updating left_sum), and what to return when no index works.

Spaced repetition bridges the gap between understanding and recall. You solve this problem today, then revisit it in a few days, then a week later, then two weeks. Each time you write the solution from scratch. After a few cycles, the prefix sum pattern and the derive-the-complement trick are locked in muscle memory.

The running prefix sum is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling the brick itself, not just one problem that uses it, builds permanent recall that transfers to new problems.

Related posts

• Maximum Subarray - Kadane's algorithm uses a similar running sum technique, making an extend-or-restart decision at each index
• Product of Array Except Self - The same "derive one side from the total" idea, applied to products with a two-pass approach
• Contains Duplicate - Another easy array problem that teaches a fundamental pattern (hash set) you will reuse everywhere