Find Pivot Index (Left Sum = Right Sum)

🎯

Find Pivot Index (Left Sum = Right Sum)

easyHASH_MAPAmazonGoogleFacebook

Imagine you are balancing weights on a seesaw and want to find the exact point where the weights on the left and right sides are perfectly balanced.

💡 This problem is about understanding how to track cumulative sums efficiently. Beginners often struggle because they try to compute sums repeatedly instead of maintaining running totals, which leads to inefficient solutions.

📋

Problem Statement

Given an array of integers nums, find the pivot index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, return -1. If there are multiple pivot indexes, return the left-most pivot index.

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

💡

Example

Input"[1, 7, 3, 6, 5, 6]"

Output3

At index 3, left sum = 1+7+3=11 and right sum = 5+6=11, so pivot index is 3.

• Single element array → 0 (pivot is the only element)
• All elements are zero → 0 (left sum and right sum are always zero)
• No pivot index exists → -1
• Pivot index at the start → 0 if right sum equals 0

⚠️

Common Mistakes

Recomputing sums inside nested loops

Leads to time limit exceeded on large inputs

✅ Use prefix sums or running sums to avoid repeated summations

Not handling empty left or right sums correctly at edges

Incorrect pivot index returned or -1 when pivot exists

✅ Remember left sum before first element and right sum after last element are zero

Using incorrect indices for prefix sums

Wrong sums computed, leading to wrong pivot index

✅ Use prefix sums with one extra element and consistent indexing

Forgetting to return -1 if no pivot found

Function returns None or undefined, causing runtime errors

✅ Always return -1 explicitly if no pivot index matches

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly translating the problem statement into code. It helps beginners understand what the problem is asking before optimizing.

Intuition

For each index, calculate the sum of elements to the left and to the right, then compare them. If equal, return that index.

Algorithm

1. Iterate over each index in the array.
2. For each index, sum all elements to the left.
3. Sum all elements to the right.
4. Compare the two sums; if equal, return the current index.

💡 The challenge is realizing that summing repeatedly inside loops leads to high time complexity, but it clearly shows the problem's requirements.

</>

Code

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left_sum = sum(nums[:i])
        right_sum = sum(nums[i+1:])
        if left_sum == right_sum:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    print(pivotIndex([1,7,3,6,5,6]))  # Output: 3
    print(pivotIndex([0]))  # Output: 0

Line Notes

for i in range(n):Iterate over each index to check if it is a pivot

left_sum = sum(nums[:i])Calculate sum of elements to the left of current index

right_sum = sum(nums[i+1:])Calculate sum of elements to the right of current index

if left_sum == right_sum:Check if current index balances left and right sums

return -1Return -1 if no pivot index found after checking all

public class Solution {
    public static int pivotIndex(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int leftSum = 0, rightSum = 0;
            for (int j = 0; j < i; j++) leftSum += nums[j];
            for (int j = i + 1; j < n; j++) rightSum += nums[j];
            if (leftSum == rightSum) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(pivotIndex(new int[]{1,7,3,6,5,6})); // Output: 3
        System.out.println(pivotIndex(new int[]{0})); // Output: 0
    }
}

Line Notes

for (int i = 0; i < n; i++) {Loop through each index to test pivot condition

for (int j = 0; j < i; j++) leftSum += nums[j];Sum elements to the left of i

for (int j = i + 1; j < n; j++) rightSum += nums[j];Sum elements to the right of i

if (leftSum == rightSum) return i;Return index if left and right sums match

return -1;Return -1 if no pivot index found

#include <iostream>
#include <vector>
using namespace std;

int pivotIndex(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int leftSum = 0, rightSum = 0;
        for (int j = 0; j < i; j++) leftSum += nums[j];
        for (int j = i + 1; j < n; j++) rightSum += nums[j];
        if (leftSum == rightSum) return i;
    }
    return -1;
}

