Find the Middle Index in Array

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0

        for i, num in enumerate(nums):
            # adjust the total sum to get the sum of right side of the index
            total_sum -= num

            # if the sum of left side is equal to the sum of right side, return the index
            if left_sum == total_sum:
                return i

            # adjust the left sum for the next index
            left_sum += num

        # if no valid index is found, return -1
        return -1

The approach here is to iterate over the array while keeping track of the sum of the elements on the left side (left_sum) and the sum of the rest of the elements (total_sum). For each index, if left_sum is equal to total_sum, return the index because that’s a valid “middle index” according to the problem’s definition. If no such index is found, the function returns -1.

Identifying Problem Isomorphism

This problem is same as problem 724. Find Pivot Index.

Yes, you’re correct. This problem is similar to the problem 724, “Find Pivot Index”, in LeetCode. Both problems involve finding an index in an array where the sum of the elements to the left of the index equals the sum of the elements to the right.

However, there is a slight variation in the definition of the pivot index and the middle index in the two problems. In problem 724, the pivot index is allowed to be the first or last index of the array (if the sum of the rest of the array is 0), while in this problem, the middle index is not allowed to be the first or last index.

The same approach can be used to solve both problems. The key idea is to maintain a running total of the elements in the array and a running total of the elements to the left of the current index. These totals can then be compared to identify if the current index is a pivot index or middle index.