LeetCode Problem 1991

Difficulty: 🟢 Easy
Topics: Array, Prefix Sum

Solution

LeetCode 1991 - Find the Middle Index in Array

Problem Understanding

The problem gives us a 0-indexed integer array called nums. We need to find an index such that the sum of all elements to the left of that index is equal to the sum of all elements to the right of that index.

More formally, for an index i:

• Left sum = nums[0] + nums[1] + ... + nums[i-1]
• Right sum = nums[i+1] + nums[i+2] + ... + nums[n-1]

If these two sums are equal, then i is considered a valid middle index.

The problem specifically asks for the leftmost valid index, meaning if multiple indices satisfy the condition, we return the smallest one. If no valid index exists, we return -1.

An important detail is how edge positions are handled:

• If i == 0, the left side contains no elements, so the left sum is 0
• If i == n - 1, the right side contains no elements, so the right sum is 0

The constraints are relatively small:

• 1 <= nums.length <= 100
• -1000 <= nums[i] <= 1000

Even though the input size is small enough for a brute-force solution to pass, the problem is fundamentally a prefix sum problem, and there is a clean linear-time solution that is more efficient and elegant.

There are several edge cases that can easily cause mistakes:

• Arrays with only one element
• Arrays where the middle index is at position 0
• Arrays where the middle index is at the last position
• Arrays containing negative numbers
• Arrays with multiple valid middle indices, where only the leftmost should be returned
• Arrays with no valid answer

A correct implementation must handle all of these scenarios carefully.

Approaches

Brute-Force Approach

The most straightforward solution is to check every index individually.

For each index i, we calculate:

• The sum of all elements before i
• The sum of all elements after i

If the two sums are equal, we immediately return i.

This approach is correct because it directly follows the problem definition. Every possible index is examined, and the first valid one is returned.

However, the inefficiency comes from repeatedly recalculating sums. For every index, we may scan large portions of the array again. If the array length is n, then each index may require O(n) work, leading to an overall complexity of O(n²).

Although the constraints are small enough that this solution works in practice, it is not optimal.

Optimal Prefix Sum Approach

The key observation is that we do not need to recompute sums repeatedly.

If we know:

• The total sum of the array
• The running sum of elements to the left

Then we can compute the right sum instantly.

Suppose:

• left_sum is the sum of elements before index i
• total_sum is the sum of the entire array
• nums[i] is the current element

Then:

right_sum = total_sum - left_sum - nums[i]

This works because:

• total_sum contains everything
• subtract left_sum to remove the left side
• subtract nums[i] to remove the current element
• the remaining value is the right side sum

Now we can determine whether index i is valid in constant time.

