algoadvance

Leetcode 1991. Find the Middle Index in Array

Problem Statement

Given a 0-indexed integer array nums, find the leftmost middle index such that the sum of the elements on its left is equal to the sum of the elements on its right. If no such index exists, return -1.

A middle index is an index where the sum of the elements to its left is equal to the sum of the elements to its right.

Clarifying Questions

Q1. What should be considered the “left” and “right” of the middle index?

A1. The elements on the left of the middle index i are those from index 0 to i-1, and the elements on the right are those from index i+1 to the end of the array.

Q2. What is the range of values for the elements in the array and the length of the array?

A2. The elements of the array can be any integer, and the length of the array can range from 1 to 10^4.

Q3. How should we handle a case where the array consists of only one element?

A3. If there’s only one element, the middle index is 0 by default because there are no elements on either side to compare.

Strategy

  1. Compute the total sum of the array.
  2. Iterate through the array and maintain a running sum of the elements to the left of the current index.
  3. For each index, compute the right sum by subtracting the current index value and the left sum from the total sum.
  4. Compare the left and right sums. If they are equal, return the current index.
  5. If no such index is found by the end of the array, return -1.

Code

#include <vector>

class Solution {
public:
    int findMiddleIndex(std::vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        int leftSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        
        return -1;
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI