Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Find Pivot Index

Try it yourself
EasyProblemExternal link

Description

You get an integer array nums.

The pivot index is an index where the sum of all the values strictly to its left equals the sum of all the values strictly to its right. The value at the pivot itself belongs to neither side. If an index is at the left edge, its left side is empty and adds up to 0; the same goes for the right edge.

Return the leftmost pivot index. If there is none, return -1.

Examples

Example 1

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

Output: 3

Explanation: Left of index 3 is 1 + 7 + 3 = 11, and right of it is 5 + 6 = 11. No index before it balances.

Example 2

Input: nums = [1, 2, 3]

Output: -1

Explanation: No index has equal sides: index 0 has 0 and 5, index 1 has 1 and 3, index 2 has 3 and 0.

Example 3

Input: nums = [2, 1, -1]

Output: 0

Explanation: Nothing is left of index 0, so its left side is 0, and its right side is 1 + (-1) = 0.

Constraints

  • 1 ≤ nums.length ≤ 10^4
  • -1000 ≤ nums[i] ≤ 1000

Editorial

Brute Force

Intuition

Check the definition directly: at each index, add up everything to its left and everything to its right, and stop at the first index where the two sums match.

Step-by-Step Explanation

Let's look for the pivot of [1, 7, 3, 6, 5, 6]:

  1. Index 0: the left side adds up to 0 and the right side to 27, so it doesn't balance. That's 5 additions so far.
  2. Index 1: the left side adds up to 1 and the right side to 20, so it doesn't balance. That's 10 additions so far.
  3. Index 2: the left side adds up to 8 and the right side to 17, so it doesn't balance. That's 15 additions so far.
  4. Index 3: the left side adds up to 11 and the right side to 11, so it balances. That's 20 additions so far.
  5. Index 3 is the leftmost pivot. Every index re-added nearly the whole array.

Add Both Sides at Every Index — The shaded cells are the left side of the index being checked; everything after it is the right side.

Algorithm

  1. For each index i from left to right:
    • add up nums[0..i-1] and nums[i+1..n-1];
    • if the two sums are equal, return i.
  2. Return -1.

Code

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int left = 0, right = 0;
            for (int j = 0; j < i; j++) left += nums[j];         // add up the left side
            for (int j = i + 1; j < n; j++) right += nums[j];    // and the right side, from scratch
            if (left == right) return i;
        }
        return -1;
    }
};

class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        n = len(nums)
        for i in range(n):
            left = 0
            for j in range(i):                  # add up the left side
                left += nums[j]
            right = 0
            for j in range(i + 1, n):           # and the right side, from scratch
                right += nums[j]
            if left == right:
                return i
        return -1

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int left = 0, right = 0;
            for (int j = 0; j < i; j++) left += nums[j];         // add up the left side
            for (int j = i + 1; j < n; j++) right += nums[j];    // and the right side, from scratch
            if (left == right) return i;
        }
        return -1;
    }
}

var pivotIndex = function(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        let left = 0, right = 0;
        for (let j = 0; j < i; j++) left += nums[j];             // add up the left side
        for (let j = i + 1; j < n; j++) right += nums[j];        // and the right side, from scratch
        if (left === right) return i;
    }
    return -1;
};

Complexity Analysis

Time Complexity: O(n²)

Each of the n indexes adds up the other n − 1 values.

Space Complexity: O(1)

Why This Approach Is Not Efficient

With 10^4 values and no pivot, that's about 10^8 additions (over the time limit in Python).

Moving from index i to index i + 1 changes each side by just one value: nums[i] joins the left side and nums[i + 1] leaves the right side. So the sums can be updated instead of recomputed.

Optimal Approach - Running Left Sum

Intuition

Add the whole array once to get total. Then walk left to right keeping left, the sum of everything before i. The right side is whatever is left: right = total − left − nums[i] (the pivot belongs to neither side, so nums[i] comes off too). Compare, then add nums[i] to left and move on.

This is the running-total idea from prefix sums: left is the running total that would sit on the gap before index i, and the total gives the rest for free.

Step-by-Step Explanation

Let's look for the pivot of [1, 7, 3, 6, 5, 6] again:

  1. Adding everything once gives a total of 28. The left side starts at 0.
  2. Index 0: the left side is 0, and the right side is 28 − 0 − 1 = 27. They differ, so add 1 to the left side and move on.
  3. Index 1: the left side is 1, and the right side is 28 − 1 − 7 = 20. They differ, so add 7 to the left side and move on.
  4. Index 2: the left side is 8, and the right side is 28 − 8 − 3 = 17. They differ, so add 3 to the left side and move on.
  5. Index 3: the left side is 11, and the right side is 28 − 11 − 6 = 11, so it balances.
  6. Index 3 is the leftmost pivot, after one pass for the total and one for the scan.

One Total, One Running Left Sum — The shaded cells are the left side so far; the right side is the total minus the left side minus the current value.

Algorithm

  1. total = the sum of nums; left = 0.
  2. For each index i: if left == total − left − nums[i], return i; otherwise add nums[i] to left.
  3. Return -1.

Code

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;
        int left = 0;                           // the sum of everything left of i
        for (int i = 0; i < (int)nums.size(); i++) {
            if (left == total - left - nums[i]) // the right side: the total minus the left side minus nums[i]
                return i;
            left += nums[i];
        }
        return -1;
    }
};

class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        total = sum(nums)
        left = 0                                # the sum of everything left of i
        for i, x in enumerate(nums):
            if left == total - left - x:        # the right side: the total minus the left side minus x
                return i
            left += x
        return -1

class Solution {
    public int pivotIndex(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        int left = 0;                           // the sum of everything left of i
        for (int i = 0; i < nums.length; i++) {
            if (left == total - left - nums[i]) // the right side: the total minus the left side minus nums[i]
                return i;
            left += nums[i];
        }
        return -1;
    }
}

var pivotIndex = function(nums) {
    const total = nums.reduce((a, b) => a + b, 0);
    let left = 0;                               // the sum of everything left of i
    for (let i = 0; i < nums.length; i++) {
        if (left === total - left - nums[i])    // the right side: the total minus the left side minus nums[i]
            return i;
        left += nums[i];
    }
    return -1;
};

Complexity Analysis

Time Complexity: O(n)

One pass for the total, one for the scan.

Space Complexity: O(1)

Two numbers, whatever the length.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Leaving nums[i] on the right side. if left == total - left:

On nums = [2, 3, 2], it returns -1; the answer is 1. The pivot belongs to neither side. total - left still includes nums[i], so the right side is too big by nums[i]: on [2, 3, 2] the real pivot, index 1, is never found. The right side is total - left - nums[i].

Returning the last pivot instead of the first. found = i # keeps going after a match

On nums = [5, 0, 0, 5], it returns 2; the answer is 1. When several indexes balance, the problem wants the leftmost. Remembering every match and returning the last one gives the rightmost: on [5, 0, 0, 5] it returns 2 instead of 1.

Skipping index 0. for i in range(1, len(nums)):

On nums = [2, 1, -1], it returns -1; the answer is 0. Index 0 can be a pivot: its left side is empty, so its sum is 0, and the rest may add up to 0 too (on [2, 1, -1] it does). Start the scan at 0.

Where This Pattern Is Taught

This problem practises sums to the left and right of every index from one running total. It's taught in Introduction to Prefix Sums.