int main() {
    vector<int> nums = {1,7,3,6,5,6};
    cout << pivotIndex(nums) << endl; // Output: 3
    vector<int> single = {0};
    cout << pivotIndex(single) << endl; // Output: 0
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Check each index as potential pivot

for (int j = 0; j < i; j++) leftSum += nums[j];Sum elements left of i

for (int j = i + 1; j < n; j++) rightSum += nums[j];Sum elements right of i

if (leftSum == rightSum) return i;Return pivot index if sums match

return -1;Return -1 if no pivot index found

function pivotIndex(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        let leftSum = 0, rightSum = 0;
        for (let j = 0; j < i; j++) leftSum += nums[j];
        for (let j = i + 1; j < n; j++) rightSum += nums[j];
        if (leftSum === rightSum) return i;
    }
    return -1;
}

// Test
console.log(pivotIndex([1,7,3,6,5,6])); // Output: 3
console.log(pivotIndex([0])); // Output: 0

Line Notes

for (let i = 0; i < n; i++) {Iterate over each index to check pivot condition

for (let j = 0; j < i; j++) leftSum += nums[j];Sum elements to the left of i

for (let j = i + 1; j < n; j++) rightSum += nums[j];Sum elements to the right of i

if (leftSum === rightSum) return i;Return index if left and right sums are equal

return -1;Return -1 if no pivot index found

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each index, sums of left and right sides are computed, each taking O(n) time, resulting in O(n^2) total.

💡 For n=1000, this means about 1,000,000 operations, which is slow and inefficient.

Interview Verdict: TLE for large inputs

This approach is too slow for large arrays but is useful to understand the problem and correctness before optimizing.

🧠

Prefix Sum Array

💡 This approach introduces prefix sums to avoid repeated summations, teaching how to precompute and reuse information efficiently.

Intuition

Precompute prefix sums so that left and right sums can be found in O(1) time for each index, reducing overall complexity.

Algorithm

1. Compute prefix sums array where prefix[i] is sum of nums[0..i-1].
2. Iterate over each index i.
3. Calculate left sum as prefix[i].
4. Calculate right sum as prefix[n] - prefix[i+1].
5. If left sum equals right sum, return i.

💡 The key insight is using prefix sums to get sums instantly, avoiding nested loops.

</>

Code

def pivotIndex(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    for i in range(n):
        left_sum = prefix[i]
        right_sum = prefix[n] - prefix[i+1]
        if left_sum == right_sum:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    print(pivotIndex([1,7,3,6,5,6]))  # Output: 3
    print(pivotIndex([2,1,-1]))  # Output: 0

Line Notes

prefix = [0] * (n + 1)Initialize prefix sums array with extra space for zero prefix

prefix[i+1] = prefix[i] + nums[i]Build prefix sums cumulatively

left_sum = prefix[i]Left sum is sum of elements before i

right_sum = prefix[n] - prefix[i+1]Right sum is total sum minus prefix sum up to index i inclusive

return -1Return -1 if no pivot index found

public class Solution {
    public static int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        for (int i = 0; i < n; i++) {
            int leftSum = prefix[i];
            int rightSum = prefix[n] - prefix[i + 1];
            if (leftSum == rightSum) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(pivotIndex(new int[]{1,7,3,6,5,6})); // Output: 3
        System.out.println(pivotIndex(new int[]{2,1,-1})); // Output: 0
    }
}

Line Notes

int[] prefix = new int[n + 1];Create prefix sums array with one extra element

prefix[i + 1] = prefix[i] + nums[i];Compute cumulative sums

int leftSum = prefix[i];Left sum is prefix sum before index i

int rightSum = prefix[n] - prefix[i + 1];Right sum is total sum minus prefix sum up to index i inclusive

return -1;Return -1 if no pivot index found

#include <iostream>
#include <vector>
using namespace std;

int pivotIndex(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    for (int i = 0; i < n; i++) {
        int leftSum = prefix[i];
        int rightSum = prefix[n] - prefix[i + 1];
        if (leftSum == rightSum) return i;
    }
    return -1;
}

int main() {
    vector<int> nums = {1,7,3,6,5,6};
    cout << pivotIndex(nums) << endl; // Output: 3
    vector<int> test = {2,1,-1};
    cout << pivotIndex(test) << endl; // Output: 0
    return 0;
}

Line Notes

vector<int> prefix(n + 1, 0);Initialize prefix sums vector with zeros

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively

int leftSum = prefix[i];Left sum is prefix sum before current index

int rightSum = prefix[n] - prefix[i + 1];Right sum is total sum minus prefix sum up to index i inclusive

return -1;Return -1 if no pivot index found

function pivotIndex(nums) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    for (let i = 0; i < n; i++) {
        const leftSum = prefix[i];
        const rightSum = prefix[n] - prefix[i + 1];
        if (leftSum === rightSum) return i;
    }
    return -1;
}

// Test
console.log(pivotIndex([1,7,3,6,5,6])); // Output: 3
console.log(pivotIndex([2,1,-1])); // Output: 0

Line Notes

const prefix = new Array(n + 1).fill(0);Create prefix sums array initialized with zeros

prefix[i + 1] = prefix[i] + nums[i];Compute running totals for prefix sums

const leftSum = prefix[i];Left sum is prefix sum before index i

const rightSum = prefix[n] - prefix[i + 1];Right sum is total sum minus prefix sum up to index i inclusive

return -1;Return -1 if no pivot index found

⏱

Complexity

TimeO(n)

SpaceO(n)

Prefix sums are computed once in O(n), then each index is checked in O(1), total O(n).

💡 For n=100,000, this means about 200,000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This approach is efficient and acceptable for large inputs, showing a clear improvement over brute force.

🧠

Optimal (Single Pass with Running Left Sum)

💡 This approach teaches how to track running state dynamically without extra space, a key skill for efficient coding.

Intuition

Calculate total sum first, then iterate once, tracking left sum. Right sum can be derived by subtracting left sum and current element from total sum.

Algorithm

1. Calculate total sum of the array.
2. Initialize left sum to zero.
3. Iterate over each index i:
4. Check if left sum equals total sum minus left sum minus nums[i].
5. If equal, return i; else add nums[i] to left sum.
6. If no pivot found, return -1.

💡 The key is realizing right sum can be computed without extra storage by subtracting left sum and current element from total.

</>

Code

def pivotIndex(nums):
    total = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        if left_sum == total - left_sum - num:
            return i
        left_sum += num
    return -1

# Driver code
if __name__ == '__main__':
    print(pivotIndex([1,7,3,6,5,6]))  # Output: 3
    print(pivotIndex([0]))  # Output: 0

Line Notes

total = sum(nums)Calculate total sum once to use for right sum calculation

left_sum = 0Initialize running left sum before iteration

for i, num in enumerate(nums):Iterate over array with index and value

if left_sum == total - left_sum - num:Check if left sum equals right sum derived from total sum minus left sum minus current element

left_sum += numUpdate left sum by adding current element

return -1Return -1 if no pivot index found

public class Solution {
    public static int pivotIndex(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (leftSum == total - leftSum - nums[i]) return i;
            leftSum += nums[i];
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(pivotIndex(new int[]{1,7,3,6,5,6})); // Output: 3
        System.out.println(pivotIndex(new int[]{0})); // Output: 0
    }
}

Line Notes

int total = 0;Initialize total sum accumulator

for (int num : nums) total += num;Compute total sum of array

int leftSum = 0;Initialize left sum before iteration

if (leftSum == total - leftSum - nums[i]) return i;Check pivot condition using total sum minus left sum and current element

leftSum += nums[i];Add current element to left sum

return -1;Return -1 if no pivot index found

#include <iostream>
#include <vector>
using namespace std;

int pivotIndex(vector<int>& nums) {
    int total = 0;
    for (int num : nums) total += num;
    int leftSum = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (leftSum == total - leftSum - nums[i]) return i;
        leftSum += nums[i];
    }
    return -1;
}

int main() {
    vector<int> nums = {1,7,3,6,5,6};
    cout << pivotIndex(nums) << endl; // Output: 3
    vector<int> single = {0};
    cout << pivotIndex(single) << endl; // Output: 0
    return 0;
}

Line Notes

int total = 0;Initialize total sum variable

for (int num : nums) total += num;Calculate total sum of all elements

int leftSum = 0;Initialize running left sum

if (leftSum == total - leftSum - nums[i]) return i;Check if current index is pivot by comparing left sum with right sum derived from total

leftSum += nums[i];Update left sum by adding current element

return -1;Return -1 if no pivot index found

function pivotIndex(nums) {
    const total = nums.reduce((acc, val) => acc + val, 0);
    let leftSum = 0;
    for (let i = 0; i < nums.length; i++) {
        if (leftSum === total - leftSum - nums[i]) return i;
        leftSum += nums[i];
    }
    return -1;
}

// Test
console.log(pivotIndex([1,7,3,6,5,6])); // Output: 3
console.log(pivotIndex([0])); // Output: 0

Line Notes

const total = nums.reduce((acc, val) => acc + val, 0);Compute total sum using reduce

let leftSum = 0;Initialize left sum accumulator

for (let i = 0; i < nums.length; i++) {Iterate over array indices

if (leftSum === total - leftSum - nums[i]) return i;Check pivot condition using total sum minus left sum and current element

leftSum += nums[i];Add current element to left sum

return -1;Return -1 if no pivot index found

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass after total sum calculation, no extra arrays needed.

💡 For n=100,000, this means about 100,000 operations, very efficient and scalable.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews due to its simplicity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the optimal single pass approach after explaining brute force and prefix sums.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Prefix Sum Array	O(n)	O(n)	No	N/A	Good intermediate step to explain optimization
3. Optimal Single Pass	O(n)	O(1)	No	N/A	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to optimize. Read it before every mock interview to build confidence.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Explain prefix sums to optimize repeated summations.Step 4: Present the optimal single pass solution using running sums.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to identify inefficiencies, optimize using prefix sums, and track running state without extra space.

Common Follow-ups

• What if multiple pivot indexes exist? → Return the left-most one.
• Can you solve it with O(1) space? → Yes, using running sums and total sum.

💡 These follow-ups check if you understand edge cases and space optimization, common interview curveballs.

🔍

Pattern Recognition

When to Use

1) Need to find an index balancing left and right sums; 2) Problem involves prefix or running sums; 3) Constraints require O(n) or better; 4) Problem hints at tracking cumulative state.

Signature Phrases

pivot indexleft sum equals right sumbalance point

NOT This Pattern When

Problems that require sorting or two pointers without cumulative sums, e.g., Two Sum.

Similar Problems

3Sum Closest - also uses prefix sums and two pointersSubarray Sum Equals K - tracks running sums to find subarraysMaximum Subarray - uses running sums to find max sum subarray

Practice

1. Given the following code, what is the final output of count_nice_subarrays([2,1,2,1], 1)?

easy

A. 4

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace at_most_k(nums, 1)

   Counting subarrays with at most 1 odd: - right=0 (2): odd_count=0, count=1 - right=1 (1): odd_count=1, count=1+(1-0+1)=3 - right=2 (2): odd_count=1, count=3+(2-0+1)=6 - right=3 (1): odd_count=2 >1, shrink left until odd_count=1 left moves from 0 to 1, odd_count=1, count=6+(3-1+1)=9 Total at_most_k(1)=9

2. Step 2: Trace at_most_k(nums, 0)

   Counting subarrays with at most 0 odd: - right=0 (2): odd_count=0, count=1 - right=1 (1): odd_count=1 >0, shrink left to 1, odd_count=0, count=1+(1-1+1)=2 - right=2 (2): odd_count=0, count=2+(2-1+1)=4 - right=3 (1): odd_count=1 >0, shrink left to 3, odd_count=0, count=4+(3-3+1)=5 Total at_most_k(0)=5

3. Final Answer:

   count_nice_subarrays = 9 - 5 = 4

