Find the Middle Index in Array

Difficulty: Easy | Acceptance: 69.60% | Paid: No Topics: Array, Prefix Sum

Given a 0-indexed integer array nums, find the leftmost middleIndex (i.e., the smallest amongst all the possible ones).

A middleIndex is an index where the sum of all the numbers strictly to its left is equal to the sum of all the numbers strictly to its right.

If the sum to the left is 0, it is valid. If the sum to the right is 0, it is valid.

If no such index exists, return -1.

• Examples
• Constraints
• Brute Force
• Prefix Sum

Examples

Example 1:

Input: nums = [2,3,-1,8,4]
Output: 3
Explanation:
The middle index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 2 + 3 + -1 = 4
Right sum = nums[4] = 4

Example 2:

Input: nums = [1,-1,4]
Output: 2
Explanation:
The middle index is 2.
Left sum = nums[0] + nums[1] = 1 + -1 = 0
Right sum = 0

Example 3:

Input: nums = [2,5]
Output: -1
Explanation:
There is no valid middle index.

Constraints

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

Brute Force

Intuition Iterate through each index and calculate the sum of elements to the left and right separately to check for equality.

Steps

• Iterate through the array with index i from 0 to n-1.
• Calculate the sum of elements from index 0 to i-1 (left sum).
• Calculate the sum of elements from index i+1 to n-1 (right sum).
• If left sum equals right sum, return i.
• If the loop finishes without finding a valid index, return -1.

from typing import List

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            left_sum = sum(nums[:i])
            right_sum = sum(nums[i+1:])
            if left_sum == right_sum:
                return i
        return -1

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple to implement but inefficient for large arrays due to repeated summation.

Prefix Sum

Intuition Calculate the total sum of the array once. As we iterate, maintain a running left sum. The right sum can be derived by subtracting the left sum and the current element from the total sum.

Steps

• Calculate the total sum of the array.
• Initialize leftSum to 0.
• Iterate through the array:
  • Calculate rightSum as totalSum - leftSum - nums[i].
  • If leftSum equals rightSum, return i.
  • Add nums[i] to leftSum.
• If the loop completes, return -1.

from typing import List

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with a single pass through the array.