Find the Middle Index in Array

easy array prefix sum

Problem

Given an array of integers nums, return the leftmost index i such that the sum of the elements strictly to the left of i equals the sum of the elements strictly to the right of i. The element at i itself counts for neither side, and an empty side is treated as a sum of 0. If no such index exists, return -1.

Inputnums = [2, 3, -1, 8, 4]

Output3

Left of index 3 is 2 + 3 + (-1) = 4, and right of index 3 is 4. Both sides match, so the answer is 3.

nums (comma-separated)

def find_middle_index(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        right = total - left - x
        if left == right:
            return i
        left += x
    return -1

function findMiddleIndex(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  let left = 0;
  for (let i = 0; i < nums.length; i++) {
    const right = total - left - nums[i];
    if (left === right) return i;
    left += nums[i];
  }
  return -1;
}

class Solution {
    public int findMiddleIndex(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            int right = total - left - nums[i];
            if (left == right) return i;
            left += nums[i];
        }
        return -1;
    }
}

int findMiddleIndex(vector<int>& nums) {
    int total = 0;
    for (int x : nums) total += x;
    int left = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        int right = total - left - nums[i];
        if (left == right) return i;
        left += nums[i];
    }
    return -1;
}

Explanation

We are looking for a pivot index where everything on its left sums to the same value as everything on its right. The number sitting at the pivot itself belongs to neither side.

The slow approach would be: for every index, add up all the numbers to its left and all the numbers to its right separately. That repeats a lot of the same addition over and over.

The faster trick uses one fact. If we know the total of the whole array, and we keep a running left sum of everything before the current index, then the right sum is just leftover arithmetic: right = total − left − nums[i]. There is no need to scan the right side at all.

So we first compute total in one pass. Then we walk left to right with left starting at 0. At each index i we compute right from the formula and check whether left == right. The first index where they match is our answer (this is why it is the leftmost). If they do not match, we fold nums[i] into left and continue.

Example: nums = [2, 3, -1, 8, 4], so total = 16. At index 3, left = 2 + 3 + (-1) = 4 and right = 16 − 4 − 8 = 4. They are equal, so we return 3. If we reach the end without a match, we return -1.

Time: O(n) Space: O(1)