</>Ali · LeetCode
#1991·EasyArrays

Find the Middle Index in Array

LeetCode #1991 · Easy · Arrays · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Prefix Sum with Two Arrays

Key insight

Precompute cumulative sums from both directions, then find the index where left sum equals right sum.

Strategy

  1. 1Build leftSum array: leftSum[i] = sum of elements before index i
  2. 2Build rightSum array: rightSum[i] = sum of elements after index i
  3. 3Find the first index where leftSum[i] == rightSum[i]
Time
O(n)
three passes through the array
Space
O(n)
two auxiliary arrays
Problem description(from LeetCode)

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.

Examples

Example 1
Input:
nums = [2,3,-1,8,4]
Output:
3
Note:
The sum of the numbers before index 3 is: 2 + 3 + -1 = 4 The sum of the numbers after index 3 is: 4 = 4 Input: nums = [1,-1,4] Output: 2 Explanation: The sum before index 2 is: 1 + -1 = 0 The sum after index 2 is: 0 Input: nums = [2,5] Output: -1 Explanation: There is no valid middleIndex.

Constraints

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

C++ Solution

solution.cpp
class Solution {
public:
int findMiddleIndex(vector<int> &nums) {
    int n = nums.size();

    if (n == 1) return 0;

    vector<int> leftSum(n, 0);
    vector<int> rightSum(n, 0);

    for (int i = 0; i < n - 1; i++) {
      leftSum[i + 1] = leftSum[i] + nums[i];
    }

    for (int j = n - 1; j > 0; j--) {
      rightSum[j - 1] = rightSum[j] + nums[j];
    }

    for (int i = 0; i < n; i++) {
      if (leftSum[i] == rightSum[i]) {
        return i;
      }
    }

    return -1;
  }

  /*
   * Approach 2: Optimized with Total Sum (Space-efficient)
   *
   * Key Insight: Instead of storing both prefix arrays, use the relationship:
   * rightSum = totalSum - leftSum - nums[i]
   *
   * At middle index: leftSum == rightSum
   * So: leftSum == totalSum - leftSum - nums[i]
   * Which means: 2 * leftSum + nums[i] == totalSum
   *
   * Time Complexity: O(n) - two passes through the array
   * Space Complexity: O(1) - only constant extra space
   */
  int findMiddleIndexOptimized(vector<int> &nums) {
    int totalSum = accumulate(nums.begin(), nums.end(), 0);
    int leftSum = 0;

    for (int i = 0; i < nums.size(); i++) {
      // Check if left sum equals right sum
      // rightSum = totalSum - leftSum - nums[i]
      if (leftSum == totalSum - leftSum - nums[i]) {
        return i;
      }
      leftSum += nums[i];
    }

    return -1;
  }
};

More Arrays problems