Find the Middle Index in Array
EasyPrompt
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 = 4Example 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: 0Example 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
totalSumof all its elements. - Initialize a
leftSumvariable to0. - Iterate through the array again with an index
ifrom0tonums.length - 1. - In each iteration, the
rightSumcan be calculated without a new loop:rightSum = totalSum - leftSum - nums[i]. - Check if
leftSum == rightSum. If they are equal,iis the middle index. Returni. - If the condition is not met, update
leftSumfor 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:
- Make a single pass through the array to compute
totalSum. - Make a second pass. In this pass, we maintain a
leftSumvariable, initialized to 0. For each indexi, we check ifleftSumis equal to the calculatedrightSum. If it is, we've found our answer. If not, we updateleftSumby addingnums[i]to it, preparing it for the check at the next indexi+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).
This approach iterates through every possible index and, for each one, calculates the sum of elements to the left and the sum of elements to the right by using two separate inner loops. It's straightforward but inefficient.
Algorithm
- Iterate through each index
ifrom0tonums.length - 1, considering it as a potentialmiddleIndex. - For each
i, initialize aleftSumto 0. - Calculate the
leftSumby iterating with a second loop from indexj = 0toi - 1and summing upnums[j]. - For the same
i, initialize arightSumto 0. - Calculate the
rightSumby iterating with a third loop from indexk = i + 1tonums.length - 1and summing upnums[k]. - Compare
leftSumandrightSum. If they are equal,iis a middle index. Since we are iterating from left to right, this is the leftmost one. Returni. - If the outer loop completes without finding any such index, it means no
middleIndexexists. Return-1.
Walkthrough
In this brute-force method, we test every single index of the array to see if it qualifies as a middleIndex. We use a main loop that iterates from the first index (0) to the last. Inside this loop, for the current index i, we perform two more traversals. The first inner loop calculates the sum of all elements to the left of i (from index 0 to i-1). The second inner loop calculates the sum of all elements to the right of i (from index i+1 to the end). After calculating both sums, we check if they are equal. If they are, we've found the leftmost middleIndex because our main loop started from the left. We can immediately return the index i. If the main loop finishes without finding any index where the sums are equal, we conclude that no such index exists and return -1.
class Solution { public int findMiddleIndex(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { int leftSum = 0; for (int j = 0; j < i; j++) { leftSum += nums[j]; } int rightSum = 0; for (int k = i + 1; k < n; k++) { rightSum += nums[k]; } if (leftSum == rightSum) { return i; } } return -1; }}Complexity
Time
O(n^2), where n is the length of the `nums` array. For each of the `n` elements, we potentially iterate over the rest of the array to calculate the left and right sums, leading to a nested loop structure.
Space
O(1). We only use a few variables to store the sums and loop indices, regardless of the input array size.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
Highly inefficient for larger arrays due to its quadratic time complexity.
Performs many redundant calculations, as sums are re-computed from scratch in each iteration.
Solutions
Solution
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; }}/** * @param {number[]} nums * @return {number} */ var findMiddleIndex = function ( nums ) { let left = 0 , right = nums . reduce (( a , b ) => a + b ); for ( let i = 0 ; i < nums . length ; ++ i ) { right -= nums [ i ]; if ( left == right ) { return i ; } left += nums [ i ]; } return - 1 ; };class Solution {public: int findMiddleIndex(vector<int> &nums) { int left = 0, right = accumulate(nums.begin(), nums.end(), 0); for (int i = 0; i < nums.size(); ++i) { right -= nums[i]; if (left == right) { return i; } left += nums[i]; } return -1; }};class Solution: def findMiddleIndex(self, nums: List[int]) -> int: left, right = 0, sum(nums) for i, x in enumerate(nums): right -= x if left == right: return i left += x return - 1Video 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.