47. Find Pivot Index

🔗 LeetCode Problem: 724. Find Pivot Index
📊 Difficulty: Easy
🏷️ Topics: Array, Prefix Sum

Problem Statement

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the right of the index.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints: - 1 <= nums.length <= 10^4 - -1000 <= nums[i] <= 1000

Note: This question is the same as 1991: Find the Middle Index in Array.

🎨 Visual Understanding

The Problem Visualized

nums = [1, 7, 3, 6, 5, 6]
Index:  0  1  2  3  4  5

Check index 0:
  Left sum = 0 (no elements)
  Right sum = 7 + 3 + 6 + 5 + 6 = 27
  0 ≠ 27 ✗

Check index 1:
  Left sum = 1
  Right sum = 3 + 6 + 5 + 6 = 20
  1 ≠ 20 ✗

Check index 2:
  Left sum = 1 + 7 = 8
  Right sum = 6 + 5 + 6 = 17
  8 ≠ 17 ✗

Check index 3:
  Left sum = 1 + 7 + 3 = 11
  Right sum = 5 + 6 = 11
  11 = 11 ✓ PIVOT!

Answer: 3

Key Observation: Use Total Sum

At any pivot index i:
  leftSum = sum of elements [0, i-1]
  rightSum = sum of elements [i+1, n-1]

If leftSum = rightSum, then i is pivot.

Key insight:
  leftSum + nums[i] + rightSum = totalSum

If leftSum = rightSum:
  leftSum + nums[i] + leftSum = totalSum
  2 × leftSum + nums[i] = totalSum
  leftSum = (totalSum - nums[i]) / 2

OR simpler:
  leftSum + nums[i] + rightSum = totalSum
  If leftSum = rightSum:
  rightSum = totalSum - leftSum - nums[i]

Check: leftSum = rightSum

Visual Process

nums = [1, 7, 3, 6, 5, 6]
totalSum = 28

Index 0: leftSum = 0
  rightSum = totalSum - leftSum - nums[0] = 28 - 0 - 1 = 27
  0 ≠ 27 ✗

Index 1: leftSum = 1
  rightSum = totalSum - leftSum - nums[1] = 28 - 1 - 7 = 20
  1 ≠ 20 ✗

Index 2: leftSum = 1 + 7 = 8
  rightSum = totalSum - leftSum - nums[2] = 28 - 8 - 3 = 17
  8 ≠ 17 ✗

Index 3: leftSum = 1 + 7 + 3 = 11
  rightSum = totalSum - leftSum - nums[3] = 28 - 11 - 6 = 11
  11 = 11 ✓

Return 3

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

For each index i:
1. Calculate sum of left side [0, i-1]
2. Calculate sum of right side [i+1, n-1]
3. If equal, return i

Return -1 if no pivot found

Implementation

public int pivotIndex(int[] nums) {
    int n = nums.length;

    for (int i = 0; i < n; i++) {
        // Calculate left sum
        int leftSum = 0;
        for (int j = 0; j < i; j++) {
            leftSum += nums[j];
        }

        // Calculate right sum
        int rightSum = 0;
        for (int j = i + 1; j < n; j++) {
            rightSum += nums[j];
        }

        // Check if pivot
        if (leftSum == rightSum) {
            return i;
        }
    }

    return -1;
}

⏰ Time: O(n²) - for each index, calculate both sums
💾 Space: O(1) - only variables

✅ Approach 2: Prefix Sum (One Pass)

The Breakthrough Insight 💡

Core Logic:

Use relationship between total sum and left sum:

totalSum = leftSum + nums[i] + rightSum

If leftSum = rightSum (pivot condition):
  rightSum = totalSum - leftSum - nums[i]

So check: leftSum == (totalSum - leftSum - nums[i])

Algorithm:
1. Calculate totalSum of array
2. Initialize leftSum = 0
3. For each index i:
   - rightSum = totalSum - leftSum - nums[i]
   - If leftSum == rightSum: return i
   - leftSum += nums[i] (prepare for next iteration)
4. Return -1 if no pivot

Visual Explanation:

