Code Implementation

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

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total = 0, left_sum = 0;
        for (int n : nums) total += n;
        for (int i = 0; i < nums.size(); ++i) {
            if (left_sum == total - left_sum - nums[i]) return i;
            left_sum += nums[i];
        }
        return -1;
    }
};
      

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

var pivotIndex = function(nums) {
    let total = nums.reduce((a, b) => a + b, 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;
};
      

Problem Description

Given an array of integers nums, your task is to find the "pivot index" of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the right of the index.

• If no such index exists, return -1.
• If there are multiple pivot indexes, return the left-most one.
• Constraints:
  • 1 ≤ nums.length ≤ 10⁴
  • -1000 ≤ nums[i] ≤ 1000

Note: You cannot reuse elements; the left and right sums must exclude the element at the pivot index.

Thought Process

To solve this problem, the first idea that comes to mind is to check each index in the array and calculate the sum of elements to its left and the sum to its right. If these two sums are equal, we've found the pivot index. However, this approach would require two passes for each index (one for the left sum and one for the right sum), leading to a time complexity of O(n²), which is inefficient for large arrays.

To optimize, we realize that we can compute the total sum of the array once. Then, as we iterate through the array, we can keep a running sum of the left side. The sum of the right side can then be calculated as total_sum - left_sum - nums[i]. If at any index the left sum equals the right sum, we've found our pivot.

This approach reduces the time complexity to O(n) and only needs a single pass through the array after calculating the total sum.

Solution Approach

• Step 1: Compute the total sum of the array and store it in a variable (e.g., total).
• Step 2: Initialize a variable left_sum to 0. This will keep track of the sum of elements to the left of the current index.
• Step 3: Iterate through the array using a loop:
  • At each index i, check if left_sum == total - left_sum - nums[i].
  • If true, return i as the pivot index.
  • If not, add nums[i] to left_sum and continue.
• Step 4: If the loop completes without finding a pivot, return -1.

This algorithm is efficient because:

• It only needs to calculate the total sum once.
• It keeps a running total for the left sum, so each check is O(1).
• It only loops through the array once after the initial sum calculation.

Example Walkthrough

Let's consider the example nums = [1, 7, 3, 6, 5, 6].

1. Compute total sum: 1 + 7 + 3 + 6 + 5 + 6 = 28
2. Initialize left_sum = 0
3. Iterate:
   • i = 0: left_sum = 0, right_sum = 28 - 0 - 1 = 27 (not equal)
   • i = 1: left_sum = 1, right_sum = 28 - 1 - 7 = 20 (not equal)
   • i = 2: left_sum = 8, right_sum = 28 - 8 - 3 = 17 (not equal)
   • i = 3: left_sum = 11, right_sum = 28 - 11 - 6 = 11 (equal!)
4. At index 3, the sum to the left (1 + 7 + 3 = 11) equals the sum to the right (5 + 6 = 11). So, return 3 as the pivot index.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²) — For each index, sum left and right sides separately.
  • Space Complexity: O(1) — Only counters are used.
• Optimized approach:
  • Time Complexity: O(n) — One pass to compute total sum, one pass to find pivot.
  • Space Complexity: O(1) — Only a few integer variables are used.

The optimized approach is efficient and suitable for large arrays.

Summary

The Find Pivot Index problem tests your ability to balance subarray sums efficiently. By leveraging the total sum of the array and keeping a running left sum, we can check the pivot condition in a single pass. This avoids unnecessary repeated summing and results in a clean, O(n) solution. The key insight is realizing that the right sum at any index is simply the total sum minus the left sum and the current element.