Scale Engineer

Find the Middle Index in Array

Easy
#1813Time: O(n), where n is the length of the `nums` array. The array is traversed a constant number of times (twice), making the overall complexity linear.Space: O(1). We only use a couple of variables (`totalSum`, `leftSum`) to store the sums, which does not depend on the size of the input array.
Patterns
Prefix Sum
Data structures
Array

Prompt

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/

Approaches

2 approaches with complexity analysis and trade-offs.

This approach significantly improves performance by avoiding recalculations. It first computes the total sum of the array. Then, it iterates through the array once more, maintaining a running leftSum. The rightSum can be calculated in constant time using the totalSum and the current leftSum.

Algorithm

  • First, iterate through the entire array once to calculate the totalSum of all its elements.
  • Initialize a leftSum variable to 0.
  • Iterate through the array again with an index i from 0 to nums.length - 1.
  • In each iteration, the rightSum can be calculated without a new loop: rightSum = totalSum - leftSum - nums[i].
  • Check if leftSum == rightSum. If they are equal, i is the middle index. Return i.
  • If the condition is not met, update leftSum for the next iteration by adding the current element: leftSum += nums[i].
  • If the loop finishes, it means no middle index was found. Return -1.

Walkthrough

The key to optimizing this problem is to avoid the expensive O(n) sum calculations inside the main loop. We can achieve this by pre-calculating the total sum of the array. Let's call this totalSum.

With totalSum, if we know the sum of elements to the left of an index i (leftSum), we can find the sum of elements to its right (rightSum) with a simple formula: rightSum = totalSum - leftSum - nums[i].

The algorithm works as follows:

  1. Make a single pass through the array to compute totalSum.
  2. Make a second pass. In this pass, we maintain a leftSum variable, initialized to 0. For each index i, we check if leftSum is equal to the calculated rightSum. If it is, we've found our answer. If not, we update leftSum by adding nums[i] to it, preparing it for the check at the next index i+1. This process continues until we find the leftmost middle index or exhaust the array.
class Solution {    public int findMiddleIndex(int[] nums) {        int totalSum = 0;        for (int num : nums) {            totalSum += num;        }         int leftSum = 0;        for (int i = 0; i < nums.length; i++) {            // The right sum is totalSum - leftSum - nums[i]            if (leftSum == totalSum - leftSum - nums[i]) {                return i;            }            leftSum += nums[i];        }         return -1;    }}

Complexity

Time

O(n), where n is the length of the `nums` array. The array is traversed a constant number of times (twice), making the overall complexity linear.

Space

O(1). We only use a couple of variables (`totalSum`, `leftSum`) to store the sums, which does not depend on the size of the input array.

Trade-offs

Pros

  • Optimal time complexity of O(n).

  • Efficient and scalable for larger inputs.

  • Uses constant extra space.

Cons

  • Requires two passes over the array (one to get the total sum, and a second to find the index).

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem