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/
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Search in rotated sorted array - Leetcode 33 - Python • NeetCode • 413,348 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