Find Pivot Index

Q: What is the time complexity of Find Pivot Index?

The total and running sum solution runs in O(n) time: one pass to add up the array and one pass to scan it. It uses O(1) extra space. Recomputing both sides at every index takes O(n²) time instead.

EasyPrefix sum

+10

You get an array of integers nums. A pivot index is an index where the sum of the values to its left equals the sum of the values to its right. The value at the pivot itself belongs to neither side, and a side with no values sums to 0.

Return the leftmost pivot index, or -1 if no index is a pivot.

Function

pivotIndex(nums: integer-array) → integer

numsinteger-array: the array of integers to balance
Returnsinteger: the leftmost pivot index, or -1 when there is none

Constraints

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Examples

Input: nums = [3, 1, 5, 2, 2]
Output: 2
Explanation: At index 2 the left side is 3 + 1 = 4 and the right side is 2 + 2 = 4. Index 0 and index 1 do not balance (left 0 against 10, left 3 against 9), so 2 is the leftmost pivot.

Input: nums = [1, 2, 3]
Output: -1
Explanation: The three candidates give 0 against 5, 1 against 3 and 3 against 0. No index balances, so the answer is -1.

+17 hidden tests on Submit

Follow-up

Can you find the leftmost pivot reading each value only once, without adding up the total first? What does that cost in memory?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Checking one index is a matter of two sums, but recomputing them at every index makes the work grow with the square of the length. The fix is to stop recomputing: the left sum grows by one value per step, and the right sum is whatever the total has left over. A pass for the total and a second pass with a running left sum find the leftmost pivot, with two numbers in memory.

Add up both sides at every index

Correct, but does not finish on the largest tests

Intuition

Follow the definition. For each index i, add up the values before it, add up the values after it, and compare. The first index where the two sums match is the answer, because you try the indices from left to right.

The edges take care of themselves. At index 0 the left loop runs zero times, so the left sum is 0; at the last index the right loop runs zero times. That is why [4, -4, 9] returns 2.

The cost is the problem. Every index adds up the other n-1 values, so the total work is about n² additions. At 10,000 values that is close to 100 million additions, and most of them repeat sums you already worked out one index earlier.

Algorithm

Loop i over every index of nums.
Add up nums[0] to nums[i-1] as the left sum.
Add up nums[i+1] to the last value as the right sum.
If the two sums are equal, return i.
If no index matches, return -1.

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left = 0
        for j in range(i):
            left += nums[j]
        right = 0
        for j in range(i + 1, n):
            right += nums[j]
        if left == right:
            return i
    return -1

Prefix sum array

Intuition

The brute force keeps adding up runs of the array. A prefix sum array does that work once. Let prefix[k] be the sum of the first k values, with prefix[0] = 0. For [3, 1, 5, 2, 2] that is [0, 3, 4, 9, 11, 13].

Now any run is a difference of two entries. The left side of index i is the first i values, so it is prefix[i]. The right side is everything after nums[i], which is prefix[n] - prefix[i+1]. At index 2 that gives 4 on the left and 13 - 9 = 4 on the right, a pivot.

Building the array takes one pass and each check takes constant time, so the whole search is O(n). The price is n+1 extra numbers in memory.

Algorithm

Create prefix of length n+1 with prefix[0] = 0.
Fill it: prefix[k+1] = prefix[k] + nums[k].
For each index i, read the left sum as prefix[i] and the right sum as prefix[n] - prefix[i+1].
Return the first i where they are equal, or -1 after the loop.

def pivotIndex(nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values.
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + nums[k]
    for i in range(n):
        left = prefix[i]
        right = prefix[n] - prefix[i + 1]
        if left == right:
            return i
    return -1

Total sum and a running left sum

Intuition

Look at which prefix entries the previous approach reads. At index i it needs prefix[i], prefix[i+1] and prefix[n]. The last one is the total, which never changes, and the other two are the running sum you would have if you walked the array once. So you can keep the total and one running left sum instead of the whole array.

Every value is on the left, at the pivot, or on the right. So the right sum is the total minus the left sum minus nums[i]. For [3, 1, 5, 2, 2] the total is 13. At index 0 the left sum is 0 and the right sum is 13 - 0 - 3 = 10. At index 1 it is 3 against 9. At index 2 it is 4 against 13 - 4 - 5 = 4, so you return 2.

The order inside the loop matters. Compare first, then add nums[i] to the left sum, so the left sum never includes the value at the index you are testing. Returning on the first match gives the leftmost pivot.

You read the array twice, once for the total and once for the scan, so the time is O(n). Only two numbers are stored, so the extra space is O(1).

Algorithm

Add up every value into total.
Set left to 0.
For each index i, if left equals total - left - nums[i], return i.
Otherwise add nums[i] to left and move on.
If the loop ends, return -1.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, value in enumerate(nums):
        # Everything that is not on the left and not nums[i] is on the right.
        if left == total - left - value:
            return i
        left += value
    return -1

Pitfalls and edge cases

Most wrong answers put the pivot's own value on one side or skip an edge index.

Adding nums[i] to the left sum before the comparison. The left side then includes the pivot value, and [3, 1, 5, 2, 2] no longer finds index 2.
Computing the right side as total - left. That counts nums[i] on the right; subtract it too.
Skipping index 0 or the last index. Both can be the pivot, because an empty side sums to 0. [1, -1, 1] returns 0 and [4, -4, 9] returns 2.
Returning the last match instead of the first. In [0, 0, 0] every index balances, and the answer is 0.
Using two pointers that move inward from both ends and grow the smaller side. That only works when every value is non-negative; here values go down to -1000, so a side can shrink as it grows.
Forgetting that Lua and R arrays start at 1. Return i-1 so the answer is a 0-based index.

Frequently asked questions4

What is the time complexity of Find Pivot Index?

The total and running sum solution runs in O(n) time: one pass to add up the array and one pass to scan it. It uses O(1) extra space. Recomputing both sides at every index takes O(n²) time instead.

Why is the right sum equal to total minus left minus nums[i]?

Every value of the array is in exactly one of three places: left of i, at i, or right of i. Their sums add up to the total, so the right sum is the total with the other two parts taken away. That lets you check an index without ever adding up the right side.

Can Find Pivot Index be solved with two pointers?

Not reliably. A two pointer scan that always grows the smaller side assumes that adding a value makes a side bigger, which fails as soon as values can be negative: a side can shrink while you grow it, so the scan can move a pointer past the real pivot. The running sum method makes no assumption about the signs and checks every index.

What is the pivot index of an array with one element?

It is 0. Both sides of the only element are empty, and an empty side sums to 0, so the two sides are equal. The running sum solution returns 0 on its first comparison: left is 0 and the total minus 0 minus the value is also 0.

Python

def pivotIndex(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [3, 1, 5, 2, 2]

Expected

Find Pivot Index

Function

Constraints

Examples

Hints

Solution

Add up both sides at every index

Prefix sum array

Total sum and a running left sum

Pitfalls and edge cases

Frequently asked questions4

Similar problems