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 to scan it, with O(1) extra space. Recomputing both sides at every index takes O(n²) .

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 sum 3 + 1 = 4 balances the right sum 2 + 2 = 4. Index 0 gives 0 against 10 and index 1 gives 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.

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

Recomputing both sums at every index costs O(n²). The left sum grows by one value per step, and the right sum is whatever the total has left over. So one pass for the total and one 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

For each index, add up the values before it and the values after it, and compare. Trying the indices from left to right makes the first match the leftmost pivot. At either edge one loop runs zero times and its sum stays 0, which is why [4, -4, 9] returns 2.

Every index adds up the other n-1 values. At 10,000 values that is close to 100 million additions, most of them repeating sums from the index before.

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

A prefix sum array does the adding 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]. The left side of index i is prefix[i], and the right side is prefix[n] - prefix[i+1]. At index 2 that gives 4 against 13 - 9 = 4, a pivot.

One pass builds the array and each check takes constant time: O(n) time, with 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

At index i the prefix approach reads prefix[i], prefix[i+1] and prefix[n]. The last is the total, which never changes, and the other two are a running sum you can build as you walk. So keep the total and one left sum instead of the array.

Every value is left of i, at i, or right of i, so the right sum is total - left - nums[i]. Compare before you add nums[i] to left, so the left sum never includes the value you are testing. In the first example the total is 13, and index 2 gives 4 against 13 - 4 - 5 = 4.

Two passes take O(n) time, and two numbers take O(1) space.

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

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. An empty side sums to 0, so [1, -1, 1] returns 0 and [4, -4, 9] returns 2.
Returning the last match. In [0, 0, 0] every index balances, and the answer is 0.
Forgetting that Lua and R arrays start at 1. Return i-1 so the answer is a 0-based index.

Frequently asked questions3

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 to scan it, with O(1) extra space. Recomputing both sides at every index takes O(n²).

Can Find Pivot Index be solved with two pointers?

Not reliably. A scan from both ends that always grows the smaller side assumes that adding a value makes a side bigger. Values here go down to -1000, so a side can shrink as it grows, and the pointers can move past the real pivot.

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 sides are equal. The running sum solution returns 0 on its first comparison.

def pivotIndex(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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 questions3

Similar problems