Watch 10 video solutions for Find the Middle Index in Array, a easy level problem involving Array, Prefix Sum. This walkthrough by Learn Together has 2,292 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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/
Problem Overview: You are given an integer array and need to return the index where the sum of elements to the left equals the sum of elements to the right. If multiple indices satisfy the condition, return the leftmost one. If none exist, return -1. This is a classic balance-point problem that relies on efficient sum calculations within an array.
Approach 1: Brute Force Approach (O(n^2) time, O(1) space)
The straightforward method checks every index and computes the sum of elements on its left and right. For each position i, iterate through the array from 0 to i-1 to calculate the left sum, and from i+1 to n-1 for the right sum. If the two sums match, return the index immediately. This method is easy to implement and useful for understanding the problem constraints, but repeated summation makes it inefficient for large arrays. The nested iteration leads to O(n^2) time complexity while using constant extra memory.
Approach 2: Prefix Sum Approach (O(n) time, O(1) space)
The optimal strategy avoids recomputing sums by tracking them incrementally using the prefix sum technique. First compute the total sum of the entire array. Then iterate through the array while maintaining a running leftSum. For each index i, calculate the right sum using rightSum = totalSum - leftSum - nums[i]. If leftSum == rightSum, you found the middle index and return it. After the check, update leftSum += nums[i] and continue scanning. This approach ensures every element is processed exactly once, producing O(n) time complexity and O(1) extra space.
The key insight is that the right side sum does not need to be recomputed from scratch. Since the total sum is known, subtracting the current value and the accumulated left sum instantly gives the right sum. This transforms an otherwise quadratic process into a linear scan.
Recommended for interviews: Start by explaining the brute force method to demonstrate baseline reasoning about left and right sums. Then transition to the prefix sum optimization, which interviewers typically expect. The O(n) solution shows you recognize repeated work and eliminate it using cumulative sums, a common pattern in prefix sum and array problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Good for understanding the problem logic or very small arrays |
| Prefix Sum | O(n) | O(1) | Best general solution; avoids repeated summation and scales efficiently |