724. Find Pivot Index

Description

Given an array of integers nums, calculate 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 index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Intuition

The pivot index in an array is the point where the sum of elements on the left side is equal to the sum of elements on the right side. The idea is to iterate through the array while keeping track of the cumulative sum from both ends. By doing this, we can efficiently determine if any index satisfies the condition where the left and right sums are equal.

Approach

1. Prefix and Postfix Sums: - First, create two auxiliary arrays, prefix and postfix. The prefix array will store the cumulative sum of elements from the left up to the current index, while the postfix array will store the cumulative sum of elements from the right up to the current index. - For the prefix array, start with an initial value of 0 and compute the cumulative sum as you traverse the array from left to right. - Similarly, populate the postfix array by traversing the array from right to left.
2. Finding the Pivot Index: - After constructing the prefix and postfix arrays, iterate through the original array to check if any index i satisfies the condition where prefix[i] equals postfix[i+1]. - If such an index is found, return it as the pivot index.
3. Edge Cases: - Handle edge cases where the pivot might be at the start or the end of the array. If no such index is found, return -1.

Complexity

Time Complexity:

The solution runs in O(n) time, where n is the length of the array. This is because we traverse the array a few times to build the prefix and postfix arrays and then perform a final pass to check for the pivot index.

Space Complexity:

The space complexity is O(n) due to the additional space required for the prefix and postfix arrays.

Code

C++

class Solution {
public:
    int pivotIndex(std::vector& nums) {
        int len = nums.size();
        std::vector prefix(len + 1, 0), postfix(len + 1, 0);

        for (int i = 0; i < len; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        for (int i = len - 1; i >= 0; i--) {
            postfix[i] = postfix[i + 1] + nums[i];
        }

        for (int i = 0; i < len; i++) {
            if (prefix[i] == postfix[i + 1]) {
                return i;
            }
        }

        return -1;
    }
};

Python

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        len_nums = len(nums)
        prefix = [0] * (len_nums + 1)
        postfix = [0] * (len_nums + 1)

        for i in range(len_nums):
            prefix[i + 1] = prefix[i] + nums[i]

        for i in range(len_nums - 1, -1, -1):
            postfix[i] = postfix[i + 1] + nums[i]

        for i in range(len_nums):
            if prefix[i] == postfix[i + 1]:
                return i

        return -1

Java

class Solution {
    public int pivotIndex(int[] nums) {
        int len = nums.length;
        int[] prefix = new int[len + 1];
        int[] postfix = new int[len + 1];

        for (int i = 0; i < len; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        for (int i = len - 1; i >= 0; i--) {
            postfix[i] = postfix[i + 1] + nums[i];
        }

        for (int i = 0; i < len; i++) {
            if (prefix[i] == postfix[i + 1]) {
                return i;
            }
        }

        return -1;
    }
}

JavaScript

var pivotIndex = function (nums) {
    let len = nums.length, prefix = [0], postfix = new Array(len + 1).fill(0);
    for (let n of nums) {
        prefix.push(n + prefix.at(-1));
    }
    for (let i = len - 1; i >= 0; i--) {
        postfix[i] = postfix[i + 1] + nums[i];
    }
    console.log("prefix: ", prefix);
    console.log("postfix: ", postfix);
    for (let i = 0; i < len; i++) {
        if (prefix[i] === postfix[i + 1]) return i;
    }
    return -1;
};