724. Find Pivot Index

EasyArrayPrefix Sum
Leetcode Link

Problem Description

The problem presents an array of integers and asks us to find what is known as the pivot index. The pivot index is when the sum of the numbers to the left of that index is equal to the sum of the numbers to the right of it. The problem clarifies a couple of edge cases:

  • If the pivot index is at the very beginning of the array (index 0), the sum of the numbers to the left is considered to be 0 since there are no numbers left of it.
  • Likewise, if the pivot is at the very end of the array, the sum of the numbers to the right is 0 for similar reasons.

Our task is to return the leftmost pivot index. In other words, we're looking for the first position from the left where this balance occurs. If no such index can be found where the sums to the left and right are equal, we must return -1.

Intuition

The challenge is to find the pivot index without checking each possible index with brute force, which would be time-consuming for very large arrays. To make it more efficient, we can look for a way to find the balance as we go through the array just once.

To solve this problem, we need to track the sums of the numbers to the left and to the right of each index. An initial idea might be to calculate the sum of all numbers to the left and all those to the right for each index in the array. However, this would involve a lot of repeated work because we'd be summing over many of the same elements multiple times.

In the solution provided, we use a clever technique to avoid this repetition. We start by calculating the sum of the entire array and assign it to right. As we iterate over each element with the index i, we do the following:

  1. Subtract the current element's value from right because we're essentially moving our 'pivot point' one step to the right, so everything that was once to the right is now either the pivot or to its left except the current element.

  2. Check if the current sums to the left and to the right of i (not including i) are equal. If they are, i is our pivot index.

  3. If they're not equal, we add the current element's value to left because if we continue to the next element, our 'pivot point' will have moved, and the current element will now be considered part of the left sum.

By iterating over the array only once and updating left and right appropriately, we efficiently find the pivot index if it exists or determine that no pivot index is present.

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The implementation of the solution involves a single pass over the array, which makes use of two helpful constructs:

  1. Cumulative Sums: We don't calculate the sum on the fly for each pivot candidate; instead, we maintain a running total (left) that we build up as we iterate through the array.

  2. Total Sum: Before we start iterating, we calculate the total sum of the array (right). This sum represents everything that would initially be to the right of a hypothetical pivot at the start of the array.

Algorithmically, the steps are:

  • We initialize left to 0, since at the start of the array, there is nothing to the left.

  • We initialize right to the sum of all elements in nums using the sum function, representing the sum to the right of our starting index.

  • We then iterate over each element x of the array alongside its index i using Python's enumerate function, which gives us both the index and the value at that index in the array.

  • For each element x, we deduct x from right, which now represents the sum of elements to the right of our current index i.

  • We compare left and right; if they are equal, we've found a pivot index, and i is returned immediately.

  • If left does not equal right, we then add the value of x to left, preparing for the next iteration where i will be one index to the right.

  • If we complete the entire loop without finding equal left and right sums, which means there is no pivot index, we return -1.

Thus, the approach cleverly manages the sum totals on either side of the current index by simply moving the index from left to right through the array, updating the sums by adding or subtracting the current element as appropriate. It does not require additional data structures or complex patterns but uses arithmetic operations judiciously to keep track of potential pivot indices.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the array nums = [1, 7, 3, 6, 5, 6].

  1. Initial Setup: Start with left as 0 and right as the sum of the entire array, which is 1 + 7 + 3 + 6 + 5 + 6 = 28.

  2. First Iteration (i = 0):

    • We have nums[i] = 1, so update right to be the sum of numbers to the right of index 0.
      right = right - nums[i] = 28 - 1 = 27.

    • Compare left and right. Since left is 0 and right is 27, they are not equal, so index 0 is not a pivot.

    • Update left to include nums[i].
      left = left + nums[i] = 0 + 1 = 1.

  3. Second Iteration (i = 1):

    • nums[i] = 7, so update right to be the sum of numbers to the right of index 1.
      right = right - nums[i] = 27 - 7 = 20.

    • Compare left and right. left is 1 and right is 20, not equal, no pivot yet.

    • Update left to include nums[i].
      left = left + nums[i] = 1 + 7 = 8.

  4. Third Iteration (i = 2):

    • nums[i] = 3, adjust right.
      right = right - nums[i] = 20 - 3 = 17.

    • Compare left and right, left is 8 and right is 17, not equal.

    • Update left.
      left = left + nums[i] = 8 + 3 = 11.

  5. Fourth Iteration (i = 3):

    • nums[i] = 6, adjust right.
      right = right - nums[i] = 17 - 6 = 11.

    • Compare left and right. Here both are 11, so we found a pivot index i = 3.

