find-pivot-index

Difficulty: Easy  ·  Topic: Arrays & Hashing  ·  Practice it on parikshan: /practice/find-pivot-index/start

The story

A logistics engineer at FedEx is balancing route stops. A delivery truck visits n stops; each stop has a positive or negative net package count (deliveries minus pickups). The dispatcher wants the first stop that splits the route into two halves with equal net package movement on either side. That stop is the natural place to put the driver's lunch break, because the truck weight is balanced before and after. The dispatcher runs the same calculation for hundreds of trucks per minute; the algorithm must be linear, with O(1) extra memory.

That is find-pivot-index. It is the cleanest demonstration of a single invariant: total minus running prefix equals the rest. Once you internalise that identity, half the array-splitting problems in the world become a single sweep.

What's actually being asked

Given an integer array nums, return the leftmost index i such that the sum of nums[0..i-1] equals the sum of nums[i+1..n-1]. The pivot element nums[i] itself is not counted on either side. If no such index exists, return -1. The empty sum is 0, so an answer at index 0 requires nums[1..n-1] to sum to 0.

The naive approach

For each candidate index i, compute the left sum and the right sum from scratch. O(n^2). At n = 10^5, that is 10^10 operations and times out comfortably.

Slightly better: precompute prefix sums into an auxiliary array. Then left(i) = prefix[i] and right(i) = total - prefix[i + 1]. O(n) time, O(n) space. Correct, but uses memory you don't need.

The key insight

You do not need to store every prefix sum. You only need the current running left and the total. The right sum is determined: right(i) = total - left - nums[i]. So at each index, you can check the pivot condition in O(1):

left == total - left - nums[i]

If yes, i is a pivot. If no, fold nums[i] into left and continue.

Compute total = sum(nums) once, walk left to right, return the first hit. O(n) time, O(1) extra space. The first hit is automatically the leftmost.

Step-by-step approach

1. Compute total = sum(nums).
2. Initialise left = 0.
3. For i from 0 to n - 1:
   • If left == total - left - nums[i], return i.
   • Otherwise, left += nums[i].
4. Return -1.

def pivot_index(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        if left == total - left - x:
            return i
        left += x
    return -1

That is the whole production algorithm.

Worked example

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

total = 28. Walk:

Verify: left of index 3 = 1 + 7 + 3 = 11. Right of index 3 = 5 + 6 = 11. Match.

Try nums = [2, 1, -1]. total = 2. At i = 0: left = 0, right = 2 - 0 - 2 = 0. Match. Return 0. (Left of index 0 is empty, sum 0; right is 1 + (-1) = 0.) The empty-prefix case works without special handling.

Complexity

• Time: O(n), one pass plus the initial sum.
• Space: O(1) extra.

Brute force was O(n^2). Prefix-array variant was O(n) time, O(n) space. The running-prefix variant is the asymptotically best you can do, with the smallest constant memory footprint.

Common pitfalls

• Computing total once is not optional: recomputing inside the loop is the O(n^2) trap that defeats the optimisation.
• Including nums[i] in left: the spec excludes the pivot from both sides. The identity is right = total - left - nums[i], with all three pieces disjoint.
• Updating left before the comparison: includes the current value in the prefix and shifts the entire check by one. Always compare first, then update.
• Returning the first match versus the last: the spec says leftmost. The straightforward left-to-right walk with an early return is correct; reversing direction silently returns the wrong index when multiple pivots exist.
• Floating-point sums: not relevant here (integer inputs), but in general, sum over floats accumulates error and can make the equality check fail for "obvious" pivots. Use exact arithmetic.
• Empty-side handling: the empty sum is 0 by convention. The algorithm handles index 0 and index n - 1 naturally because the formula uses total, not a separate "left-of-end" computation.

Where this shows up in the enterprise

• FedEx / UPS route balancing: the story above; truck weight balance for driver lunch breaks.
• Stripe transaction-day balance audits: identify the timestamp that splits a settlement window into two equal-credit halves; same shape applied to running monetary totals.
• AWS S3 lifecycle policy splitting: when migrating buckets between storage classes, find the prefix at which the migrated and unmigrated data weigh equally. Used to schedule the move with minimum disruption.
• GitHub Actions runner load balancing: among a fleet of N runners with varying queue depths, find the runner index that balances total queue depth on either side; helps with bisection-style autoscaling.
• Cloudflare Workers cold-start optimisation: across a sorted list of route handlers by cumulative bundle size, find the pivot at which the bundle is balanced; informs which routes to deploy as separate Worker scripts.
• Snowflake query partitioning: partition a sorted result set into equal-cost halves; pivot index of the cost array.
• Spotify playlist energy balancing: tools that split a playlist at the song that keeps total energy before and after equal; same algorithm over energy scores.
• NYSE / Nasdaq end-of-day auction matching: balance buy-side and sell-side cumulative volume at a single clearing price; conceptually a pivot scan over the order book.

The pattern "find the split point where a prefix aggregate equals a suffix aggregate" is universal.

Variants you'll see elsewhere

• running-sum-of-1d-array: the prefix-sum building block.
• product-of-array-except-self: the multiplicative cousin.
• subarray-sum-equals-k: generalises prefix-sum bookkeeping with a hash map.
• partition-array-into-two-arrays-with-minimum-difference: NP-style "split as evenly as possible"; not a pivot index but the same intuition.
• split-array-largest-sum: binary search on the answer; uses prefix sums as the inner check.
• find-the-middle-index: an alias problem; literally the same question.
• count-of-range-sum: range-sum queries with a sorted data structure.

How parikshan turns this into a learning loop

Read this article, then click into practice. The editor runs your code against public tests plus per-session dynamic private tests generated fresh each attempt, so memorising a gist fails. Hints are graduated: free first hint, small penalty for the second, larger for the third. The AI training assistant in exam mode offers Explain, Review, Find Bugs, Add Comments, Optimise, each with a small integrity cost so you spend AI deliberately. In practice mode AI chat is free, the right place to walk through the prefix-sum identity. After the verdict, the dispute flow sends contested results to a human reviewer in one click. Attempt in practice mode first, then redo in exam mode untouched. When you can write the seven-line solution in two minutes from a blank screen, the pattern is in your fingers.

In the AI-integrated workspace

An AI agent will write the O(n) solution most of the time. The failure modes that survive review:

1. Building a full prefix-sum array when a running scalar suffices. O(n) memory the system did not need to spend.
2. Off-by-one in the comparison: left == total - left - nums[i] is the right identity. left == total - left (without subtracting the pivot) is a common bug; the generated code looks right because it passes on inputs where nums[i] = 0.
3. Forgetting the leftmost requirement: returning any pivot rather than the smallest. A left-to-right scan returns the leftmost naturally; agents that sort or split-merge can produce a non-leftmost answer.
4. Negative values: the identity holds for any sign, but agents sometimes write abs(left) "to be safe" and silently get a wrong answer.

A senior engineer reads "find the index that splits the array into two equal-sum sides" and immediately maps it to the running-prefix identity. The candidate who can do that directs AI agents productively. The candidate who cannot ships the O(n) memory variant in a hot path and notices the inefficiency only after the cost dashboards complain. parikshan trains the first kind.