Skip to main content
Talentd

Find the Middle Index in Array - Solution & Explanation

EasyArrayPrefix Sum19 min readAsked at: Amazon, Google, Bloomberg +1
Practice this problem

Problem Statement

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.

In C, we first calculate the total sum of the array. Then, as we iterate through the array, we maintain a left running sum. If the condition leftSum * 2 + nums[i] == totalSum is true, the current index is returned as the middle index. If no such index is found, -1 is returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), since we use only a constant amount of extra space.

Try this approach in the editor →

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.

In this C brute force approach, we iterate through each index and compute the sum on the left and right side of the index independently. If left and right sums match, that index is returned as the middleIndex.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), because for each index we compute left and right sums by iterating over the array.
Space Complexity: O(1), only using constant extra space for variables.

Try this approach in the editor →

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:

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum Approach

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), since we use only a constant amount of extra space.

Brute Force Approach

Time Complexity: O(n^2), because for each index we compute left and right sums by iterating over the array.
Space Complexity: O(1), only using constant extra space for variables.

Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^2)O(1)Good for understanding the problem logic or very small arrays
Prefix SumO(n)O(1)Best general solution; avoids repeated summation and scales efficiently

Video Solution

Find the middle index in array (Leetcode) • RusanCodingTech • 2,514 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find the Middle Index in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Pivot Index

Next

Left and Right Sum Differences