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.
Consider the time and space complexity. Detail the edge cases and explain your logic clearly. Provide code samples in Python.
A brute force approach involves iterating through each index of the array and calculating the left and right sums for that index. If the sums are equal, the index is returned. This is a straightforward but inefficient solution.
def find_middle_index_brute_force(nums):
for i in range(len(nums)):
left_sum = 0
for j in range(i):
left_sum += nums[j]
right_sum = 0
for k in range(i + 1, len(nums)):
right_sum += nums[k]
if left_sum == right_sum:
return i
return -1
A more efficient solution uses prefix sums. We first calculate the total sum of the array. Then, we iterate through the array, maintaining a running sum of the left side. For each index, we can determine the right sum by subtracting the current element and the left sum from the total sum. If the left sum equals the right sum, we have found our middle index.
def find_middle_index_optimal(nums):
total_sum = sum(nums)
left_sum = 0
for i in range(len(nums)):
right_sum = total_sum - left_sum - nums[i]
if left_sum == right_sum:
return i
left_sum += nums[i]
return -1
The optimal solution is implemented in the code snippet above.