nums = [1, 7, 3, 6, 5, 6]
totalSum = 28

At index 3:
  leftSum = 11 (sum of [1, 7, 3])
  nums[3] = 6
  rightSum = totalSum - leftSum - nums[3]
           = 28 - 11 - 6
           = 11

  leftSum (11) == rightSum (11) ✓

Visual:
[1  7  3][6][5  6]
 sum=11  ↑  sum=11
      pivot

Why This Works:

Total array sum:
[left elements] [pivot] [right elements]

totalSum = leftSum + pivot + rightSum

For pivot index:
  leftSum = rightSum

Therefore:
  totalSum = leftSum + pivot + leftSum
  totalSum = 2×leftSum + pivot
  leftSum = (totalSum - pivot) / 2

Or check directly:
  rightSum = totalSum - leftSum - pivot
  If leftSum == rightSum → found pivot!

Implementation

public int pivotIndex(int[] nums) {
    // Calculate total sum
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }

    // Check each index as potential pivot
    int leftSum = 0;
    for (int i = 0; i < nums.length; i++) {
        // rightSum = totalSum - leftSum - nums[i]
        // Check if leftSum == rightSum
        if (leftSum == totalSum - leftSum - nums[i]) {
            return i;
        }
        // Update leftSum for next iteration
        leftSum += nums[i];
    }

    return -1;
}

⏰ Time: O(n) - two passes (one for total, one for checking)
💾 Space: O(1) - only variables

🔍 Step-by-Step Execution

Example: nums = [1, 7, 3, 6, 5, 6]

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, 7, 3, 6, 5, 6]
n = 6


Step 1: Calculate totalSum
═══════════════════════════════════════════════════════════════════
totalSum = 1 + 7 + 3 + 6 + 5 + 6 = 28


Step 2: Find pivot (initialize leftSum = 0)
═══════════════════════════════════════════════════════════════════


Check i = 0:
───────────────────────────────────────────────────────────────────
leftSum = 0 (no elements to the left)
nums[0] = 1
rightSum = totalSum - leftSum - nums[0]
         = 28 - 0 - 1
         = 27

Check: leftSum == rightSum?
       0 == 27? NO ✗

Update leftSum:
  leftSum += nums[0]
  leftSum = 0 + 1 = 1

Visual:
[][1][7, 3, 6, 5, 6]
 ↑  ↑  sum = 27
left=0


Check i = 1:
───────────────────────────────────────────────────────────────────
leftSum = 1
nums[1] = 7
rightSum = totalSum - leftSum - nums[1]
         = 28 - 1 - 7
         = 20

Check: leftSum == rightSum?
       1 == 20? NO ✗

Update leftSum:
  leftSum += nums[1]
  leftSum = 1 + 7 = 8

Visual:
[1][7][3, 6, 5, 6]
 ↑  ↑  sum = 20
left=1


Check i = 2:
───────────────────────────────────────────────────────────────────
leftSum = 8
nums[2] = 3
rightSum = totalSum - leftSum - nums[2]
         = 28 - 8 - 3
         = 17

Check: leftSum == rightSum?
       8 == 17? NO ✗

Update leftSum:
  leftSum += nums[2]
  leftSum = 8 + 3 = 11

Visual:
[1, 7][3][6, 5, 6]
 sum=8 ↑  sum = 17


Check i = 3:
───────────────────────────────────────────────────────────────────
leftSum = 11
nums[3] = 6
rightSum = totalSum - leftSum - nums[3]
         = 28 - 11 - 6
         = 11

Check: leftSum == rightSum?
       11 == 11? YES ✓

Found pivot at index 3!
Return 3

Visual:
[1, 7, 3][6][5, 6]
 sum = 11 ↑  sum = 11
        PIVOT!


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 3
═══════════════════════════════════════════════════════════════════

Example 2: nums = [2, 1, -1]

Step 1: Calculate totalSum
═══════════════════════════════════════════════════════════════════
totalSum = 2 + 1 + (-1) = 2


Step 2: Find pivot
═══════════════════════════════════════════════════════════════════

