We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Middle Index in Array

Difficulty: Easy

Problem Description

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.

Key Insights

  • The left side sum for any index can be calculated by keeping a running total as we iterate through the array.
  • The right side sum can be derived from the total sum of the array minus the current index value and the left side sum.
  • The solution must find the leftmost index that satisfies the middle index condition.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The algorithm uses a single pass through the array to calculate the total sum of the elements. As we iterate through the array, we maintain a running sum of the left side elements. For each index, we can compute the right side sum by subtracting the left side sum and the current element from the total sum. If the left side sum equals the right side sum at any index, we return that index. If no such index is found by the end of the loop, we return -1.

Code Solutions

def findMiddleIndex(nums):
    total_sum = sum(nums)  # Calculate the total sum of the array
    left_sum = 0  # Initialize left sum to 0
    
    for index in range(len(nums)):
        if left_sum == total_sum - left_sum - nums[index]:  # Check if left sum equals right sum
            return index  # Return the current index if the condition is met
        left_sum += nums[index]  # Update left sum for the next iteration
        
    return -1  # Return -1 if no middle index is found
← Back to All Questions