Find the Middle Index in Array
Easy
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.
Solution
Naive Solution
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
- Big(O) Runtime: O(n^2) - For each index, we iterate through the array to calculate the left and right sums.
- Big(O) Space Usage: O(1) - Constant space is used.
Optimal Solution
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
- Big(O) Runtime: O(n) - We iterate through the array twice (once for calculating the total sum, and once for finding the middle index).
- Big(O) Space Usage: O(1) - Constant space is used.
Edge Cases
- Empty array: The problem statement specifies that the array length is between 1 and 100, so an empty array is not possible. However, we should still consider how our function would handle such a scenario.
- Array with one element: In this case, the middle index is 0, as both left and right sums are 0.
- No middle index: If no index satisfies the condition, the function should return -1.
- Negative numbers: The presence of negative numbers should not affect the algorithm as long as the sums are calculated correctly.
Code Implementation (Python)
The optimal solution is implemented in the code snippet above.