Check i = 0:
───────────────────────────────────────────────────────────────────
leftSum = 0
nums[0] = 2
rightSum = totalSum - leftSum - nums[0]
         = 2 - 0 - 2
         = 0

Check: leftSum == rightSum?
       0 == 0? YES ✓

Found pivot at index 0!
Return 0

Visual:
[][2][1, -1]
 ↑  ↑  sum = 0
left=0

Explanation: Empty left sum = 0, right sum = 1 + (-1) = 0


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 0
═══════════════════════════════════════════════════════════════════

Example 3: nums = [1, 2, 3] (No pivot)

Step 1: Calculate totalSum
═══════════════════════════════════════════════════════════════════
totalSum = 1 + 2 + 3 = 6


Step 2: Find pivot
═══════════════════════════════════════════════════════════════════

Check i = 0:
  leftSum = 0, rightSum = 6 - 0 - 1 = 5
  0 ≠ 5 ✗
  leftSum = 1

Check i = 1:
  leftSum = 1, rightSum = 6 - 1 - 2 = 3
  1 ≠ 3 ✗
  leftSum = 3

Check i = 2:
  leftSum = 3, rightSum = 6 - 3 - 3 = 0
  3 ≠ 0 ✗
  leftSum = 6

No pivot found!


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: -1
═══════════════════════════════════════════════════════════════════

🔍 Edge Cases

Case 1: Pivot at start (left sum = 0)
Input: nums = [2, 1, -1]
Output: 0
Explanation: Left = 0, Right = 1 + (-1) = 0

Case 2: Pivot at end (right sum = 0)
Input: nums = [-1, -1, 0, 1, 1, 0]
Output: 5
Explanation: Left = -1 + (-1) + 0 + 1 + 1 = 0, Right = 0

Case 3: No pivot exists
Input: nums = [1, 2, 3]
Output: -1

Case 4: Single element (both sides empty)
Input: nums = [0]
Output: 0
Explanation: Left = 0, Right = 0

Case 5: All zeros
Input: nums = [0, 0, 0]
Output: 0
Explanation: Any index works, return leftmost (0)

Case 6: Negative numbers
Input: nums = [-1, -1, -1, 1, 1, 1]
Output: -1
Explanation: No pivot

Case 7: Multiple valid pivots (return leftmost)
Input: nums = [0, 0, 0, 0]
Output: 0
Explanation: All are pivots, return leftmost

Case 8: Two elements
Input: nums = [1, -1]
Output: -1
Explanation: No pivot possible

Common Mistakes

Mistake 1: Not updating leftSum correctly
❌ Wrong: 
    if (leftSum == rightSum) {
        leftSum += nums[i];  // Update before returning
        return i;
    }
✓ Right: 
    if (leftSum == rightSum) {
        return i;  // Return immediately
    }
    leftSum += nums[i];  // Update after check
Reason: Once pivot found, return immediately

Mistake 2: Calculating rightSum instead of using formula
❌ Wrong: 
    int rightSum = 0;
    for (int j = i + 1; j < n; j++) {
        rightSum += nums[j];  // O(n) operation
    }
✓ Right: 
    int rightSum = totalSum - leftSum - nums[i];  // O(1)
Reason: Use mathematical relationship for efficiency

Mistake 3: Not initializing leftSum to 0
❌ Wrong: 
    int leftSum;  // Uninitialized
    for (int i = 0; i < n; i++) {
        if (leftSum == totalSum - leftSum - nums[i]) ...
    }
✓ Right: 
    int leftSum = 0;  // Initialize
Reason: First element has no left elements (sum = 0)

Mistake 4: Wrong condition check
❌ Wrong: 
    if (leftSum == rightSum - nums[i]) {
        // Wrong formula
    }
✓ Right: 
    if (leftSum == totalSum - leftSum - nums[i]) {
        // Correct: rightSum = total - left - current
    }
Reason: Must subtract both leftSum AND current element

Mistake 5: Including current element in leftSum before check
❌ Wrong: 
    leftSum += nums[i];
    if (leftSum == totalSum - leftSum) {
        // leftSum already includes nums[i]!
    }
