# Find the Middle Index in Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-middle-index-in-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-middle-index-in-array
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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:
# Approaches
## Brute Force with Nested Loops
This approach iterates through every possible index and, for each one, calculates the sum of elements to the left and the sum of elements to the right by using two separate inner loops. It's straightforward but inefficient.
**Time:** O(n^2), where n is the length of the `nums` array. For each of the `n` elements, we potentially iterate over the rest of the array to calculate the left and right sums, leading to a nested loop structure. · **Space:** O(1). We only use a few variables to store the sums and loop indices, regardless of the input array size.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient for larger arrays due to its quadratic time complexity.; Performs many redundant calculations, as sums are re-computed from scratch in each iteration.
### Explanation
In this brute-force method, we test every single index of the array to see if it qualifies as a `middleIndex`. We use a main loop that iterates from the first index (`0`) to the last. Inside this loop, for the current index `i`, we perform two more traversals. The first inner loop calculates the sum of all elements to the left of `i` (from index `0` to `i-1`). The second inner loop calculates the sum of all elements to the right of `i` (from index `i+1` to the end). After calculating both sums, we check if they are equal. If they are, we've found the leftmost `middleIndex` because our main loop started from the left. We can immediately return the index `i`. If the main loop finishes without finding any index where the sums are equal, we conclude that no such index exists and return `-1`.
```java
class Solution {
public int findMiddleIndex(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
int leftSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
int rightSum = 0;
for (int k = i + 1; k < n; k++) {
rightSum += nums[k];
}
if (leftSum == rightSum) {
return i;
}
}
return -1;
}
}
```
### Algorithm
- Iterate through each index `i` from `0` to `nums.length - 1`, considering it as a potential `middleIndex`.
- For each `i`, initialize a `leftSum` to 0.
- Calculate the `leftSum` by iterating with a second loop from index `j = 0` to `i - 1` and summing up `nums[j]`.
- For the same `i`, initialize a `rightSum` to 0.
- Calculate the `rightSum` by iterating with a third loop from index `k = i + 1` to `nums.length - 1` and summing up `nums[k]`.
- Compare `leftSum` and `rightSum`. If they are equal, `i` is a middle index. Since we are iterating from left to right, this is the leftmost one. Return `i`.
- If the outer loop completes without finding any such index, it means no `middleIndex` exists. Return `-1`.
## Optimized Approach using Prefix Sum
This approach significantly improves performance by avoiding recalculations. It first computes the total sum of the array. Then, it iterates through the array once more, maintaining a running `leftSum`. The `rightSum` can be calculated in constant time using the `totalSum` and the current `leftSum`.
**Time:** O(n), where n is the length of the `nums` array. The array is traversed a constant number of times (twice), making the overall complexity linear. · **Space:** O(1). We only use a couple of variables (`totalSum`, `leftSum`) to store the sums, which does not depend on the size of the input array.
**Pros:** Optimal time complexity of O(n).; Efficient and scalable for larger inputs.; Uses constant extra space.
**Cons:** Requires two passes over the array (one to get the total sum, and a second to find the index).
### Explanation
The key to optimizing this problem is to avoid the expensive O(n) sum calculations inside the main loop. We can achieve this by pre-calculating the total sum of the array. Let's call this `totalSum`.
With `totalSum`, if we know the sum of elements to the left of an index `i` (`leftSum`), we can find the sum of elements to its right (`rightSum`) with a simple formula: `rightSum = totalSum - leftSum - nums[i]`.
The algorithm works as follows:
1. Make a single pass through the array to compute `totalSum`.
2. Make a second pass. In this pass, we maintain a `leftSum` variable, initialized to 0. For each index `i`, we check if `leftSum` is equal to the calculated `rightSum`. If it is, we've found our answer. If not, we update `leftSum` by adding `nums[i]` to it, preparing it for the check at the next index `i+1`. This process continues until we find the leftmost middle index or exhaust the array.
```java
class Solution {
public int findMiddleIndex(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
int leftSum = 0;
for (int i = 0; i < nums.length; i++) {
// The right sum is totalSum - leftSum - nums[i]
if (leftSum == totalSum - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}
}
```
### Algorithm
- First, iterate through the entire array once to calculate the `totalSum` of all its elements.
- Initialize a `leftSum` variable to `0`.
- Iterate through the array again with an index `i` from `0` to `nums.length - 1`.
- In each iteration, the `rightSum` can be calculated without a new loop: `rightSum = totalSum - leftSum - nums[i]`.
- Check if `leftSum == rightSum`. If they are equal, `i` is the middle index. Return `i`.
- If the condition is not met, update `leftSum` for the next iteration by adding the current element: `leftSum += nums[i]`.
- If the loop finishes, it means no middle index was found. Return `-1`.
# Solutions
### Java
```java
class Solution {
public
int findMiddleIndex(int[] nums) {
int left = 0, right = Arrays.stream(nums).sum();
for (int i = 0; i < nums.length; ++i) {
right -= nums[i];
if (left == right) {
return i;
}
left += nums[i];
}
return -1;
}
}
```
### JavaScript
```javascript
/** * @param {number[]} nums * @return {number} */ var findMiddleIndex = function ( nums ) { let left = 0 , right = nums . reduce (( a , b ) => a + b ); for ( let i = 0 ; i < nums . length ; ++ i ) { right -= nums [ i ]; if ( left == right ) { return i ; } left += nums [ i ]; } return - 1 ; };
```
### CPP
```cpp
class Solution {
public:
int findMiddleIndex(vector &nums) {
int left = 0, right = accumulate(nums.begin(), nums.end(), 0);
for (int i = 0; i < nums.size(); ++i) {
right -= nums[i];
if (left == right) {
return i;
}
left += nums[i];
}
return -1;
}
};
```
### Python
```python
class Solution:
def findMiddleIndex(self, nums: List[int]) -> int: left, right = 0, sum(nums) for i, x in enumerate(nums): right -= x if left == right: return i left += x return - 1
```