Problem

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 _theleftmost _middleIndex that satisfies the condition, or-1 if there is no such index.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

1
2
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/

Solution

Method 1 – Prefix Sum

Intuition

We want to find the leftmost index where the sum of elements to the left equals the sum of elements to the right. By precomputing the total sum and using a running prefix sum, we can check this condition efficiently for each index.

Approach

  1. Compute the total sum of the array.
  2. Initialize a variable for the prefix sum (sum of elements to the left).
  3. For each index, check if the prefix sum equals the total sum minus the prefix sum minus the current element (right sum).
  4. If so, return the current index.
  5. If no such index exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0), pre = 0;
        for(int i=0;i<nums.size();++i) {
            if(pre == total - pre - nums[i]) return i;
            pre += nums[i];
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9

func findMiddleIndex(nums []int) int {
    total, pre := 0, 0
    for _, x := range nums { total += x }
    for i, x := range nums {
        if pre == total-pre-x { return i }
        pre += x
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int findMiddleIndex(int[] nums) {
        int total = 0, pre = 0;
        for(int x : nums) total += x;
        for(int i=0;i<nums.length;++i) {
            if(pre == total-pre-nums[i]) return i;
            pre += nums[i];
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun findMiddleIndex(nums: IntArray): Int {
        val total = nums.sum(); var pre = 0
        for(i in nums.indices) {
            if(pre == total-pre-nums[i]) return i
            pre += nums[i]
        }
        return -1
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def findMiddleIndex(self, nums: list[int]) -> int:
        total = sum(nums)
        pre = 0
        for i, x in enumerate(nums):
            if pre == total - pre - x:
                return i
            pre += x
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn find_middle_index(nums: Vec<i32>) -> i32 {
        let total: i32 = nums.iter().sum();
        let mut pre = 0;
        for (i, &x) in nums.iter().enumerate() {
            if pre == total - pre - x { return i as i32; }
            pre += x;
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    findMiddleIndex(nums: number[]): number {
        const total = nums.reduce((a,b)=>a+b,0);
        let pre = 0;
        for(let i=0;i<nums.length;++i) {
            if(pre === total-pre-nums[i]) return i;
            pre += nums[i];
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, as we scan the array once.
  • 🧺 Space complexity: O(1), only a few variables are used.