Find the Middle Index in Array solution and explanation
Google
9 more videos on this problem
Find the middle index in array (Leetcode)RusanCodingTech · 13:20 · 2K views
Leetcode 1991 : Find the Middle Index in ArrayLearn Together · 12:45 · 2K views
Leetcode Biweekly Contest 60 | Find the Middle Index in Array | Find All Groups of Farmlandcode Explainer · 10:43 · 2K views
Leetcode Biweekly Contest 60 | 1991. Find the Middle Index in Array(Easy) in EnglishCompetitive Somya · 2:55 · 1K views
1991. Find the Middle Index in Array (Leetcode Easy)Programming Live with Larry · 4:40 · 1K views
Find the Middle Index in Array | LeetCode | C#Daily Code · 4:35 · 1K views
Find Pivot Index- Leetcode 724 | Find the middle index in array- Leetcode 1991 | #9 | Entri ElevateEntri Elevate Coding हिन्दी · 7:14 · 954 views
Find the Middle Index in Array Leetcode 1991 || Biweekly contest || Coding Culture5 Minutes Code · 6:05 · 745 views
Python Programming - Find the Middle Index in Array | JavaScript, Java and C++ | LeetCode #1991CodingNinja · 5:46 · 713 views
Leetcode problem: 1991. Find the Middle Index in ArrayDetective Coder · 9:15 · 567 views
The problem
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.
Example 1:
Input: nums = [2,3,-1,8,4] Output: 3 Explanation: The sum of the numbers before index 3 is: 2 + 3 + -1 = 4 The sum of the numbers after index 3 is: 4 = 4
Example 2:
Input: nums = [1,-1,4] Output: 2 Explanation: The sum of the numbers before index 2 is: 1 + -1 = 0 The sum of the numbers after index 2 is: 0
Example 3:
Input: nums = [2,5] Output: -1 Explanation: There is no valid middleIndex.
Constraints:
1 <= nums.length <= 100-1000 <= nums[i] <= 1000
Note: This question is the same as 724: https://leetcode.com/problems/find-pivot-index/
Approach overview
Problem Overview: You are given an integer array and need to return the index where the sum of elements to the left equals the sum of elements to the right. If multiple indices satisfy the condition, return the leftmost one. If none exist, return -1. This is a classic balance-point problem that relies on efficient sum calculations within an array.
Approach 1: Brute Force Approach (O(n^2) time, O(1) space)
The straightforward method checks every index and computes the sum of elements on its left and right. For each position i, iterate through the array from 0 to i-1 to calculate the left sum, and from i+1 to n-1 for the right sum. If the two sums match, return the index immediately. This method is easy to implement and useful for understanding the problem constraints, but repeated summation makes it inefficient for large arrays. The nested iteration leads to O(n^2) time complexity while using constant extra memory.
Approach 2: Prefix Sum Approach (O(n) time, O(1) space)
The optimal strategy avoids recomputing sums by tracking them incrementally using the prefix sum technique. First compute the total sum of the entire array. Then iterate through the array while maintaining a running leftSum. For each index i, calculate the right sum using rightSum = totalSum - leftSum - nums[i]. If leftSum == rightSum, you found the middle index and return it. After the check, update leftSum += nums[i] and continue scanning. This approach ensures every element is processed exactly once, producing O(n) time complexity and O(1) extra space.
The key insight is that the right side sum does not need to be recomputed from scratch. Since the total sum is known, subtracting the current value and the accumulated left sum instantly gives the right sum. This transforms an otherwise quadratic process into a linear scan.
Recommended for interviews: Start by explaining the brute force method to demonstrate baseline reasoning about left and right sums. Then transition to the prefix sum optimization, which interviewers typically expect. The O(n) solution shows you recognize repeated work and eliminate it using cumulative sums, a common pattern in prefix sum and array problems.
Approach 1: Prefix Sum Approach
This approach uses the concept of prefix sums to calculate sums on both sides of each index efficiently. We compute the total sum of the array and iterate through each index, maintaining a running sum from the left side. At each index, we simply check if twice the running sum equals the total sum minus the current element. If it does, we've found our middle index.
def find_middle_index(nums):
total_sum = sum(nums)
left_sum = 0
for i, num in enumerate(nums):
if left_sum * 2 + num == total_sum:
return i
left_sum += num
return -1
if __name__ == "__main__":
nums = [2, 3, -1, 8, 4]
result = find_middle_index(nums)
print(result)class Solution {
public int findMiddleIndex(int[] nums) {
int totalSum = 0, leftSum = 0;
for (int num : nums) {
totalSum += num;
}
for (int i = 0; i < nums.length; i++) {
if (leftSum * 2 + nums[i] == totalSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 3, -1, 8, 4};
int result = solution.findMiddleIndex(nums);
System.out.println(result);
}
}#include <iostream>
#include <vector>
using namespace std;
int findMiddleIndex(vector<int>& nums) {
int totalSum = 0, leftSum = 0;
for (int num : nums) {
totalSum += num;
}
for (int i = 0; i < nums.size(); i++) {
if (leftSum * 2 + nums[i] == totalSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}
int main() {
vector<int> nums = {2, 3, -1, 8, 4};
int result = findMiddleIndex(nums);
cout << result << endl;
return 0;
}function findMiddleIndex(nums) {
let totalSum = nums.reduce((a, b) => a + b, 0);
let leftSum = 0;
for (let i = 0; i < nums.length; i++) {
if (leftSum * 2 + nums[i] === totalSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}
const nums = [2, 3, -1, 8, 4];
const result = findMiddleIndex(nums);
console.log(result);#include <stdio.h>
int findMiddleIndex(int* nums, int numsSize) {
int totalSum = 0, leftSum = 0;
for (int i = 0; i < numsSize; i++) {
totalSum += nums[i];
}
for (int i = 0; i < numsSize; i++) {
if (leftSum * 2 + nums[i] == totalSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}
int main() {
int nums[] = {2, 3, -1, 8, 4};
int result = findMiddleIndex(nums, sizeof(nums) / sizeof(nums[0]));
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int FindMiddleIndex(int[] nums) {
int totalSum = 0, leftSum = 0;
foreach (int num in nums) {
totalSum += num;
}
for (int i = 0; i < nums.Length; i++) {
if (leftSum * 2 + nums[i] == totalSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {2, 3, -1, 8, 4};
int result = solution.FindMiddleIndex(nums);
Console.WriteLine(result);
}
}In Python, we use the built-in sum() function to calculate the total sum of the array. As we iterate with enumerate(), we maintain a left_sum and check our condition to determine the middle index.
Time Complexity: O(n), due to the single pass through the array.
Space Complexity: O(1), as we're using only a few additional variables.
Approach 2: Brute Force Approach
In the brute force approach, we iterate over each possible index in the array and calculate the sum of elements on both sides of that index. This approach involves two nested iterations: one to determine the left sum and another for the right sum for each index.
def find_middle_index(nums):
for i in range(len(nums)):
left_sum = sum(nums[:i])
right_sum = sum(nums[i+1:])
if left_sum == right_sum:
return i
return -1
if __name__ == "__main__":
nums = [2, 3, -1, 8, 4]
result = find_middle_index(nums)
print(result)class Solution {
public int findMiddleIndex(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int leftSum = 0, rightSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
for (int j = i + 1; j < nums.length; j++) {
rightSum += nums[j];
}
if (leftSum == rightSum) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 3, -1, 8, 4};
int result = solution.findMiddleIndex(nums);
System.out.println(result);
}
}#include <iostream>
#include <vector>
using namespace std;
int findMiddleIndex(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
int leftSum = 0, rightSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
for (int j = i + 1; j < nums.size(); j++) {
rightSum += nums[j];
}
if (leftSum == rightSum) {
return i;
}
}
return -1;
}
int main() {
vector<int> nums = {2, 3, -1, 8, 4};
int result = findMiddleIndex(nums);
cout << result << endl;
return 0;
}function findMiddleIndex(nums) {
for (let i = 0; i < nums.length; i++) {
const leftSum = nums.slice(0, i).reduce((a, b) => a + b, 0);
const rightSum = nums.slice(i + 1).reduce((a, b) => a + b, 0);
if (leftSum === rightSum) {
return i;
}
}
return -1;
}
const nums = [2, 3, -1, 8, 4];
const result = findMiddleIndex(nums);
console.log(result);#include <stdio.h>
int findMiddleIndex(int* nums, int numsSize) {
for (int i = 0; i < numsSize; i++) {
int leftSum = 0, rightSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
for (int j = i + 1; j < numsSize; j++) {
rightSum += nums[j];
}
if (leftSum == rightSum) {
return i;
}
}
return -1;
}
int main() {
int nums[] = {2, 3, -1, 8, 4};
int result = findMiddleIndex(nums, sizeof(nums) / sizeof(nums[0]));
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int FindMiddleIndex(int[] nums) {
for (int i = 0; i < nums.Length; i++) {
int leftSum = 0, rightSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
for (int j = i + 1; j < nums.Length; j++) {
rightSum += nums[j];
}
if (leftSum == rightSum) {
return i;
}
}
return -1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {2, 3, -1, 8, 4};
int result = solution.FindMiddleIndex(nums);
Console.WriteLine(result);
}
}In Python, for each potential middle index, we calculate sums of the prefix and suffix using the slicing method. If the sums match, the current index becomes the middleIndex.
Time Complexity: O(n^2), due to the use of slicing which iteratively computes sums left and right at each index.
Space Complexity: O(1).
Approach 3: Prefix Sum
We define two variables l and r, representing the sum of elements to the left and right of index i in the array nums, respectively. Initially, l = 0 and r = sum_{i = 0}^{n - 1} nums[i].
We traverse the array nums, and for the current number x, we update r = r - x. If l = r at this point, it means the current index i is the middle index, and we return it directly. Otherwise, we update l = l + x and continue to the next number.
If the traversal ends without finding a middle index, return -1.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Similar problems:
function findMiddleIndex(nums: number[]): number {
let l = 0;
let r = nums.reduce((a, b) => a + b, 0);
for (let i = 0; i < nums.length; ++i) {
r -= nums[i];
if (l === r) {
return i;
}
l += nums[i];
}
return -1;
}func findMiddleIndex(nums []int) int {
l, r := 0, 0
for _, x := range nums {
r += x
}
for i, x := range nums {
r -= x
if l == r {
return i
}
l += x
}
return -1
}impl Solution {
pub fn find_middle_index(nums: Vec<i32>) -> i32 {
let mut l = 0;
let mut r: i32 = nums.iter().sum();
for (i, &x) in nums.iter().enumerate() {
r -= x;
if l == r {
return i as i32;
}
l += x;
}
-1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n), due to the single pass through the array. |
| Brute Force Approach | Time Complexity: O(n^2), due to the use of slicing which iteratively computes sums left and right at each index. |
| Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Good for understanding the problem logic or very small arrays |
| Prefix Sum | O(n) | O(1) | Best general solution; avoids repeated summation and scales efficiently |
Frequently asked questions
Is Find the Middle Index in Array easy or hard?
Find the Middle Index in Array is categorized as an Easy problem. The logic becomes straightforward once you recognize the prefix sum pattern, allowing a clean O(n) solution with constant extra space.
Find the Middle Index in Array Python/Java solution
Most implementations follow the same prefix sum logic across languages. Compute the total sum, iterate through the array, maintain a running left sum, and check whether leftSum equals totalSum - leftSum - nums[i]. This approach works consistently in Python, Java, C++, JavaScript, C#, and C.
How to solve Find the Middle Index in Array in O(n)?
First compute the total sum of the array. Traverse the array while maintaining a running leftSum. For each index i, compute rightSum = totalSum - leftSum - nums[i]. If leftSum equals rightSum, return that index. Update leftSum by adding nums[i] and continue.
What is the best approach for Find the Middle Index in Array?
The prefix sum approach is the most efficient solution. Compute the total array sum, then iterate while maintaining a running left sum. The right sum at each index can be calculated as totalSum - leftSum - currentValue, giving an O(n) time and O(1) space solution.
Is Find the Middle Index in Array asked at Google/Amazon/Meta?
Problems involving prefix sums and balance indices frequently appear in technical interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying pattern of prefix sums and running totals is common in array interview problems.
What data structure is used in Find the Middle Index in Array?
The problem primarily uses arrays and the prefix sum technique. No additional data structures like hash maps or stacks are required because the solution relies on maintaining running sums during a single pass.
What is the time complexity of Find the Middle Index in Array?
The optimal prefix sum solution runs in O(n) time because the array is scanned once after computing the total sum. A naive brute force method recalculates left and right sums for every index, resulting in O(n^2) time complexity.