Find Pivot Index (Balance Point of an Array)

• The pivot index is the leftmost index where the left sum equals the right sum.
• The element at the pivot belongs to neither side.
• Compute the total sum in one pass, then scan with a running leftSum.
• At each index: rightSum = total - leftSum - nums[i].
• Return immediately on the first match for the leftmost pivot.
• Time is O(N) and space is O(1): no map needed.

What is the Find Pivot Index problem?

Given an array of integers, find the leftmost index where the sum of all elements strictly to its left equals the sum of all elements strictly to its right. The element at the pivot index itself belongs to neither side. Return -1 if no such index exists. This is LeetCode 724.

For example, given [1, 7, 3, 6, 5, 6], the pivot index is 3 because 1 + 7 + 3 = 11 and 5 + 6 = 11.

How does the single-pass prefix approach work?

First compute the total sum. Then scan left to right maintaining a running left sum. At each index, the right sum is total - leftSum - nums[i]. If leftSum == rightSum, return the current index. Otherwise, add nums[i] to leftSum and continue.

package com.bank.service;

public class PivotIndexService {

    /**
     * Finds the balance-point transaction in a settlement batch.
     * Used by the National Bank of India operations team.
     */
    public static int pivotIndex(long[] settlements) {
        long total = 0;
        for (long s : settlements) total += s;

        long leftSum = 0;
        for (int i = 0; i < settlements.length; i++) {
            long rightSum = total - leftSum - settlements[i];
            if (leftSum == rightSum) {
                return i;
            }
            leftSum += settlements[i];
        }
        return -1;
    }

    public static void main(String[] args) {
        long[] settlements = {10000, 70000, 30000, 60000, 50000, 60000};
        int pivot = pivotIndex(settlements);
        System.out.println("Pivot index: " + pivot);
        if (pivot != -1) {
            System.out.println("Balance-point amount: Rs." + settlements[pivot]);
        }
    }
}

javac -d out com/bank/service/PivotIndexService.java
java -cp out com.bank.service.PivotIndexService

Pivot index: 3
Balance-point amount: Rs.60000

Why does the pivot element belong to neither side?

The problem defines the left sum as everything strictly before the pivot and the right sum as everything strictly after it. The pivot element is excluded from both computations, which is why the right sum formula subtracts nums[i] from the remaining total.

What are the edge cases?

Several edge cases require attention.

• First index as pivot: the left side is empty (sum = 0), so the first index is a pivot if everything after it sums to zero.
• Last index as pivot: everything before it must sum to zero.
• All zeros: every index is a valid pivot; return index 0 (leftmost).
• Negative numbers: fully supported because we compare sums, not relying on monotonicity.
• No pivot exists: return -1.

package com.bank.core;

public class PivotEdgeCases {
    public static void main(String[] args) {
        // First index as pivot
        System.out.println(pivotIndex(new long[]{0, 1, -1})); // 0

        // Last index as pivot
        System.out.println(pivotIndex(new long[]{-1, 1, 0})); // 2

        // No pivot
        System.out.println(pivotIndex(new long[]{1, 2, 3}));  // -1
    }

    static int pivotIndex(long[] arr) {
        long total = 0; for (long a : arr) total += a;
        long left = 0;
        for (int i = 0; i < arr.length; i++) {
            if (left == total - left - arr[i]) return i;
            left += arr[i];
        }
        return -1;
    }
}

0
2
-1

What is the time and space complexity?

Time is O(N): one pass for the total, one pass for the scan. Space is O(1): two running totals. This is the simplest form of prefix sums, needing no hash map.

How is this different from Subarray Sum Equals K?

Pivot index needs only a single running prefix and the total. Subarray sum equals K needs a hash map because it counts pairs of prefix sums. The distinction is important.

| Problem | Needs map? | Why |
|---|---|---|
| Pivot index | No | Single comparison at each index |
| Subarray sum = K | Yes | Count all prefix pairs differing by k |
| Subarray sum divisible by K | Yes | Count all prefix pairs with same remainder |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• No map variant: this is prefix sums in their simplest form. Knowing when a map is and is not required shows you understand the technique rather than applying it blindly.
• Overflow: use long for the total and running sum on large monetary batches.
• Return on first match: returning immediately on the first match gives the leftmost pivot without extra bookkeeping.
• Generalization: finding all pivot indices requires continuing the scan and collecting all matches.

What are common interview follow-up questions?

Interviewers often extend this problem.

• Find all pivot indices: continue scanning after the first match.
• Pivot in a circular array: wrap around using modular arithmetic.
• Weighted pivot: each element has a weight, and the weighted sums must balance.