Find the Middle Index in Array

Easy

Find the Middle Index in Array

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected return value if no middle index exists?
What are the possible value ranges for the integers in the array? Can they be negative?
Is an empty array a valid input, and if so, what should I return?
Can the input array contain non-integer values?
In the case of multiple 'middle' indices, which one should be returned (e.g., the first, the last)?

Brute Force Solution

Approach

We're figuring out where the middle is by exhaustively checking. We'll consider every single spot in the list as a possible middle, one at a time. For each spot, we'll compare the 'weight' on the left to the 'weight' on the right.

Here's how the algorithm would work step-by-step:

First, pick the very first spot in the list and pretend it's the middle.
Calculate the total 'weight' of everything to the left of this spot.
Calculate the total 'weight' of everything to the right of this spot.
See if the 'weight' on the left matches the 'weight' on the right. If they do, we've found our middle!
If they don't match, move on to the next spot in the list and repeat steps 2, 3, and 4.
Keep doing this until you either find a spot where the 'weights' match, or you run out of spots to try.
If you reach the end of the list without finding a match, then there's no middle spot.

Code Implementation

def find_middle_index_brute_force(numbers):
    for potential_middle_index in range(len(numbers)):
        left_sum = 0
        for index_on_left in range(potential_middle_index):
            left_sum += numbers[index_on_left]

        # Reset the right sum for each middle index
        right_sum = 0
        for index_on_right in range(potential_middle_index + 1, len(numbers)):
            right_sum += numbers[index_on_right]

        # Check sums, we found the middle
        if left_sum == right_sum:
            return potential_middle_index

    # No middle found, weights never match
    return -1

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements of the input array, considering each element as a potential middle index. For each potential middle index, it calculates the sum of the elements to its left and the sum of the elements to its right. Calculating each sum requires iterating through a portion of the array, taking up to n operations in the worst case. Therefore, in the worst case, the algorithm performs n iterations, and each iteration takes O(n) time, resulting in a time complexity of approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm calculates left and right sums for each index, but it doesn't explicitly store any additional data structures like lists or maps that scale with the input size N (the number of elements in the input array). It likely uses a few variables to store the left sum, right sum, and the current index being evaluated. These variables consume a constant amount of space, irrespective of N, resulting in constant auxiliary space complexity.

Optimal Solution

Approach

The key is to avoid redundant calculations. Instead of repeatedly summing sections of the collection, we calculate a cumulative sum from one side and use that to efficiently derive sums from the opposite side when needed.

Here's how the algorithm would work step-by-step:

Calculate the total sum of all the numbers in the collection.
Start from the beginning of the collection and keep a running sum as you go through each number.
At each number, check if the running sum (sum of numbers to the left) is equal to the total sum minus the current number and the running sum (sum of numbers to the right).
If the sums are equal, that means the current number is the middle, and you've found your answer.
If you get to the end of the collection without finding such a number, it means there is no middle number that satisfies the condition.

Code Implementation

def find_middle_index(numbers):
    total_sum = sum(numbers)

    running_sum = 0

    for i, number in enumerate(numbers):
        # Check if left sum equals right sum
        if running_sum == (total_sum - running_sum - number):

            return i

        # Keep a running sum of the left side
        running_sum += number

    # If no middle index is found
    return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm first calculates the total sum of the array, which requires iterating through all n elements once. Then, it iterates through the array again, maintaining a running sum. Inside this loop, it performs a constant number of arithmetic operations to check the middle index condition. Therefore, the time complexity is dominated by the two linear traversals of the array, resulting in O(n) time complexity.

Space Complexity

O(1) – The solution calculates a total sum and a running sum. It uses a few variables like total_sum and running_sum to store these sums, and possibly an index variable to iterate through the collection. The number of these variables remains constant regardless of the size of the input collection (N). Therefore, the space complexity is constant, O(1).

Edge Cases

Case	How to Handle
Null or empty array input	Return -1 immediately, as a middle index cannot exist in an empty array.
Array with only one element	Return 0 as the first and only element satisfies the condition of having equal sum on both sides.
Array with all elements equal to zero	Return 0 as the first index since the sum on both sides will always be 0.
Array with a large number of elements (performance considerations)	Use a prefix sum approach for O(n) time complexity to efficiently handle large arrays.
Integer overflow when calculating sums, especially with large positive or negative numbers	Use long data type to store sums to prevent potential integer overflows.
Array where no middle index exists	Return -1 after iterating through the entire array and not finding a suitable middle index.
Array with negative numbers	The algorithm should handle negative numbers correctly since it's based on calculating sums.
Array with extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	Using long avoids overflow which would be relevant in boundary value calculations.