1991. Find the Middle Index in Array

Problem Description

The problem provides an array of integers called nums, which is indexed starting from 0. We are tasked with finding the leftmost middleIndex in this array, defined as an index where the sum of elements to the left of middleIndex is equal to the sum of elements to the right of middleIndex. If middleIndex is chosen at the very beginning (0th index) or the end (last index), then the sum of elements on the one side without elements is taken as 0.

Our goal is to identify the lowest index that satisfies this condition or determine that no such index exists and return -1. A middle index that divides the array into two parts with equal sums forms a balance point in the array, and finding the leftmost index means we are looking for the first position that creates equilibrium from the start of the array moving towards the end.

Intuition

To solve this problem, the key is to iterate through the array while keeping track of two sums: the sum of elements to the left of the current index and the sum of elements to the right. This can be done efficiently by maintaining two variables, one for the left sum and another for the right sum (which initially is the sum of all elements in the array).

We start iterating through the array from the leftmost index. For each index i, we perform the following steps:

We subtract the value at index i from the right sum, as we are now considering this value as a part of the left sum.
We check if the left sum is equal to the right sum. If it is, we have found a middleIndex.
If the left sum is not equal to the right sum, we add the value at index i to the left sum, effectively moving our middleIndex to the next position.

This way, we are continuously updating the sums on either side of the current index in O(1) time, leading to an overall O(n) time complexity for this algorithm, where n is the length of the array. We only need to do a single pass through the array, which makes this approach efficient. If none of the indices satisfies the middle index condition, we return -1, indicating that no such index exists.

Learn more about Prefix Sum patterns.

Solution Approach

The solution approach involves the following steps:

Initialize a variable left with a value of 0. It will hold the sum of elements to the left of the current index during the iteration.
Initialize a variable right with the sum of all the elements in the nums array, which will be the total sum of elements to the right of the current index before iteration starts.
Iterate over the array using a loop, where i is the current index and x is the value at nums[i].

a. Subtract the current element x from right because this step effectively updates the sum to the right of the current index to exclude x (since x either falls on the middle or moves to the left part in the next step).

b. Check if left is equal to right. If yes, we have found a middleIndex since the sum of elements on either side of i is the same. Therefore, return i.

c. If left does not equal right, it means the current index i is not the middleIndex. Add x to left to include it in the sum of elements on the left side for the subsequent iterations.
If the loop completes without returning a middle index, this indicates that no such index exists in the array that satisfies the condition. In this case, return -1.

This algorithm uses a single loop making it a linear solution with O(n) time complexity, where n is the number of elements in nums. The space complexity is O(1), as we are only using two extra variables. This approach is efficient because it only needs a single pass over the data, which is a classic example of the prefix sum technique often used in array processing problems.

Here, the left variable maintains the prefix sum of elements seen so far (cumulative sum up to the current index), and right variable represents the remaining sum of the array not included in the prefix. It is a straightforward solution that easily identifies the middle index by balancing these two sums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example.

Consider the array nums = [2, 3, -1, 8, 4]. We will use this array to walk through the solution approach step by step.

We initialize a variable left with a value of 0. This will keep track of the sum of elements to the left of the current index in our loop.
We initialize a variable right with the sum of all the elements in the nums array, which is 2 + 3 + (-1) + 8 + 4 = 16.
Now we begin iterating over the array, looking to find a middleIndex where the sum of elements on either side of it are equal:
- For i = 0 (x = nums[0] is 2): a. Subtract x (which is 2) from right, so right becomes 16 - 2 = 14. b. Check if left equals right. They are not equal (0 != 14), so we move on. c. Finally, add x to left, making left now 0 + 2 = 2.
- For i = 1 (x = nums[1] is 3): a. Subtract x (which is 3) from right, so right becomes 14 - 3 = 11. b. Check if left equals right. They are not equal (2 != 11), so we move on. c. Add x to left, making left now 2 + 3 = 5.
- For i = 2 (x = nums[2] is -1): a. Subtract x (which is -1) from right, so right becomes 11 - (-1) = 12. b. Check if left equals right. They are not equal (5 != 12), so we move on. c. Add x to left, making left now 5 - 1 = 4.
- For i = 3 (x = nums[3] is 8): a. Subtract x (which is 8) from right, so right becomes 12 - 8 = 4. b. Check if left equals right. They are equal (4 == 4), so this means the current index i (which is 3) is the middleIndex. We can return 3 as the index where the sum of elements to the left and to the right are equal.
There is no need to proceed further as we have found our solution.
If we hadn't found a middleIndex, we would return -1 at the end of the iteration. But in this case, we return the index 3.