✓ Right: 
    if (leftSum == totalSum - leftSum - nums[i]) {
        // Check BEFORE updating
    }
    leftSum += nums[i];
Reason: leftSum should not include current element during check

Mistake 6: Not handling edge cases
❌ Wrong: 
    // Assume array has at least 3 elements
✓ Right: 
    // Works for array of size 1 or 2
    if (leftSum == totalSum - leftSum - nums[i]) ...
Reason: Algorithm naturally handles all sizes

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

Approach 2: Prefix Sum (RECOMMENDED)
  Time: O(n)
  Space: O(1)
  Use: Optimal solution

🔑 The Core Insight

Mathematical Relationship:
═══════════════════════════════════════════════════════════════

At any index i:
  totalSum = leftSum + nums[i] + rightSum

For pivot index:
  leftSum = rightSum

Therefore:
  rightSum = totalSum - leftSum - nums[i]

Check:
  if leftSum == rightSum
  if leftSum == totalSum - leftSum - nums[i]

This allows O(1) check per index!

Algorithm Pattern:
═══════════════════════════════════════════════════════════════

1. Calculate totalSum (one pass)
2. Initialize leftSum = 0
3. For each index i:
   a. Check if leftSum == totalSum - leftSum - nums[i]
   b. If yes: return i (found pivot)
   c. Update: leftSum += nums[i]
4. Return -1 (no pivot found)

Key Points:
- Update leftSum AFTER checking
- Don't include nums[i] in leftSum during check
- Empty left/right sides have sum = 0 (naturally handled)

Visual Understanding:
═══════════════════════════════════════════════════════════════

[left elements][pivot][right elements]
 sum = L        nums[i]  sum = R

Total: L + nums[i] + R = totalSum

If pivot: L = R
Then: R = totalSum - L - nums[i]

Check: L == totalSum - L - nums[i]

Example:
nums = [1, 7, 3, 6, 5, 6]
       [1, 7, 3][6][5, 6]
        sum=11  ↑  sum=11

totalSum = 28
At i=3: leftSum = 11, nums[3] = 6
rightSum = 28 - 11 - 6 = 11
leftSum == rightSum ✓

Time Complexity:
═══════════════════════════════════════════════════════════════

One pass to calculate total: O(n)
One pass to find pivot: O(n)
Total: O(n) + O(n) = O(n)

Each check is O(1), not O(n) like brute force!

Space Complexity:
═══════════════════════════════════════════════════════════════

Only variables (totalSum, leftSum):
Space: O(1)

No need to store prefix sum array!
This is better than typical prefix sum problems.

🎯 Pattern Recognition

Problem Type: Balance Point Using Prefix Sum
Core Pattern: Running Sum with Mathematical Property

When to Apply:
✓ Find balance/equilibrium point
✓ Left sum equals right sum
✓ Single pass solution needed
✓ O(1) space requirement

Recognition Keywords:
- "Pivot index"
- "Left sum equals right sum"
- "Balance point"
- "Equilibrium"
- "Equal sums on both sides"

Relationship to Prefix Sum:
┌────────────────────────────────────────────┐
│ Problem #46: Store prefix sum array       │
│ Problem #47: Don't store, just track sum  │
│                                            │
│ Both use cumulative sum concept!          │
└────────────────────────────────────────────┘

Key Difference from Problem #46:
- #46: Need range queries → store prefix array
- #47: Need running check → just track current sum

Related Problems:
- Find the Middle Index in Array (LC 1791) - Same problem
- Product of Array Except Self (LC 238)
- Partition Array Into Three Parts With Equal Sum (LC 1013)

🧠 Interview Strategy

Step 1: "Need to find where left sum equals right sum"
Step 2: "Brute force: O(n²) - recalculate sums each time"
Step 3: "Use mathematical relationship with total sum"
Step 4: "rightSum = totalSum - leftSum - nums[i]"
Step 5: "Check leftSum == rightSum in O(1)"
Step 6: "Single pass: O(n) time, O(1) space"

Key Points to Mention:
- Recognize balance point problem
- Use total sum relationship
- Running leftSum (prefix sum concept)
- rightSum = totalSum - leftSum - current
- Check condition: leftSum == rightSum
- Update leftSum after checking
- Edge cases handled naturally (empty sides = 0)
- Two passes: calculate total, find pivot
- O(n) time, O(1) space
- No need to store prefix array!

Why Not Store Prefix Array?
"Unlike range sum queries where we need multiple queries,
here we only make one pass checking each index. So we can
use a running sum instead of storing the entire prefix array.
This saves space while maintaining O(n) time."

The Mathematical Insight:
"The key is recognizing that if we know the total sum
and the left sum, we can calculate the right sum instantly:
rightSum = totalSum - leftSum - current. This turns an
O(n) calculation into O(1)."

This shows great optimization thinking! 🏆

📝 Quick Revision Notes

🎯 Core Concept:

Use totalSum relationship: rightSum = totalSum - leftSum - nums[i]. Check leftSum == rightSum in O(1). Track running leftSum, no array needed!

⚡ Quick Implementation:

import java.util.Arrays;

class Test {
  public int pivotIndex(int[] a) {
    int totalSum = Arrays.stream(a).sum();
    int leftSum = 0;

    for (int i = 0; i < a.length; i++) {
      int rightSum = totalSum - leftSum - a[i];

      if (leftSum == rightSum) {
        return i;
      }

      // updated for next index like running sum
      leftSum += a[i];
    }

    return -1;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.pivotIndex(new int[] { 1, 7, 3, 6, 5, 6 }));
    System.out.println(t.pivotIndex(new int[] { 1, 2, 3 }));
    System.out.println(t.pivotIndex(new int[] { 2, 1, -1 }));
  }
}

🔑 Key Insights:

Pattern: Balance point using running sum
Formula: rightSum = totalSum - leftSum - nums[i]
Check: leftSum == rightSum (or leftSum == totalSum - leftSum - nums[i])
Update: leftSum += nums[i] AFTER checking
Edge case: Empty sides naturally = 0
First pass: Calculate totalSum
Second pass: Find pivot with running leftSum
Time: O(n) - two passes
Space: O(1) - no array stored!
Return: First (leftmost) pivot, or -1

🎪 Memory Aid:

"TOTAL minus LEFT minus CURRENT = RIGHT! Check BEFORE update!"
Think: "Running sum, check balance, update after!"

💡 The Key Formula:

totalSum = leftSum + nums[i] + rightSum

If pivot (leftSum = rightSum):
  rightSum = totalSum - leftSum - nums[i]

Check: leftSum == totalSum - leftSum - nums[i]

Visual:
[LEFT][i][RIGHT]
  L   ↑    R

Total = L + nums[i] + R
If L = R: R = Total - L - nums[i]

🔥 Why This is Better:

Brute Force: Recalculate both sums
  Time: O(n²)

Optimized: Use mathematical relationship
  Time: O(n)

But NO extra space needed!
  Space: O(1)

Better than storing prefix array for this problem!

⚠️ Critical Detail:

// WRONG order:
leftSum += nums[i];
if (leftSum == ...) { }  // leftSum already includes nums[i]!

// RIGHT order:
if (leftSum == totalSum - leftSum - nums[i]) { }  // Check first
leftSum += nums[i];  // Update after

Find the Middle Index in Array (LC 1791) - Identical problem
Product of Array Except Self (LC 238)
Partition Array Into Three Parts With Equal Sum (LC 1013)
Range Sum Query - Immutable (LC 303) - Uses prefix array

Happy practicing! 🎯

47. Find Pivot Index

Problem Statement

🎨 Visual Understanding

The Problem Visualized

Key Observation: Use Total Sum

Visual Process

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Implementation

✅ Approach 2: Prefix Sum (One Pass)

The Breakthrough Insight 💡

Implementation

🔍 Step-by-Step Execution

Example: nums = [1, 7, 3, 6, 5, 6]

Example 2: nums = [2, 1, -1]

Example 3: nums = [1, 2, 3] (No pivot)

🔍 Edge Cases

Common Mistakes

🎯 Key Takeaways

⚡ Algorithm Comparison

🔑 The Core Insight

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

Related Patterns