Since we've found a pivot index, we would return it (3). If we hadn't found a pivot index at this point, we would've continued with the process for the rest of the array. If no pivot index was found after the last iteration, we'd return -1.

This example walk-through demonstrates how the approach scans through the array, updating the sums of values to the left and right of the current index, and checks equality at each step without needing to sum over large subarrays repeatedly.

Solution Implementation

1from typing import List
2
3class Solution:
4    def pivotIndex(self, nums: List[int]) -> int:
5        # Initialize the left sum and right sum.
6        # Right sum is the sum of all elements initially.
7        left_sum, right_sum = 0, sum(nums)
8      
9        # Iterate through the list
10        for index, element in enumerate(nums):
11            # Subtract the element from right sum as it will not be part of the right segment
12            right_sum -= element
13          
14            # If left sum and right sum are equal, the current index is the pivot
15            if left_sum == right_sum:
16                return index  # Return the pivot index
17          
18            # Add the element to left sum as it becomes part of the left segment
19            left_sum += element
20      
21        # If no pivot index is found, return -1.
22        return -1
23
1class Solution {
2    public int pivotIndex(int[] nums) {
3        // Initialize the sum of numbers to the left of the pivot to 0
4        int sumLeft = 0;
5      
6        // Calculate the total sum of the array elements
7        int totalSum = 0;
8        for (int num : nums) {
9            totalSum += num;
10        }
11      
12        // Iterate through the array to find the pivot index
13        for (int i = 0; i < nums.length; i++) {
14            // Right sum is total sum minus the current element
15            // since the current element is to be the pivot
16            int sumRight = totalSum - sumLeft - nums[i];
17          
18            // If the sum of numbers to the left of the pivot is equal to
19            // the sum of numbers to the right of the pivot, return current index
20            if (sumLeft == sumRight) {
21                return i;
22            }
23
24            // Update the sumLeft by adding the current element's value
25            sumLeft += nums[i];
26        }
27      
28        // If no pivot index is found, return -1
29        return -1;
30    }
31}
32
1#include <vector>
2#include <numeric> // Required for std::accumulate function
3
4class Solution {
5public:
6    // Function to find the pivot index of the array
7    int pivotIndex(vector<int>& nums) {
8        int sumLeft = 0; // Initialize sum of elements to the left of the pivot
9        // Compute the total sum of the array elements with std::accumulate
10        int sumRight = std::accumulate(nums.begin(), nums.end(), 0);
11
12        // Iterate over the array elements
13        for (int i = 0; i < nums.size(); ++i) {
14            sumRight -= nums[i]; // Subtract the current element from the right sum as it's under consideration
15
16            // If left sum is equal to right sum, the current index is the pivot index
17            if (sumLeft == sumRight) {
18                return i; // Return the current index as the pivot index
19            }
20
21            sumLeft += nums[i]; // Add the current element to the left sum before moving to the next element
22        }
23
24        return -1; // If no pivot index is found, return -1
25    }
26};
27
1// Function to find the pivot index of an array
2// The pivot index is where the sum of the numbers to the left of the index
3// is equal to the sum of the numbers to the right of the index
4function pivotIndex(nums: number[]): number {
5    let sumLeft = 0; // Initialize sum of elements to the left
6    let sumRight = nums.reduce((a, b) => a + b, 0); // Initialize sum of all elements
7
8    // Iterate through the array elements
9    for (let i = 0; i < nums.length; ++i) {
10        sumRight -= nums[i]; // Subtract the current element from the right sum
11
12        // Check if left sum and right sum are equal
13        if (sumLeft === sumRight) {
14            return i; // Return the current index as pivot index
15        }
16      
17        sumLeft += nums[i]; // Add the current element to the left sum
18    }
19
20    return -1; // If no pivot index is found, return -1
21}
22
Not Sure What to Study? Take the 2-min Quiz：

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of elements in the nums list. This is because we iterate over all elements of the array exactly once in a single loop to find the pivot index.

The space complexity of the code is O(1) since we use only a constant amount of extra space for the variables left, right, i, and x irrespective of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