#1991

Easy

LeetCode Problem Workspace

Find the Middle Index in Array

Find the smallest middle index where the sum of elements on the left equals the sum on the right using prefix sums efficiently.

array prefix sum

Problem Statement

Given a 0-indexed integer array nums, find the leftmost middle index where the sum of all elements before it equals the sum of all elements after it. If multiple indices satisfy this condition, return the smallest one.

A middle index is defined such that the sum of nums[0] to nums[middleIndex - 1] is equal to the sum of nums[middleIndex + 1] to nums[nums.length - 1]. For the first index, the left sum is considered 0, and for the last index, the right sum is considered 0.

Examples

Example 1

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

Output: 3

The sum of the numbers before index 3 is: 2 + 3 + -1 = 4 The sum of the numbers after index 3 is: 4 = 4

Example 2

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

Output: 2

The sum of the numbers before index 2 is: 1 + -1 = 0 The sum of the numbers after index 2 is: 0

Example 3

Input: nums = [2,5]

Output: -1

There is no valid middleIndex.

Constraints

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

Solution Approach

Calculate Total and Track Left Sum

Compute the total sum of the array first. Then iterate through each element, maintaining a left sum that accumulates elements from the start. At each step, compare the left sum with total sum minus left sum minus current element to find the middle index.

Linear Pass with Early Exit

By using a single linear pass, you can immediately return the first index that balances left and right sums. This ensures the solution handles the leftmost requirement and avoids unnecessary computation for the rest of the array.

Handle Edge Cases

Check boundary conditions explicitly: if the first index satisfies the balance, left sum is 0; if the last index does, right sum is 0. This prevents off-by-one errors and ensures correctness for arrays with minimal or negative elements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to a single pass through the array, and space complexity is O(1) since only cumulative sums are stored, making it efficient for the given constraints.

What Interviewers Usually Probe

Look for a solution using a single left-to-right traversal with running sums.
Be careful with the first and last index where one side sum is zero.
Discuss how prefix sum logic reduces repeated summation calculations.

Common Pitfalls or Variants

Common pitfalls

Calculating left and right sums separately at each index, leading to O(n^2) time.
Ignoring the requirement to return the leftmost middle index first.
Off-by-one errors when handling the first or last index sums.

Follow-up variants

Find all middle indices instead of only the leftmost one.
Consider arrays with floating-point numbers requiring precision checks.
Modify the problem to find middle index where left sum is greater than right sum by a fixed difference.

FAQ

What exactly is a middle index in this problem?

A middle index is one where the sum of elements before it equals the sum after it, considering 0 for sums outside array bounds.

Can negative numbers affect the solution?

Yes, negative numbers are valid, but the prefix sum approach still correctly identifies balance regardless of sign.

Why return the leftmost middle index?

The problem specifies leftmost to ensure a unique answer when multiple indices satisfy the sum equality.

What is the best time complexity for this problem?

O(n) is optimal by using a single pass with a running left sum and the total sum of the array.

Does this problem always require prefix sums?

Using a running sum is the most efficient approach, though conceptually you are leveraging the prefix sum pattern to avoid repeated summation.

terminal

Solution

Solution 1: Prefix Sum

We define two variables $l$ and $r$, representing the sum of elements to the left and right of index $i$ in the array $\textit{nums}$, respectively. Initially, $l = 0$ and $r = \sum_{i = 0}^{n - 1} \textit{nums}[i]$.

1

2

3

4

5

6

7

8

9

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        l, r = 0, sum(nums)
        for i, x in enumerate(nums):
            r -= x
            if l == r:
                return i
            l += x
        return -1

Continue Practicing

#2017 grid game #2025 maximum number of ways to partition an array #1943 describe the painting