Find Pivot Index

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all numbers strictly to the left of the index equals the sum of all numbers strictly to the index's right.

If the index is on the left edge, the left sum is 0 (no elements to the left). Similarly for the right edge.

Return the leftmost pivot index. Return -1 if no such index exists.

Examples:

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

Output: 3

Explanation: The pivot index is 3. Left sum = 1+7+3 = 11, Right sum = 5+6 = 11.

Input: nums = [1,2,3]

Output: -1

Explanation: No index satisfies the conditions.

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

Output: 0

Explanation: Pivot index is 0. Left sum = 0, Right sum = 1+(-1) = 0.

Constraints

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Editorial

Intuition:

The pivot index exists when the sum of elements to the left equals the sum to the right. By precomputing the total sum, we can derive the right sum for any index as total - left_sum - nums[i]. Maintaining a running left_sum during iteration allows O(1) right sum calculation per index.

Approach:

Compute the total sum of all elements in the array.
Initialize left_sum to 0 (sum of elements before the first index).
Iterate through each index i from 0 to n-1:
1. Calculate right_sum = total_sum - left_sum - nums[i].
2. If left_sum == right_sum, return i (leftmost pivot).
3. Otherwise, add nums[i] to left_sum for the next iteration.
If no pivot is found after the loop, return -1.

class Solution {
public:
    int pivotIndex(const vector<int>& nums) {
        int total = 0;
        for (int num : nums) total += num;
        int left_sum = 0;
        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;
        for (int num : nums) total += num;
        int left_sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (left_sum == total - left_sum - nums[i]) {
                return i;
            }
            left_sum += nums[i];
        }
        return -1;
    }
}
class Solution:
    def pivot_index(self, 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
class Solution {
    pivotIndex(nums) {
        let total = nums.reduce((a, b) => a + b, 0);
        let left_sum = 0;
        for (let i = 0; i < nums.length; i++) {
            if (left_sum === total - left_sum - nums[i]) {
                return i;
            }
            left_sum += nums[i];
        }
        return -1;
    }
}

Complexity Analysis:

Time Complexity: O(n), where n is the array length. We perform two linear passes: one for the total sum and one for finding the pivot index.

Space Complexity: O(1), as only a few integer variables are used regardless of input size.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories