{x}
blog image

Find the Middle Index in Array

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/

Problem: Find the Middle Index in Array

Given a 0-indexed integer array nums, find the leftmost middleIndex such that the sum of elements to the left of middleIndex equals the sum of elements to its right. If middleIndex is 0, the left sum is 0. If middleIndex is the last index, the right sum is 0. Return the leftmost middleIndex or -1 if none exists.

Solution: Prefix Sum Approach

The most efficient way to solve this problem is using the prefix sum technique. This avoids repeatedly calculating sums, leading to a linear time complexity solution.

Algorithm:

  1. Calculate Total Sum: First, calculate the total sum of all elements in the nums array.
  2. Iterate and Compare: Iterate through the array. For each index i:
    • Calculate the right sum by subtracting the current element nums[i] from the total sum.
    • Compare the left sum (initially 0) with the right sum. If they are equal, i is the middleIndex, so return i.
    • Update the left sum by adding the current element nums[i].
  3. Return -1: If the loop completes without finding a middleIndex, return -1.

Code Examples

Here are implementations in several programming languages:

Python:

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

Java:

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

C++:

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        int leftSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            totalSum -= nums[i]; //Right sum
            if (leftSum == totalSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
};

JavaScript:

var findMiddleIndex = function(nums) {
    let totalSum = nums.reduce((a, b) => a + b, 0);
    let leftSum = 0;
    for (let i = 0; i < nums.length; i++) {
        totalSum -= nums[i]; //Right sum
        if (leftSum === totalSum) {
            return i;
        }
        leftSum += nums[i];
    }
    return -1;
};

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.

Space Complexity: O(1). We use only a few variables to store sums; the space used is constant regardless of the input size.