Find Pivot Index

Find Pivot Index

What is this problem about?

The Find Pivot Index interview question asks you to find an index where the sum of all numbers to its strictly left is equal to the sum of all numbers to its strictly right. If no such index exists, return -1. If multiple exist, return the leftmost one. This Find Pivot Index coding problem is a fundamental application of prefix totals.

Why is this asked in interviews?

Companies like Meta, Amazon, and Microsoft ask this to evaluate your mastery of the Prefix Sum interview pattern. It tests if you can solve an equilibrium problem in $O(N)$ time and $O(1)$ extra space by calculating the "right sum" based on the "total sum" and the "left sum."

Algorithmic pattern used

This problem follows the Running Total pattern.

1. Total Sum: Calculate the sum of the entire array first.
2. Iterate: Maintain a leftSum variable, initialized to 0.
3. Check Condition: For each index i:
   • The rightSum is implicitly TotalSum - leftSum - nums[i].
   • If leftSum == rightSum, then i is the pivot.
4. Update: Add nums[i] to leftSum and move to the next index.

Example explanation

Array: [1, 7, 3, 6, 5, 6]

1. Total Sum = 28.
2. index 0 (1): left=0, right=27.
3. index 1 (7): left=1, right=20.
4. index 2 (3): left=8, right=17.
5. index 3 (6): left=11, right=11. MATCH! Result: index 3.

Common mistakes candidates make

• Nested Loops: Using a second loop inside to calculate sums for every index, resulting in $O(N^2)$.
• Strictly Left/Right: Including the pivot element itself in either the left or right sum.
• Empty Boundaries: Failing to handle index 0 or $n-1$ correctly (where the left or right sum is 0).

Interview preparation tip

Always look for ways to avoid recalculating sums. If you have the total sum, you only need to track the sum from one side to know the sum of the other. This is a vital Array interview pattern optimization.