algoadvance

Leetcode 724. Find Pivot Index

Problem Statement

The problem is to find the pivot index of an array. The pivot index is defined as an index i such that the sum of the elements to the left of i is equal to the sum of the elements to the right of i. If no such index exists, return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example:

Note:

  1. The length of nums will be in the range [0, 10000].
  2. Each element nums[i] will be an integer in the range [-1000, 1000].

Clarifying Questions

  1. Can the array be empty?
    • Yes, if the array is empty, we should return -1.
  2. If there are multiple valid pivot indexes, should we return the smallest index?
    • Yes, we should return the left-most pivot index.

Strategy

  1. Calculate the total sum of the array: This will help us to avoid calculating the right sum repetitively.
  2. Iterate through the array: Maintain a running sum of elements on the left side of the current index. The right sum can be computed as totalSum - leftSum - nums[i].
  3. Check the condition: At each index i, check if the left sum equals the right sum.
  4. Return the index if such a pivot exists; otherwise, return -1 after the loop.

Code

Here’s the implementation in C++:

#include <vector>
#include <numeric> // for std::accumulate

class Solution {
public:
    int pivotIndex(std::vector<int>& nums) {
        int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
        int leftSum = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        
        return -1;
    }
};

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of elements in the input array nums. This is because we traverse the array twice (once for calculating totalSum and once for finding the pivot index). The space complexity is O(1) since we are using a fixed amount of extra space.

This approach efficiently finds the pivot index, leveraging a single scan of the array to check each candidate index while maintaining a running sum of the left-hand side.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI