What is the brute force approach and complexity for Find Pivot Index?

For each index, loop to sum the left side and loop again to sum the right side with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Find Pivot Index?

Compute the total once; right side = total − left − nums[i] with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Find Pivot Index?

Look for key signals in the prompt: "sum of all numbers strictly to the left" indicates A prefix sum: a running total from the left end, stopping just before i.; "sum of all numbers strictly to the right" indicates A suffix sum: a running total from the right end — or simply the total minus everything else.; "each index" indicates Every index needs information from both sides → a left pass and a right pass, then combine per index.; "leftmost" indicates Scan from the left and return on the first match..

Find Pivot Index

Easy·LeetCode #724Basic Anchor

LeetCode

Jump:

30-Second Mental ModelPrefix Sum (prefix + suffix)

Complexity:O(N²)→O(N)

Key Insight

Add up the whole array once to get total. Walk from the left keeping left, the sum of everything before i. The right side is whatever is not on the left and is not nums[i], so right = total − left − nums[i]. Return the first i where left == right.

Core Validity Invariant

Index i is a pivot when left == total − left − nums[i], where left covers only the numbers before i and neither side includes nums[i].

Problem

You are given an integer array nums.

An index i is a pivot if the sum of all numbers strictly to its left equals the sum of all numbers strictly to its right. nums[i] itself belongs to neither side. If there is nothing on one side, that side's sum is 0.

Return the leftmost pivot index. If no index is a pivot, return -1.

Input

An integer array nums of length n.

Output

One integer: the smallest pivot index, or -1 if there is none.

Example 1

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

Output: 3

Left of index 3: 1 + 7 + 3 = 11. Right of index 3: 5 + 6 = 11. No earlier index works.

Example 2

Input: nums = [1, 2, 3]

Output: -1

No index has equal sums on both sides.

Example 3

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

Output: 0

Index 0 has nothing on its left (sum 0). Its right side is 1 + (−1) = 0.

Constraints

• 1 ≤ n ≤ 10^4
• −1000 ≤ nums[i] ≤ 1000

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
For one fixed index i, which numbers are on the left and which are on the right? Where does nums[i] go?
2.
If I know the left sum for index i, how do I get the left sum for index i + 1?
3.
Left part + nums[i] + right part — what does that add up to, for every i?
4.
Can negative numbers break any idea that relies on sums only growing?
5.
If several indices are pivots, which one do I return, and in what order should I check them?

Brute force approach

Idea

Try each index i from left to right. Add up nums[0 … i−1] and nums[i+1 … n−1] with two small loops. The first index where they match is the answer.

Thinking process

1
The definition is about one index at a time, so just check each index.
2
For index i, the left side is everything before it and the right side is everything after it. nums[i] is in neither.
3
Add up both sides with plain loops and compare.
4
Go from left to right and return on the first match, so the answer is the leftmost pivot.

Code & Implementation

brute.cpp

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();

        // Try every index as the pivot, from left to right.
        for (int i = 0; i < n; i++) {
            int left = 0, right = 0;
            for (int j = 0; j < i; j++) left += nums[j];       // strictly left of i
            for (int j = i + 1; j < n; j++) right += nums[j];  // strictly right of i
            if (left == right) return i;   // first match is the leftmost pivot
        }
        return -1;
    }
};

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;

        // Try every index as the pivot, from left to right.
        for (int i = 0; i < n; i++) {
            int left = 0, right = 0;
            for (int j = 0; j < i; j++) left += nums[j]; // strictly left of i
            for (int j = i + 1; j < n; j++) right += nums[j]; // strictly right of i
            if (left == right) return i; // first match is the leftmost pivot
        }
        return -1;
    }
}

class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        n = len(nums)

        # Try every index as the pivot, from left to right.
        for i in range(n):
            left = sum(nums[:i])
            right = sum(nums[i + 1 :])
            if left == right:
                return i
        return -1

export function pivotIndex(nums: number[]): number {
    const n = nums.length;

    // Try every index as the pivot, from left to right.
    for (let i = 0; i < n; i++) {
        let left = 0, right = 0;
        for (let j = 0; j < i; j++) left += nums[j];
        for (let j = i + 1; j < n; j++) right += nums[j];
        if (left === right) return i;
    }
    return -1;
}

Complexity

Time O(N²)Space O(1)

Every index adds up about n numbers. With n = 10^4 that is around 10^8 additions — it passes here only because n is small, and it would not scale.

Better approach

Why brute force is slow

For every index, brute force adds up both sides again from scratch.

What repeated work are we doing?

The left side of index i + 1 is the left side of index i with one extra number. Brute force re-adds all the old numbers anyway. Same on the right side.

What information can we reuse?

Running sums. leftSum[i] = leftSum[i−1] + nums[i−1] (left to right) and rightSum[i] = rightSum[i+1] + nums[i+1] (right to left). Each array takes one pass.

New approach

Idea

Build leftSum[i] = sum of everything before i with a pass from the left, and rightSum[i] = sum of everything after i with a pass from the right. Then index i is a pivot when leftSum[i] == rightSum[i].

Thinking process

1
Brute force rebuilds the left sum of i + 1 from zero, but it is just the left sum of i plus nums[i].
2
So one running total from the left gives every left sum in one pass.
3
The right side works the same way, walking from the right end.
4
Store both in arrays, then scan once from the left and return the first index where they match.

Visual

leftSum[i] = sum before i, rightSum[i] = sum after i. Neither includes nums[i]. Compare them index by index.

Left pass + right passnums = [1, 7, 3, 6, 5, 6]step 1/16

nums

▲i

leftSum

rightSum

Left pass

leftSum[0]: 0 (nothing before index 0)

Left pass: index 0

Nothing is before index 0, so leftSum[0] = 0.

Code & Implementation

better.cpp

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();

        // leftSum[i] = sum of nums[0 .. i-1]   (everything before i)
        vector<int> leftSum(n, 0);
        for (int i = 1; i < n; i++) leftSum[i] = leftSum[i - 1] + nums[i - 1];

        // rightSum[i] = sum of nums[i+1 .. n-1] (everything after i)
        vector<int> rightSum(n, 0);
        for (int i = n - 2; i >= 0; i--) rightSum[i] = rightSum[i + 1] + nums[i + 1];

        for (int i = 0; i < n; i++) {
            if (leftSum[i] == rightSum[i]) return i;
        }
        return -1;
    }
};

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;

        // leftSum[i] = sum of nums[0 .. i-1] (everything before i)
        int[] leftSum = new int[n];
        for (int i = 1; i < n; i++) leftSum[i] = leftSum[i - 1] + nums[i - 1];

        // rightSum[i] = sum of nums[i+1 .. n-1] (everything after i)
        int[] rightSum = new int[n];
        for (int i = n - 2; i >= 0; i--) rightSum[i] = rightSum[i + 1] + nums[i + 1];

        for (int i = 0; i < n; i++) {
            if (leftSum[i] == rightSum[i]) return i;
        }
        return -1;
    }
}

class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        n = len(nums)

        # leftSum[i] = sum of nums[0 .. i-1] (everything before i)
        left_sum = [0] * n
        for i in range(1, n):
            left_sum[i] = left_sum[i - 1] + nums[i - 1]

        # rightSum[i] = sum of nums[i+1 .. n-1] (everything after i)
        right_sum = [0] * n
        for i in range(n - 2, -1, -1):
            right_sum[i] = right_sum[i + 1] + nums[i + 1]

        for i in range(n):
            if left_sum[i] == right_sum[i]:
                return i
        return -1

export function pivotIndex(nums: number[]): number {
    const n = nums.length;

    // leftSum[i] = sum of nums[0 .. i-1] (everything before i)
    const leftSum = new Array(n).fill(0);
    for (let i = 1; i < n; i++) leftSum[i] = leftSum[i - 1] + nums[i - 1];

    // rightSum[i] = sum of nums[i+1 .. n-1] (everything after i)
    const rightSum = new Array(n).fill(0);
    for (let i = n - 2; i >= 0; i--) rightSum[i] = rightSum[i + 1] + nums[i + 1];

    for (let i = 0; i < n; i++) {
        if (leftSum[i] === rightSum[i]) return i;
    }
    return -1;
}

Complexity

Time O(N)Space O(N)

Three passes, but two extra arrays of size n. The right array can be dropped completely, because the right side is just what's left over from the total.

Optimized approach

Idea

Start from brute force

Brute force adds up the left side and the right side of every index from scratch. The better approach stores all left sums and all right sums in two arrays.

Find the repeated work

Brute force re-adds the same numbers for neighbouring indices. And even the better approach does extra work: the right array holds nothing new, because left + nums[i] + right is always the same number — the total.

Define the state — what variables do I need?

total: Sum of the whole array, computed once before the main loop.
left: Sum of nums[0 … i−1], the numbers strictly before the current index.
right: total − left − nums[i]: the numbers strictly after the current index.

Define validity

Index i is a pivot when left == total − left − nums[i], where left covers only the numbers before i and neither side includes nums[i].

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

total = sum of all nums; left = 0

For index 0 nothing is on the left, so its left sum is 0. The total lets us get any right side with one subtraction.

At each index i

right = total − left − nums[i]; if left == right return i

Every number is either before i, at i, or after i. Take away the first two from the total and you have exactly the right side.

After checking index i

left += nums[i]

For index i + 1, nums[i] is now on the left. Add it only after the check, so it is never counted on the left of itself.

What does the current window add to the answer?

Each index is checked once, in order from left to right. The first index that passes is returned, which is exactly the leftmost pivot.

Code & Implementation

optimal.cpp

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;

        int left = 0;   // sum of everything before i
        for (int i = 0; i < (int)nums.size(); i++) {
            // Whatever is not on the left and is not nums[i] itself is on the right.
            int right = total - left - nums[i];
            if (left == right) return i;
            left += nums[i];   // nums[i] joins the left side for the next index
        }
        return -1;
    }
};

class Solution {
    public int pivotIndex(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;

        int left = 0; // sum of everything before i
        for (int i = 0; i < nums.length; i++) {
            // Whatever is not on the left and is not nums[i] itself is on the right.
            int right = total - left - nums[i];
            if (left == right) return i;
            left += nums[i]; // nums[i] joins the left side for the next index
        }
        return -1;
    }
}

class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        total = sum(nums)

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

export function pivotIndex(nums: number[]): number {
    let total = 0;
    for (const x of nums) total += x;

    let left = 0;
    for (let i = 0; i < nums.length; i++) {
        const right = total - left - nums[i];
        if (left === right) return i;
        left += nums[i];
    }
    return -1;
}

Complexity

Time O(N)Space O(1)

Two passes over the array (one for total, one for the check) and two integers of extra memory.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each index, loop to sum the left side and loop again to sum the right side	O(N²)	O(1)
Better	One pass builds all left sums, one pass builds all right sums, then compare	O(N)	O(N)
Optimal	Compute the total once; right side = total − left − nums[i]	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“sum of all numbers strictly to the left”A prefix sum: a running total from the left end, stopping just before i.
“sum of all numbers strictly to the right”A suffix sum: a running total from the right end — or simply the total minus everything else.
“each index”Every index needs information from both sides → a left pass and a right pass, then combine per index.
“leftmost”Scan from the left and return on the first match.

Per-index answer+needs the sum on both sides+left + self + right = total→Prefix Sum (prefix + suffix)

This is the anchor of the prefix + suffix sub-pattern: every index needs something from its left and something from its right. Here that something is a sum, and sums have a shortcut: right = total − left − nums[i], so one running variable replaces the whole suffix array. Later questions in this group use the same left-pass / right-pass idea with products and counts, where the shortcut works differently.

Don't make this mistake

Counting nums[i] on one of the sides

✗ left += nums[i]; int right = total - left; if (left == right) return i;

✓ int right = total - left - nums[i]; if (left == right) return i; left += nums[i];

The pivot itself belongs to neither side. If you add nums[i] to left before the check (or forget to subtract it from the right), you are testing a different question. Check first, then add.

Returning the last pivot instead of the first

✗ int ans = -1; for (...) if (left == right) ans = i; // keeps overwriting return ans;

✓ for (...) if (left == right) return i;

With zeros there can be several pivots, e.g. [3, −2, 4, 1, 0, 0, 2, −1, 5, 0] has pivots at 4 and 5. The question wants the leftmost one, so return immediately.

Pattern confusion: two pointers from both ends

✗ while (l < r) { if (leftSum < rightSum) leftSum += nums[l++]; else rightSum += nums[r--]; }

✓ Compute total once, then walk left to right with right = total − left − nums[i].

Moving the pointer on the smaller side only works if adding a number always makes a side bigger. With negative numbers, adding can make a side smaller, so there is no safe direction to move and the pointers can skip the real pivot. Prefix sums don't care about the sign — they just compare exact totals.

Forgetting that an empty side counts as 0

Index 0 has nothing on its left, and the last index has nothing on its right. Those sides are 0, not "invalid". [2, 1, −1] has its pivot at index 0. Starting left at 0 handles this with no special case.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture