Find Pivot Index (Left Sum = Right Sum)

📋

Problem

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.

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

Edge cases: 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

</>

IDE

def pivotIndex(nums: list[int]) -> int:public int pivotIndex(int[] nums)int pivotIndex(vector<int> &nums)function pivotIndex(nums)

def pivotIndex(nums):
    # Write your solution here
    pass

class Solution {
    public int pivotIndex(int[] nums) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int pivotIndex(vector<int> &nums) {
    // Write your solution here
    return -1;
}

function pivotIndex(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: -1Fails to find pivot index when it exists, often due to incorrect sum calculations or missing left-most pivot.✅ Track total sum and running left sum; return index when left sum equals total minus left sum minus current element.

Wrong: Wrong pivot index (e.g., last pivot instead of left-most)Returns any pivot index instead of the left-most one.✅ Return the first index where left sum equals right sum during iteration.

Wrong: Index out of range or off-by-one errorsIncorrectly summing elements including or excluding pivot element.✅ Ensure sums exclude the pivot element itself; left sum is sum of elements before index, right sum is total minus left sum minus current element.

Wrong: Timeout or no outputUsing O(n^2) brute force approach on large inputs.✅ Implement O(n) single pass solution using running sums and total sum.

Wrong: Incorrect pivot index due to negative numbersMiscomputing sums when array contains negative values.✅ Use total sum and running left sum correctly; do not assume all numbers are positive.

✓

Test Cases

Try testing your code on minimal and boundary inputs like single element arrays.

Consider tricky cases with negative numbers and multiple pivots.

Focus on optimizing your solution to run in linear time using running sums.

t1_01basic

Input{"nums":[1,7,3,6,5,6]}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Consider the sums of elements to the left and right of each index.

💡 Use prefix sums or running totals to efficiently compare left and right sums.

💡 Track total sum and running left sum; pivot if left sum equals total minus left sum minus current element.

Why it failed: Incorrect pivot index returned; likely not correctly comparing left and right sums or missing the left-most pivot. Fix by tracking total sum and updating left sum as you iterate.

✓ Correctly identifies the pivot index by balancing left and right sums.

t1_02basic

Input{"nums":[2,1,-1]}

Expected0

⏱ Performance - must finish in 2000ms

At index 0, left sum = 0 and right sum = 1 + (-1) = 0, so pivot index is 0.

💡 Check if the pivot can be at the start of the array where left sum is zero.

💡 Remember to handle negative numbers correctly when computing sums.

💡 Use total sum and running left sum to verify if left sum equals right sum at each index.

Why it failed: Fails to identify pivot at index 0; likely not handling left sum = 0 case correctly. Fix by initializing left sum to zero and checking at each index.

✓ Correctly handles pivot at start of array with left sum zero.

t2_01edge

Input{"nums":[0]}

Expected0

⏱ Performance - must finish in 2000ms

Single element array; pivot index is 0 since left and right sums are zero.

💡 Consider the smallest input size: a single element array.

💡 Left and right sums are empty sums, both zero, so pivot is index 0.

💡 Return 0 immediately if array length is 1 or check sums accordingly.

Why it failed: Fails single element case by returning -1 or other index; fix by returning 0 when array length is 1.

✓ Correctly returns 0 for single element array.

t2_02edge

Input{"nums":[0,0,0,0]}

Expected0

⏱ Performance - must finish in 2000ms

All elements zero; left sum and right sum always zero, so pivot index is 0 (left-most).

💡 Test arrays where all elements are zero.

💡 Left and right sums are always zero, so first index is pivot.

💡 Ensure code returns left-most pivot index when multiple pivots exist.

Why it failed: Fails to return left-most pivot index when multiple pivots exist; fix by returning first index where condition holds.

✓ Correctly returns left-most pivot index when all elements are zero.

t2_03edge

Input{"nums":[1,2,3]}

Expected-1

⏱ Performance - must finish in 2000ms

No pivot index exists where left sum equals right sum; return -1.

💡 Check cases where no pivot index exists.

💡 Verify that no index satisfies left sum == right sum.

💡 Return -1 if no pivot found after checking all indices.

Why it failed: Returns incorrect pivot index when none exists; fix by returning -1 if no index satisfies condition.

✓ Correctly returns -1 when no pivot index exists.

t3_01corner

Input{"nums":[1,2,3,4,6]}

Expected3

⏱ Performance - must finish in 2000ms

Pivot index is 3; left sum = 1+2+3=6, right sum = 6.

💡 Beware of greedy approaches that pick first index without checking all.

💡 Use running sums to verify pivot condition at each index.

💡 Track total sum and update left sum correctly to find pivot.

Why it failed: Greedy approach fails by returning wrong pivot index; fix by checking all indices with running sums.

✓ Correctly finds pivot index by checking all indices.

t3_02corner

Input{"nums":[2,1,-1,2]}

Expected-1

⏱ Performance - must finish in 2000ms

No pivot index exists; total sum=4. For each index, left sum and right sum differ, so return -1.

💡 Check that negative numbers do not confuse sum calculations.

💡 Verify pivot condition carefully with total sum minus left sum minus current element.

💡 Do not assume pivot must be positive or at certain positions.

Why it failed: Incorrectly returns pivot index due to miscalculating sums with negative numbers; fix by correctly computing right sum as total - left sum - current element.

✓ Correctly handles negative numbers and returns -1 when no pivot exists.

t3_03corner

Input{"nums":[1,-1,0]}

Expected2

⏱ Performance - must finish in 2000ms

Pivot index is 2; left sum = 1 + (-1) = 0, right sum = 0.

💡 Check for off-by-one errors in summing left and right parts.

💡 Ensure sums exclude the pivot element itself.

💡 Use running left sum and total sum minus left sum minus current element to find pivot.

Why it failed: Off-by-one error causes wrong pivot index; fix by excluding current element from both left and right sums correctly.

✓ Correctly excludes pivot element and finds correct pivot index.

t4_01performance

Input{"nums":[1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with alternating large positive and negative values; O(n) solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use a single pass with running left sum and total sum to achieve O(n) time.

💡 Avoid recomputing sums repeatedly; track sums incrementally.

Why it failed: Brute force or nested loops cause TLE; fix by implementing O(n) single pass solution using running sums.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following code snippet implementing the optimal prefix sum with hash map approach. What is the final returned value when the input is nums = [1, 2, 3] and k = 3?

def subarraySum(nums, k):
    count = 0
    running_sum = 0
    prefix_counts = {0: 1}
    for num in nums:
        running_sum += num
        if running_sum - k in prefix_counts:
            count += prefix_counts[running_sum - k]
        prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
    return count

print(subarraySum([1, 2, 3], 3))

easy

A. 3

B. 0

C. 1

D. 2

Solution

1. Step 1: Trace running_sum and prefix_counts

   Iteration 1: running_sum=1, prefix_counts={0:1,1:1}, count=0 Iteration 2: running_sum=3, running_sum-k=0 in prefix_counts, count=1, prefix_counts={0:1,1:1,3:1} Iteration 3: running_sum=6, running_sum-k=3 in prefix_counts, count=2, prefix_counts={0:1,1:1,3:1,6:1}

2. Step 2: Return count

   Count is 2, representing subarrays [1,2] and [3].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Count matches expected subarrays summing to 3. [OK]

Hint: Track running_sum and prefix_counts carefully [OK]

Common Mistakes:

• Off-by-one errors in counting
• Forgetting to initialize prefix_counts with {0:1}
• Miscounting subarrays ending at current index

2. The following code attempts to find all anagrams of p in s using the sliding window approach. Identify the line that contains a subtle bug causing incorrect results on some inputs.

medium

A. Missing matches adjustment after decreasing s_count[index_l]

B. Line updating s_count[index_l] after removing left char

C. Line appending index l to result when matches == 26

D. Line updating s_count[index_r] and matches after adding right char

Solution

1. Step 1: Identify where matches count is updated

   Matches are updated correctly when adding the right character but not when removing the left character.

2. Step 2: Locate missing matches adjustment

   After decreasing s_count[index_l], matches should be updated if counts now match or mismatch, but this is missing, causing incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug causes false negatives on some inputs due to stale matches count [OK]

Hint: Check matches update after both add and remove steps [OK]

Common Mistakes:

• Forgetting to update matches after removing left char
• Updating matches twice incorrectly
• Off-by-one in window boundaries

3. The following code attempts to implement the optimal prefix sum with hash map approach for Subarray Sum Equals K. Which line contains a subtle bug that causes incorrect counting of subarrays starting at index 0?

def subarraySum(nums, k):
    count = 0
    running_sum = 0
    prefix_counts = {}
    for num in nums:
        running_sum += num
        if running_sum - k in prefix_counts:
            count += prefix_counts[running_sum - k]
        prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
    return count

medium

A. Line 3: prefix_counts initialized as empty dictionary instead of {0:1}

B. Line 6: Missing check for running_sum == k before hash map lookup

C. Line 7: Incorrect update of prefix_counts frequency

D. Line 2: running_sum initialized to 0 instead of null

Solution

1. Step 1: Identify initialization issue

   prefix_counts must start with {0:1} to count subarrays starting at index 0 correctly.

2. Step 2: Understand effect of empty initialization

   Without {0:1}, subarrays that sum exactly to k from the start are missed, causing undercount.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding {0:1} fixes counting of subarrays starting at index 0. [OK]

Hint: Always initialize prefix_counts with {0:1} [OK]

Common Mistakes:

• Forgetting initial prefix sum count
• Updating hash map before checking condition
• Misinitializing running_sum

4. What is the time complexity of the optimal two-pointer approach for the Summary Ranges problem on an input list of length n?

medium

A. O(n log n) due to sorting the input before scanning for ranges.

B. O(n²) because the inner while loop can run up to n times for each start pointer.

C. O(n) because each element is visited at most twice by the two pointers combined.

D. O(n) but with O(n) auxiliary space for storing the output ranges.

Solution

1. Step 1: Analyze outer and inner loops

   The outer loop advances start pointer, inner loop advances end pointer; together they move forward without revisiting elements.

2. Step 2: Confirm total iterations

   Each element is visited at most twice (once by start, once by end), so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two pointers linear scan -> O(n) time [OK]

Hint: Two pointers each move forward once -> O(n) time [OK]

Common Mistakes:

• Assuming inner loop restarts fully causing O(n²)
• Confusing sorting cost if input is already sorted
• Ignoring that output space is separate from time complexity

5. Suppose the problem is modified so that elements can be removed multiple times (i.e., you can reuse elements from the ends infinitely) to reduce x to zero. Which approach correctly adapts to this variant?

hard

A. Use a dynamic programming approach to find the minimum number of removals with unlimited reuse, similar to coin change.

B. Apply a greedy approach removing the largest elements repeatedly from ends until x is zero.

C. Use the same sliding window approach on the original array once; it still works without changes.

D. Use prefix and suffix sums with a hash map but ignore overlapping since reuse is allowed.

Solution

1. Step 1: Understand the reuse variant

   Since elements can be reused infinitely, the problem becomes similar to coin change where you want minimum coins (elements) summing to x.

2. Step 2: Recognize sliding window limitation

   Sliding window relies on contiguous subarrays without reuse; it cannot handle infinite reuse.

3. Step 3: Use DP approach

   Dynamic programming can find minimum removals with unlimited reuse by building solutions for all sums up to x.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles reuse, sliding window does not [OK]

Hint: Reuse implies DP coin change pattern [OK]

Common Mistakes:

• Assuming sliding window works with reuse
• Ignoring infinite reuse changes problem nature
• Using greedy which fails on some sums