algoadvance

You are given a 0-indexed integer array nums. The middle index is any index i such that nums[0] + nums[1] + ... + nums[i-1] == nums[i+1] + nums[i+2] + ... + nums[nums.length-1].

• If i is the middle index, return i, otherwise, return -1.
• If there are multiple middle indices, return the leftmost one.

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.

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 an empty sum, which is 0.

3. Input: nums = [2, 5] Output: -1 Explanation: There is no valid middle index.

Clarifying Questions

1. Could the input array be empty? (Assume no, as the problem would be undefined).
2. Can we have negative numbers in the array? (Yes)
3. Is it possible to have multiple solutions? (Return the leftmost one)

Strategy

To find the middle index, we’ll keep track of the running sum from the start and the end of the array.

1. Compute the Total Sum:
   • Compute the total sum of the array elements.
2. Iterate Through the Array:
   • Use a variable to keep track of the left sum as we iterate.
   • For each index i, the right sum can be derived by subtracting the left sum and the element at index i from the total sum.
   • If the left sum equals the right sum at any index, that’s our answer.
3. Return the index if found, else return -1.

Code

def findMiddleIndex(nums):
    total_sum = sum(nums)
    left_sum = 0

    for i, num in nums:
        right_sum = total_sum - left_sum - num
        if left_sum == right_sum:
            return i
        left_sum += num
    
    return -1

Time Complexity

• O(N): We iterate through the array elements once to compute the total sum, and then another time to find the middle index.

Space Complexity

• O(1): Only a few additional variables are used regardless of input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?