This reduces the total complexity to O(n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recalculates left and right sums for every index
Optimal	O(n)	O(1)	Uses running prefix sum and total sum

Algorithm Walkthrough

Optimal Prefix Sum Algorithm

1. Compute the total sum of the array using sum(nums).

This gives us the sum of every element in the array. We will use it to derive the right-side sum efficiently. 2. Initialize a variable called left_sum to 0.

Before we begin iterating, there are no elements to the left of index 0. 3. Iterate through the array using both index and value.

At each position, we want to determine whether the current index satisfies the middle index condition. 4. Compute the right-side sum.

The formula is:

right_sum = total_sum - left_sum - current_value

This removes the left portion and current element from the total, leaving only the right side. 5. Compare left_sum and right_sum.

If they are equal, return the current index immediately.

Since we iterate from left to right, the first valid index found is automatically the leftmost valid answer. 6. Update left_sum.

Add the current value to left_sum before moving to the next iteration. 7. If the loop finishes without finding a valid index, return -1.

Why it works

The algorithm maintains an important invariant:

• Before processing index i, left_sum always equals the sum of all elements strictly to the left of i.

Using the total sum, we can derive the exact right-side sum in constant time. Since every index is checked exactly once and the first valid index is returned immediately, the algorithm correctly finds the leftmost middle index.

Python Solution

from typing import List

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0

        for index, value in enumerate(nums):
            right_sum = total_sum - left_sum - value

            if left_sum == right_sum:
                return index

            left_sum += value

        return -1

The implementation begins by computing the total sum of the array. This allows the algorithm to derive the right-side sum without repeatedly scanning the array.

The variable left_sum tracks the cumulative sum of elements before the current index. Initially, it is 0 because there are no elements to the left of index 0.

The loop processes each element exactly once. For every position, the code computes the right-side sum using the formula:

right_sum = total_sum - left_sum - value

If the left and right sums match, the current index is returned immediately. Because the iteration proceeds from left to right, this guarantees the returned index is the leftmost valid answer.

After checking the condition, the current value is added to left_sum so that it correctly represents the left-side sum for the next iteration.

If no valid index is found, the function returns -1.

Go Solution

func findMiddleIndex(nums []int) int {
    totalSum := 0

    for _, value := range nums {
        totalSum += value
    }

    leftSum := 0

    for index, value := range nums {
        rightSum := totalSum - leftSum - value

        if leftSum == rightSum {
            return index
        }

        leftSum += value
    }

    return -1
}

The Go implementation follows the exact same logic as the Python solution.

Since Go does not provide a built-in sum() function for slices, the total sum is computed manually using a loop.

Go slices are reference-based structures, but since the algorithm only reads values and uses a few integer variables, no additional memory allocation is required beyond constant space.

The constraints are small, so integer overflow is not a concern in this problem.

Worked Examples

Example 1

Input: nums = [2,3,-1,8,4]

First compute:

total_sum = 2 + 3 + (-1) + 8 + 4 = 16

Initial state:

left_sum = 0

Index	Value	Left Sum	Right Sum Calculation	Right Sum	Equal?
0	2	0	16 - 0 - 2	14	No
1	3	2	16 - 2 - 3	11	No
2	-1	5	16 - 5 - (-1)	12	No
3	8	4	16 - 4 - 8	4	Yes

At index 3, the left and right sums are both 4, so the algorithm returns 3.

Example 2

Input: nums = [1,-1,4]

Compute total sum:

total_sum = 4

Initial:

left_sum = 0

Index	Value	Left Sum	Right Sum Calculation	Right Sum	Equal?
0	1	0	4 - 0 - 1	3	No
1	-1	1	4 - 1 - (-1)	4	No
2	4	0	4 - 0 - 4	0	Yes

At index 2, both sides equal 0, so the answer is 2.

Example 3

Input: nums = [2,5]

Compute total sum:

total_sum = 7

Index	Value	Left Sum	Right Sum	Equal?
0	2	0	5	No
1	5	2	0	No

No valid index exists, so the algorithm returns -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is traversed once after computing the total sum
Space	O(1)	Only a few integer variables are used

The algorithm performs two linear passes over the array:

• One pass to compute the total sum
• One pass to find the middle index

Since both passes are linear, the overall time complexity remains O(n).

The algorithm does not use any auxiliary data structures proportional to input size, so the space complexity is constant.

Test Cases

from typing import List

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0

        for index, value in enumerate(nums):
            right_sum = total_sum - left_sum - value

            if left_sum == right_sum:
                return index

            left_sum += value

        return -1

solution = Solution()

assert solution.findMiddleIndex([2, 3, -1, 8, 4]) == 3  # provided example
assert solution.findMiddleIndex([1, -1, 4]) == 2  # valid at last index
assert solution.findMiddleIndex([2, 5]) == -1  # no valid middle index

assert solution.findMiddleIndex([1]) == 0  # single element array
assert solution.findMiddleIndex([0, 0, 0]) == 0  # multiple valid answers, return leftmost
assert solution.findMiddleIndex([2, 1, -1]) == 0  # valid at first index
assert solution.findMiddleIndex([-1, -1, -1, 0, 1, 1]) == 0  # negative numbers
assert solution.findMiddleIndex([1, 2, 3, 4, 6]) == 3  # standard middle case
assert solution.findMiddleIndex([0]) == 0  # single zero element
assert solution.findMiddleIndex([1, 2, 3]) == -1  # impossible case
assert solution.findMiddleIndex([10, -10, 10, -10, 10, -10, 0]) == 6  # alternating values

Test	Why
[2,3,-1,8,4]	Valid middle index in the middle of array
[1,-1,4]	Valid middle index at last position
[2,5]	No valid answer exists
[1]	Single element edge case
[0,0,0]	Multiple valid answers, must return leftmost
[2,1,-1]	Valid index at position 0
[-1,-1,-1,0,1,1]	Handles negative numbers correctly
[1,2,3,4,6]	Standard non-trivial balanced case
[0]	Single zero element
[1,2,3]	Simple impossible case
[10,-10,10,-10,10,-10,0]	Stress test with alternating values

Edge Cases

Single Element Array

An array containing only one element is a very important boundary case. For example:

[5]

At index 0, there are no elements on either side, so both left and right sums are 0. The correct answer is therefore 0.

A buggy implementation might incorrectly assume both sides must contain elements. The current solution handles this naturally because:

right_sum = total_sum - left_sum - value

becomes:

5 - 0 - 5 = 0

which matches the left sum.

Middle Index at the Beginning

Consider:

[2, 1, -1]

At index 0:

• Left sum = 0
• Right sum = 1 + (-1) = 0

The answer should therefore be 0.

This case can expose off-by-one errors, especially if the implementation incorrectly includes the current element in the left-side calculation. The solution avoids this by updating left_sum only after checking the current index.

Multiple Valid Middle Indices

Consider:

[0, 0, 0]

Every index satisfies the condition because both left and right sums are always 0.

However, the problem requires the leftmost valid index, which is 0.

The implementation handles this correctly because it iterates from left to right and immediately returns the first valid index encountered.

Arrays with Negative Numbers

Negative values can make balancing conditions less intuitive. For example:

[-1, -1, -1, 0, 1, 1]

The valid answer is 0.

A naive intuition might assume sums must grow monotonically, but negative numbers invalidate that assumption. The prefix-sum approach remains fully correct because it uses exact arithmetic rather than relying on ordering properties.