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 Python function that checks if an array can be paired such that sums are divisible by k. What is the return value when called with nums = [2, 4, 1, 3] and k = 5?

def canArrange(nums, k):
    if len(nums) % 2 != 0:
        return False
    freq = {}
    for num in nums:
        r = ((num % k) + k) % k
        freq[r] = freq.get(r, 0) + 1
    if freq.get(0, 0) % 2 != 0:
        return False
    for r in freq:
        if r != 0:
            complement = (k - r) % k
            if freq.get(r, 0) != freq.get(complement, 0):
                return False
    if k % 2 == 0 and freq.get(k // 2, 0) % 2 != 0:
        return False
    return True

easy

A. false

B. Depends on order of iteration over freq keys

C. Raises an exception due to missing key

D. true

Solution

1. Step 1: Compute remainders and their frequencies

   nums = [2,4,1,3], k=5 Remainders: 2%5=2, 4%5=4, 1%5=1, 3%5=3 freq = {2:1,4:1,1:1,3:1}

2. Step 2: Check pairing conditions

   freq[0] = 0 (even), Check pairs: - remainder 1 pairs with 4 -> freq[1]=1, freq[4]=1 (equal) - remainder 2 pairs with 3 -> freq[2]=1, freq[3]=1 (equal) k is odd, so no special k/2 check needed All conditions satisfied -> return true

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All remainder pairs match frequencies [OK]

Hint: Check remainder frequencies and their complements [OK]

Common Mistakes:

• Forgetting to handle negative numbers modulo
• Not checking freq[0] is even
• Assuming order of freq iteration affects result

2. 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

3. What is the time complexity of the optimal approach that uses a hash map to count frequencies of remainders modulo k for the problem of checking if array pairs sum to multiples of k?

medium

A. O(n * k) because for each element we check all possible remainders

B. O(n^2) due to nested loops checking pairs

C. O(n) because we iterate over the array once and then over at most k remainders

D. O(k^2) because we compare all remainder pairs

Solution

1. Step 1: Analyze iteration over input array

   The algorithm iterates once over the array of size n to compute remainder frequencies, which is O(n).

2. Step 2: Analyze iteration over remainder keys

   It then iterates over at most k remainder keys to verify pairing conditions, which is O(k).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(n + k), simplified to O(n) when n >> k [OK]

Hint: Frequency map iteration is O(k), array iteration is O(n) [OK]

Common Mistakes:

• Confusing nested loops with frequency map iteration
• Assuming O(n*k) because of remainder checks
• Ignoring that k is usually much smaller than n

4. Identify the bug in the following code snippet for the Minimum Operations to Reduce X to Zero problem:

medium

A. Line with 'if target == 0: return -1' should return len(nums) instead.

B. The while loop condition should be 'current_sum >= target' instead of '>'.

C. The initialization of max_len should be 0 instead of -1.

D. The final return should be 'max_len' instead of 'len(nums) - max_len'.

Solution

1. Step 1: Understand the edge case when target == 0

   If target == 0, it means totalSum == x, so removing all elements is needed, so minimum operations = length of array.

2. Step 2: Identify incorrect return value

   The code returns -1 incorrectly, which signals no solution, but the correct answer is to remove all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning -1 here causes wrong output on full removal case [OK]

Hint: Check edge cases where x equals total sum [OK]

Common Mistakes:

• Returning -1 instead of full length when target == 0
• Misinterpreting no solution vs full removal
• Ignoring edge cases in initial checks

5. What is the time complexity of the optimal prefix sum with hash map solution for the Subarray Sum Equals K problem, given an input array of length n?

medium

A. O(n) because each element is processed once and hash map operations are O(1) on average

B. O(n) for iteration plus O(n) for prefix sum storage, total O(n) space and time

C. O(n log n) due to sorting or balanced tree operations in the hash map

D. O(n^2) due to nested loops over the array

Solution

1. Step 1: Identify main operations

   The algorithm iterates over the array once, updating running_sum and hash map counts.

2. Step 2: Analyze hash map operations

   Hash map insertions and lookups are O(1) on average, so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No nested loops or sorting involved, so O(n) time complexity. [OK]

Hint: Hash map lookups are average O(1), not O(log n) [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming hash map operations are O(log n)
• Counting prefix sum storage as extra time