Find the Middle Index in Array

Find the Middle Index in Array

What is this problem about?

The Find the Middle Index in Array interview question asks you to find an index i such that the sum of all elements to the left of i is equal to the sum of all elements to the right of i. If no such index exists, return -1. This is also known as the "Pivot Index" problem.

Why is this asked in interviews?

This "Easy" difficulty question is a standard part of Meta and Amazon interviews. It tests your ability to use the Prefix Sum interview pattern to optimize sum calculations. It evaluations whether you can avoid the $O(N^2)$ trap of re-calculating sums for every index and instead use a running total to achieve $O(N)$ time.

Algorithmic pattern used

This problem uses Prefix Sums or a Running Total.

1. Calculate the totalSum of the entire array.
2. Maintain a leftSum initialized to 0.
3. Iterate through the array. For each index $i$:
   • The rightSum is totalSum - leftSum - nums[i].
   • If leftSum == rightSum, then $i$ is the middle index.
   • Add nums[i] to leftSum and continue.

Example explanation

nums = [2, 3, -1, 8, 4]

1. totalSum = 16.
2. Index 0: left=0, right=14. No.
3. Index 1: left=2, right=11. No.
4. Index 2: left=5, right=9. No.
5. Index 3: left=4, right=4. Yes! Result: 3.

Common mistakes candidates make

• $O(N^2)$ solution: Using a nested loop to calculate left and right sums for every index.
• Empty sums: Forgetting that the sum of elements to the left of the first index is 0.
• Integer Overflow: While not common for small arrays, it's something to mention if values are huge.

Interview preparation tip

For any problem involving "sum of elements to the left/right," the formula RightSum = Total - LeftSum - Current is a classic optimization. Always calculate the total sum first to simplify your logic.