724. Find Pivot Index

[songyy5517]

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.

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Intuition This problem is to find an element in the array which can seperate the entire array into two parts and keep the sum of these two parts equal. A straightforward idea is that we can see the total sum of the raw array as three parts: [left_sum, nums[i], right_sum]. Therefore, we have right_sum = total_sum - nums[i] - left_sum. Loop through the array, and take each element as the pivot element, we need to determine whether left_sum == right_sum = total_sum - nums[i] - left_sum. If yes, then return the current index; return -1 otherwise.

[songyy5517]

Approach: Prefix Sum

1. Exception handling;
2. Define variables:
   • left_sum = 0: the sum of the current left part;
   • total_sum = sum[0:len-1]: the total sum of the whole array.
3. Iterate over the array, and take each element as the pivot index: （1）Deternmine whether left_sum == right_sum = total_sum - nums[i] - left_sum, if so, return the current index; （2）Update the sum of the left part left_sum += nums[i];
4. No such index, return -1.

Complexity Analysis

• Time complexity: $O(N)$ , looping through the array costs $O(N)$ time;
• Space complexity: $O(1)$ , additionally define constant-level variables.

[songyy5517]

class Solution {
    public int pivotIndex(int[] nums) {
        // Intuition: Prefix sum.
        // 1. Exception handling
        if (nums == null || nums.length == 0)
            return -1;

        // 2. Define variables
        int left_sum  = 0;
        int total_sum = 0;
        for (int num : nums)
            total_sum += num;

        // 3. Loop through the array to find the pivot index
        for (int i = 0; i < nums.length; i++){
            if (left_sum == total_sum - nums[i] - left_sum)
                return i;

            left_sum += nums[i];
        }

        return -1;
    }
}

[songyy5517]

2024/5/15