Find The Middle Index In Array - Leetcode Solution

Problem Statement:

Given a non-empty array of integers nums, you should return the index of the middle element.

If the array contains an even number of elements, the index must be in the lower half of the array.

Example 1:

Input: nums = [2,3,-1,8,4] Output: 3 Explanation: The middle index is 3, which is the index of the element 8.

Example 2:

Input: nums = [1,-5,7,2,4] Output: 2 Explanation: The middle index is 2, which is the index of the element 7.

Approach:

We can start by calculating the sum of all elements of the array using a loop. Then, we can iterate through the elements of the array again, keeping track of the left sum as we go. If the left sum equals the sum of all elements minus the left sum minus the current element, we have found the middle index and can return it.

Code:

Here is the code for the solution in Python:

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

    for i in range(len(nums)):
        if left_sum == total_sum - left_sum - nums[i]:
            return i
        left_sum += nums[i]
    
    return -1 # If middle index not found

Complexity Analysis:

Time Complexity: O(n), where n is the length of the array.

Space Complexity: O(1), since no additional space is used apart from a few variables.

1