Find Pivot Index

Introduction

Today, I tackled another intriguing problem from LeetCode 75: Find Pivot Index. This easy-level question requires an understanding of prefix sums and arrays. The goal is to 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. Let's dive into the problem statement, approach, and solution.

Problem Statement

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

Constraints:

• 1 <= nums.length <= 104

• -1000 <= nums[i] <= 1000

Approach to Solve the Problem

To solve this problem, we can use prefix sums to calculate the sum of elements to the left and right of each index. Here are the steps involved:

1. Initialize Arrays: Create two arrays, leftSum and rightSum, to store the sums of elements to the left and right of each index.

2. Calculate Prefix Sums: Iterate through the input array to fill leftSum and rightSum arrays.

3. Find Pivot Index: Iterate through the array and compare the values of leftSum and rightSum at each index to find the pivot index.

Solution

Here’s the Java code that implements the above approach:

public static int pivotIndex(int[] nums) {
    int n = nums.length;

    int [] leftSum = new int[n];
    int [] rightSum = new int[n];

    leftSum[0] = 0;
    rightSum[n-1] = 0;

    // storing the sums of left and right at each index
    for(int i = 1, j = n-2; i < n; i++, j--){
        leftSum[i] = leftSum[i-1] + nums[i-1];
        rightSum[j] = rightSum[j+1] + nums[j+1];
    }

    // checking at which index the sum is same
    for(int i = 0; i < n; i++){
        if(leftSum[i] == rightSum[i])
            return i;
    }


    return -1;
}

Explanation

1. Initialization: The leftSum and rightSum arrays are initialized to store the cumulative sums of elements to the left and right of each index.

2. Prefix Sum Calculation: The first loop fills the leftSum and rightSum arrays with the appropriate cumulative sums.

3. Finding the Pivot Index: The second loop iterates through the array to find the index where the left and right sums are equal.

Performance

This solution efficiently calculates the pivot index with a time complexity of O(n), where n is the length of the array. The use of prefix sums ensures that we only need to traverse the array a couple of times, making it both time and space efficient.

Conclusion

This problem is a great example of how prefix sums can be used to solve array-related problems efficiently. Understanding this technique is essential for tackling various other problems in competitive programming and real-world applications.

I hope you found this explanation helpful. Stay tuned for more daily blogs on interesting problems and concepts I encounter in my learning journey!