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 of0
. 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 thenums
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 andx
is the value atnums[i]
.a. Subtract the current element
x
fromright
because this step effectively updates the sum to the right of the current index to excludex
(sincex
either falls on the middle or moves to the left part in the next step).b. Check if
left
is equal toright
. If yes, we have found amiddleIndex
since the sum of elements on either side ofi
is the same. Therefore, returni
.c. If
left
does not equalright
, it means the current indexi
is not themiddleIndex
. Addx
toleft
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 EvaluatorExample 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 of0
. 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 thenums
array, which is2 + 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]
is2
): a. Subtractx
(which is2
) fromright
, soright
becomes16 - 2 = 14
. b. Check ifleft
equalsright
. They are not equal (0 != 14
), so we move on. c. Finally, addx
toleft
, makingleft
now0 + 2 = 2
. -
For
i = 1
(x = nums[1]
is3
): a. Subtractx
(which is3
) fromright
, soright
becomes14 - 3 = 11
. b. Check ifleft
equalsright
. They are not equal (2 != 11
), so we move on. c. Addx
toleft
, makingleft
now2 + 3 = 5
. -
For
i = 2
(x = nums[2]
is-1
): a. Subtractx
(which is-1
) fromright
, soright
becomes11 - (-1) = 12
. b. Check ifleft
equalsright
. They are not equal (5 != 12
), so we move on. c. Addx
toleft
, makingleft
now5 - 1 = 4
. -
For
i = 3
(x = nums[3]
is8
): a. Subtractx
(which is8
) fromright
, soright
becomes12 - 8 = 4
. b. Check ifleft
equalsright
. They are equal (4 == 4
), so this means the current indexi
(which is3
) is themiddleIndex
. We can return3
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 index3
.
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.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first