In this example, the middleIndex that satisfies our condition is 3. Thus, using this approach, we efficiently found the balance point in a single pass through the array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findMiddleIndex(self, nums: List[int]) -> int:
5        # Initialize the prefix sum (sum of elements to the left of the current index)
6        prefix_sum = 0
7        # Initialize the total sum (sum of all elements in the array)
8        total_sum = sum(nums)
9      
10        # Iterate over the array
11        for index, value in enumerate(nums):
12            # Update the total sum by subtracting the current element
13            total_sum -= value
14          
15            # Compare the prefix sum and the remaining total sum,
16            # If they are equal, the current index is the middle index
17            if prefix_sum == total_sum:
18                return index
19          
20            # Update the prefix sum by adding the current element
21            prefix_sum += value
22      
23        # If no valid middle index is found, return -1
24        return -1
25

1class Solution {
2  
3    /**
4     * Find the index such that the sum of the elements to the left of the index 
5     * is equal to the sum of the elements to the right of the index.
6     * 
7     * @param nums An array of integers to analyze.
8     * @return The leftmost middle index if such an index exists, or -1 otherwise.
9     */
10    public int findMiddleIndex(int[] nums) {
11        // Initialize leftSum to keep track of the sum of elements to the left of the current index
12        int leftSum = 0;
13        // Calculate the total sum of all elements in the array
14        int totalSum = Arrays.stream(nums).sum();
15        // Initialize rightSum, which will be updated to keep track of the elements' sum to the right of the current index
16        int rightSum = totalSum;
17      
18        // Iterate over the array to determine the middle index where the leftSum equals rightSum
19        for (int i = 0; i < nums.length; ++i) {
20            // Exclude the current element from rightSum
21            rightSum -= nums[i];
22          
23            // Check if the leftSum equals rightSum at the current index
24            if (leftSum == rightSum) {
25                // If sums are equal, return the current index as the answer
26                return i;
27            }
28          
29            // Include the current element in the leftSum for the next iteration
30            leftSum += nums[i];
31        }
32      
33        // If no such index is found, return -1 to indicate failure
34        return -1;
35    }
36}
37

1#include <vector>
2#include <numeric> // For std::accumulate
3
4class Solution {
5public:
6    // This method finds the index such that the sum of the elements to the left
7    // of it is equal to the sum of the elements to the right of it.
8    int findMiddleIndex(vector<int>& nums) {
9        int leftSum = 0; // Sum of elements to the left of the current index
10        // Calculate the sum of all elements in the vector as the initial right sum.
11        int rightSum = std::accumulate(nums.begin(), nums.end(), 0); 
12
13        for (int index = 0; index < nums.size(); ++index) {
14            // Subtract the current element from right sum because it's not part of the right sum anymore.
15            rightSum -= nums[index];
16            // If the left sum is equal to the right sum, we have found the middle index.
17            if (leftSum == rightSum) {
18                return index;
19            }
20            // Add the current element to the left sum after checking, 
21            // since it will be part of the left sum when index is incremented.
22            leftSum += nums[index];
23        }
24        // Return -1 if no index can satisfy the condition.
25        return -1;
26    }
27};
28

1// Function to find the middle index where the sum of the numbers to the left
2// is equal to the sum of the numbers to the right.
3function findMiddleIndex(nums: number[]): number {
4    // Initialize the left sum to 0
5    let sumToLeft = 0;
6    // Compute the sum for the entire array, which will start as the sum to the right
7    let sumToRight = nums.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
8  
9    // Iterate through the nums array to find the middle index
10    for (let i = 0; i < nums.length; i++) {
11        // Subtract the current element from sumToRight before comparing
12        sumToRight -= nums[i];
13      
14        // If sumToLeft is equal to sumToRight, the middle index is found
15        if (sumToLeft === sumToRight) {
16            return i;
17        }
18      
19        // Add the current element to sumToLeft to use it for the next iteration's comparison
20        sumToLeft += nums[i];
21    }
22  
23    // If no index satisfies the condition, return -1
24    return -1;
25}
26

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the input list nums. This is because the code iterates through each element of nums exactly once in a single for-loop, performing a constant number of operations at each step.

Space Complexity

The space complexity of the provided code is O(1) since it uses a fixed amount of extra space: variables left, right, i, and x. The total amount of extra space required does not grow with the size of the input list, hence it is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

BFS

DFS

Both

Neither

I don’t know