Leetcode – Find the Middle Index in Array Solution

The “Find the Middle Index in Array” problem is a classic question that tests your understanding of array manipulation and algorithmic efficiency. It is often encountered in interviews and competitive programming contests. In this article, we will dive deep into solving this problem in Python, evaluating different approaches, and their respective time complexities.

1. Problem Statement

The problem asks for the middle index of an array such that the sum of the elements on the left is equal to the sum of the elements on the right. If there are multiple middle indices, return the left-most one.

Example:

Input: nums = [2, 3, -1, 8, 4]
Output: 3

The sum of elements to the left of index 3 is 2 + 3 + -1 = 4, and to the right is 4. Since both sums are equal, index 3 is the middle index.

2. Clarifying Assumptions and Constraints

• The array may contain both positive and negative integers.
• If there is no such index, return -1.

3. Brute-Force Approach

A naive approach is to check each index one-by-one to see if it’s a middle index:

Python Code:

def findMiddleIndex(nums):
    for i in range(len(nums)):
        if sum(nums[:i]) == sum(nums[i+1:]):
            return i
    return -1

4. Optimizing with Prefix Sum

Calculating the sum of elements every time in the loop is inefficient. Instead, we can pre-calculate the prefix sum of the array to reduce the number of calculations.

Python Code:

def findMiddleIndex(nums):
    total_sum = sum(nums)
    prefix_sum = 0
    
    for i, num in enumerate(nums):
        total_sum -= num
        if prefix_sum == total_sum:
            return i
        prefix_sum += num
    
    return -1

5. Space-Efficient Approach

The above method can be further optimized to work without additional space by maintaining two variables to keep track of the sum.

Python Code:

def findMiddleIndex(nums):
    left_sum, right_sum = 0, sum(nums)
    
    for i, num in enumerate(nums):
        right_sum -= num
        if left_sum == right_sum:
            return i
        left_sum += num
    
    return -1

6. Time Complexity Analysis

• Brute-Force: O(n^2) due to nested sum calculation.
• Prefix Sum: O(n) for generating the prefix sum and another O(n) for finding the middle index. So, O(n) in total.
• Space-Efficient: O(n) for the single loop through the array.

7. Conclusion

The “Find the Middle Index in Array” problem tests your ability to work with arrays and understand algorithmic efficiency. The problem can be solved in various ways, from a brute-force approach to more efficient techniques using prefix sums. Understanding how and why each method works, and their associated time complexities, is crucial for mastering algorithmic problem-solving.