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.
This approach uses the concept of prefix sums to calculate sums on both sides of each index efficiently. We compute the total sum of the array and iterate through each index, maintaining a running sum from the left side. At each index, we simply check if twice the running sum equals the total sum minus the current element. If it does, we've found our middle index.
In C, we first calculate the total sum of the array. Then, as we iterate through the array, we maintain a left running sum. If the condition leftSum * 2 + nums[i] == totalSum is true, the current index is returned as the middle index. If no such index is found, -1 is returned.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), since we use only a constant amount of extra space.
In the brute force approach, we iterate over each possible index in the array and calculate the sum of elements on both sides of that index. This approach involves two nested iterations: one to determine the left sum and another for the right sum for each index.
In this C brute force approach, we iterate through each index and compute the sum on the left and right side of the index independently. If left and right sums match, that index is returned as the middleIndex.
Time Complexity: O(n^2), because for each index we compute left and right sums by iterating over the array.
Space Complexity: O(1), only using constant extra space for variables.
We define two variables l and r, representing the sum of elements to the left and right of index i in the array nums, respectively. Initially, l = 0 and r = sum_{i = 0}^{n - 1} nums[i].
We traverse the array nums, and for the current number x, we update r = r - x. If l = r at this point, it means the current index i is the middle index, and we return it directly. Otherwise, we update l = l + x and continue to the next number.
If the traversal ends without finding a middle index, return -1.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Similar problems:
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n), where n is the number of elements in the array. |
| Brute Force Approach | Time Complexity: O(n^2), because for each index we compute left and right sums by iterating over the array. |
| Prefix Sum | — |
| 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 |
Leetcode 1991 : Find the Middle Index in Array • Learn Together • 2,292 views views
Watch 9 more video solutions →Practice Find the Middle Index in Array with our built-in code editor and test cases.
Practice on FleetCode