4. Quick Check:

   Rechecking counts confirms 4 subarrays with exactly 1 odd [OK]

Hint: Subtract at_most_k(k-1) from at_most_k(k) [OK]

Common Mistakes:

• Off-by-one in counting subarrays
• Miscounting odd numbers in window
• Forgetting to shrink window correctly

2. You need to find the length of the longest substring in a string that contains at most two distinct characters. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a brute force approach checking all substrings with nested loops and counting distinct characters each time.

B. Use a sliding window with a frequency map to track character counts and adjust window size dynamically.

C. Use dynamic programming to store results of substrings and build up the solution.

D. Use a greedy approach that always picks the next character if it doesn't increase distinct count beyond two.

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest substring with at most two distinct characters, which suggests a variable-length window that expands and contracts based on distinct character count.

2. Step 2: Identify suitable algorithm

   Sliding window with a frequency map efficiently tracks character counts and distinct characters, allowing O(n) time complexity by adjusting window boundaries dynamically.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with frequency map is the classic optimal approach for this problem [OK]

Hint: Sliding window tracks distinct chars in O(n) time [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing DP with substring problems
• Assuming greedy always works

3. Given the following code and input nums = [3,1,1,1,5], x = 5, what is the returned value?

easy

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Calculate totalSum and target

   totalSum = 3+1+1+1+5 = 11; target = 11 - 5 = 6.

2. Step 2: Use sliding window to find longest subarray summing to 6

   Window expands: [3] sum=3, [3,1] sum=4, [3,1,1] sum=5, [3,1,1,1] sum=6 -> max_len=4; next, add 5 sum=11 > 6, shrink from left: remove 3 sum=8 >6, remove 1 sum=7 >6, remove 1 sum=6 -> max_len=4 remains (subarray [1,1,1]).

3. Step 3: Calculate minimum operations

   Minimum removals = array length - max_len = 5 - 4 = 1.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Longest subarray length 4 -> min ops = 1 [OK]

Hint: Sliding window finds longest subarray sum [OK]

Common Mistakes:

• Off-by-one errors in window length calculation
• Miscomputing sums when shrinking window
• Confusing min operations with longest subarray length

4. The following code attempts to solve the Continuous Subarray Sum problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: updating remainder_map[running_sum] = i before checking condition

B. Line 11: verifying subarray length > 1

C. Line 9: checking if running_sum in remainder_map

D. Line 3: initializing running_sum to 0

Solution

1. Step 1: Understand remainder_map update timing

   The original code updated remainder_map[running_sum] = i before checking if running_sum already exists, overwriting the earliest index.

2. Step 2: Identify consequence of overwriting

   Overwriting earliest index causes missing longer subarrays that satisfy the condition, leading to false negatives.

3. Step 3: Correct the code

   Update remainder_map[running_sum] = i only if running_sum is not already in remainder_map, preserving earliest occurrence.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct code inserts remainder only if not present to preserve earliest index [OK]

Hint: Earliest remainder index must be preserved to find valid subarrays [OK]

Common Mistakes:

• Updating remainder map on every occurrence
• Not checking subarray length >= 2
• Modulo by zero errors

5. Consider the following buggy code for finding the longest substring with at most two distinct characters. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line inside while loop missing check to decrement distinct_count when freq hits zero

B. Line where freq[ord(s[right])] is incremented

C. Line inside while loop where freq[ord(s[left])] is decremented

D. Line where distinct_count is incremented when freq is zero

Solution

1. Step 1: Identify the bug

   The code decrements freq for s[left] inside the while loop but does not check if freq reaches zero to decrement distinct_count.

2. Step 2: Consequences of missing check

   Without decrementing distinct_count, the while loop condition distinct_count > 2 never becomes false, causing infinite loop or incorrect window size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing distinct_count decrement inside while loop is a classic subtle bug [OK]

Hint: Check distinct_count update when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement distinct_count
• Incorrect window size calculation
• Not breaking early in brute force