Find Pivot Index
Ramayana — The Fulcrum of Lanka — Finding the Balance Point of Ravana's Island Kingdom
यत्र वामं दक्षिणं समं — तत्र केन्द्रं विद्यते। तस्य पूर्वं समस्तं चापरं — सन्तुलनं परम्॥
*Where left equals right — there lies the center. Everything before it and everything after — perfect balance.*
The Story
When Hanuman surveyed Lanka for Rama, he needed to identify the island's balance point — the position where the combined weight of all districts to the LEFT exactly equaled the combined weight of all districts to the RIGHT. This was the strategic center: from this pivot point, both flanks could be defended with equal force.
Lanka's district strengths were recorded as `[1, 7, 3, 6, 5, 6]`.
"Find the index where the sum of all elements to its left equals the sum of all elements to its right," Vibhishana explained to Hanuman.
Hanuman's first thought: "For each index i, compute leftSum = sum(0..i-1) and rightSum = sum(i+1..n-1). Check if they're equal."
"That's O(n²) — recomputing the sums for each candidate pivot," Vibhishana said.
"The elegant solution," Hanuman realized, "requires only the total sum."
**Key insight:** If `leftSum = rightSum` at index i, then: `leftSum + nums[i] + rightSum = total` `2 × leftSum + nums[i] = total` `leftSum = (total - nums[i]) / 2`
Or equivalently: `leftSum == total - leftSum - nums[i]` → `leftSum == rightSum`.
Algorithm: 1. Compute `total` = sum of all elements. O(n) 2. Scan left to right, maintaining `leftSum`. 3. At each index i: `rightSum = total - leftSum - nums[i]`. If `leftSum == rightSum`, return i. 4. Update `leftSum += nums[i]`.
Hanuman traced through `[1, 7, 3, 6, 5, 6]`:
total = 1+7+3+6+5+6 = 28
- i=0: leftSum=0. right=28-0-1=27. 0≠27 - i=1: leftSum=1. right=28-1-7=20. 1≠20 - i=2: leftSum=8. right=28-8-3=17. 8≠17 - i=3: leftSum=11. right=28-11-6=11. **11==11!** Return 3.
"Index 3, value 6," Hanuman confirmed. "Districts 0-2 have total strength 1+7+3=11. Districts 4-5 have total strength 5+6=11. Perfect balance!"
Vibhishana nodded. "From district 3, Hanuman could split his forces equally in both directions. The fulcrum of Lanka."
"What if no pivot exists?" Hanuman asked.
"Return -1. The total can never be split equally around any position."
"What if multiple pivots exist? Like `[2, 1, -1]` with pivots at index 0 (leftSum=0, rightSum=0)?"
"Return the LEFTMOST one — the first we encounter in our left-to-right scan."
Hanuman marked district 3 on his map. Rama's forces would be positioned there for maximum strategic balance. The battle plan that would topple Ravana was built around this single pivot point.
"Total sum, one pass," Hanuman summarized. "The prefix sum does not need to be stored — just updated incrementally. The right sum is derived from left sum and total in O(1)."
This is the Prefix Sum technique for finding the pivot index.
Vibhishana's First Instinct
For each index, compute left sum (all elements before it) and right sum (all elements after it). Check equality. O(n²) time.
public int pivotIndexBruteForce(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
// Compute left sum
int leftSum = 0;
for (int j = 0; j < i; j++) leftSum += nums[j];
// Compute right sum
int rightSum = 0;
for (int j = i + 1; j < n; j++) rightSum += nums[j];
if (leftSum == rightSum) return i;
}
return -1;
}Hanuman's Pivot Wisdom
public int pivotIndex(int[] nums) {
// Step 1: Compute total sum
int total = 0;
for (int n : nums) total += n;
// Step 2: Scan left to right, check pivot condition
int leftSum = 0;
for (int i = 0; i < nums.length; i++) {
// rightSum = total - leftSum - nums[i]
if (leftSum == total - leftSum - nums[i]) {
return i; // Pivot found!
}
leftSum += nums[i]; // Update for next position
}
return -1; // No pivot found
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().pivotIndex(new int[]{1,7,3,6,5,6})); // 3
System.out.println(new Solution().pivotIndex(new int[]{1,2,3})); // -1
System.out.println(new Solution().pivotIndex(new int[]{2,1,-1})); // 0 (leftSum=0, rightSum=0)
}Step-by-Step Walkthrough
nums = [2, 1, -1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
total = 2+1+(-1) = 2
i=0: leftSum=0
rightSum = 2-0-2 = 0
leftSum(0) == rightSum(0) ✅ → return 0!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return 0
Verify: left of index 0 = [] = sum 0
right of index 0 = [1,-1] = sum 0 ✓Deep Insight
**Why is `leftSum == total - leftSum - nums[i]` equivalent to `leftSum == rightSum`?**
`rightSum = total - leftSum - nums[i]` (total sum = left part + current element + right part)
So `leftSum == rightSum` becomes `leftSum == total - leftSum - nums[i]`. Rearranging: `2×leftSum = total - nums[i]`.
**O(1) space:** We don't store the right sum separately — it's computed on-the-fly from total and leftSum. No extra array needed.
**Edge cases:** - First element as pivot: leftSum=0 at start. Check if `0 == total - 0 - nums[0]` = `total == nums[0]` (all other elements sum to 0) - Last element as pivot: leftSum = total - nums[n-1]. Check if `total - nums[n-1] == 0` - All zeros: every index is a pivot; return 0 (leftmost) - Single element: return 0 (leftSum=0, rightSum=0)
**Multiple pivots:** The scan returns the FIRST (leftmost) pivot encountered.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Two inner loops per index |
| Optimal | O(n) | O(1) | One pass for total + one pass for pivot check |
Pattern Recognition
✅ Find index where left sum equals right sum ✅ Use total sum to derive right sum in O(1) ✅ Running prefix sum with one pass ✅ No extra array — O(1) space **LeetCode Trigger Phrases:** → "pivot index" where left sum equals right sum → "left sum equals right sum" → "find equilibrium index"
Bhagavad Gita 12.18
समः शत्रौ च मित्रे च तथा मानापमानयोः। शीतोष्णसुखदुःखेषु समः सङ्गविवर्जितः॥
One who is equal to enemies and friends alike, equal in honor and disgrace, equal in heat and cold, in pleasure and pain, free from all attachment.
Connection: The pivot index is the point of perfect equanimity — where everything to the left and everything to the right are exactly equal in weight. Like the yogi described in the Gita who maintains balance between praise and blame, heat and cold, the pivot is the index that balances all opposing forces. The algorithm finds this equilibrium point efficiently by using the total sum as a reference, computing balance without disturbing any element.