Find the Middle Index in Array

EASY

Description

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 nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1].

If middleIndex == 0, the left side sum is considered to be 0. Similarly, if middleIndex == nums.length - 1, the right side sum is considered to be 0.

Return the leftmost middleIndex that satisfies the condition, or -1 if there is no such index.

Example 1:

Input: nums = [2,3,-1,8,4]
Output: 3
Explanation: 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
Explanation: 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
Explanation: There is no valid middleIndex.

Constraints:

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

Note: This question is the same as 724: https://leetcode.com/problems/find-pivot-index/

Approaches

Checkout 2 different approaches to solve Find the Middle Index in Array. Click on different approaches to view the approach and algorithm in detail.

Optimized Approach using Prefix Sum

This approach significantly improves performance by avoiding recalculations. It first computes the total sum of the array. Then, it iterates through the array once more, maintaining a running leftSum. The rightSum can be calculated in constant time using the totalSum and the current leftSum.

Algorithm

First, iterate through the entire array once to calculate the totalSum of all its elements.
Initialize a leftSum variable to 0.
Iterate through the array again with an index i from 0 to nums.length - 1.
In each iteration, the rightSum can be calculated without a new loop: rightSum = totalSum - leftSum - nums[i].
Check if leftSum == rightSum. If they are equal, i is the middle index. Return i.
If the condition is not met, update leftSum for the next iteration by adding the current element: leftSum += nums[i].
If the loop finishes, it means no middle index was found. Return -1.

The key to optimizing this problem is to avoid the expensive O(n) sum calculations inside the main loop. We can achieve this by pre-calculating the total sum of the array. Let's call this totalSum.

With totalSum, if we know the sum of elements to the left of an index i (leftSum), we can find the sum of elements to its right (rightSum) with a simple formula: rightSum = totalSum - leftSum - nums[i].

The algorithm works as follows:

Make a single pass through the array to compute totalSum.
Make a second pass. In this pass, we maintain a leftSum variable, initialized to 0. For each index i, we check if leftSum is equal to the calculated rightSum. If it is, we've found our answer. If not, we update leftSum by adding nums[i] to it, preparing it for the check at the next index i+1. This process continues until we find the leftmost middle index or exhaust the array.

class Solution {
    public int findMiddleIndex(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            // The right sum is totalSum - leftSum - nums[i]
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }

        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the `nums` array. The array is traversed a constant number of times (twice), making the overall complexity linear.Space Complexity: O(1). We only use a couple of variables (`totalSum`, `leftSum`) to store the sums, which does not depend on the size of the input array.

Pros and Cons

Pros:

Optimal time complexity of O(n).
Efficient and scalable for larger inputs.
Uses constant extra space.

Cons:

Requires two passes over the array (one to get the total sum, and a second to find the index).

Code Solutions

Checking out 4 solutions in different languages for Find the Middle Index in Array. Click on different languages to view the code.

class Solution {
public
  int findMiddleIndex(int[] nums) {
    int left = 0, right = Arrays.stream(nums).sum();
    for (int i = 0; i < nums.length; ++i) {
      right -= nums[i];
      if (left == right) {
        return i;
      }
      left += nums[i];
    }
    return -1;
  }
}

Video Solution

Watch the video walkthrough for Find the Middle Index in Array

Patterns:

Prefix Sum

Data Structures:

Array