Leetcode 724: Find Pivot Index

Input: The input consists of an array of integers nums.

Example: nums = [5, 6, 4, 2]

Constraints:

• 1 <= nums.length <= 10^4

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

Output: The output is the leftmost pivot index where the sum of elements on the left equals the sum of elements on the right.

Example: Output: 1

Constraints:

• Return -1 if no pivot index exists.

Goal: Determine the index where the sum of the left side of the array equals the sum of the right side.

Steps:

• 1. Compute the total sum of the array.

• 2. Traverse the array, updating the left sum and comparing it to the right sum (initially the total sum).

• 3. If the left sum equals the right sum at any index, return that index.

• 4. If no such index exists, return -1.

Goal: Constraints are provided to define the input limits.

Steps:

• The length of the input array nums is between 1 and 10^4.

• Each element in nums is an integer between -1000 and 1000.

Assumptions:

• The input array will not be empty.

• The pivot index will be calculated by comparing sums of integers on both sides.

• Input: Input: [2, 4, 1, 3, 5]

• Explanation: The sum to the left of index 2 is 6 (2 + 4), and the sum to the right is 8 (3 + 5). Thus, the pivot index is 2.

Approach: The approach involves calculating the total sum and iterating through the array while maintaining running sums of the left and right sides.

Observations:

• We can use a running left sum and calculate the right sum by subtracting the current element from the total sum.

• If the left sum equals the right sum at any index, return that index. Otherwise, continue the search.

Steps:

• 1. Calculate the total sum of the array.

• 2. Iterate through the array while updating the left sum.

• 3. For each index, subtract the current element from the total sum to get the right sum.

• 4. Compare the left sum and the right sum, and return the index if they are equal.

Empty Inputs:

• Handle cases where the input array has only one element.

Large Inputs:

• Ensure the solution works efficiently for large arrays (up to 10^4 elements).

Special Values:

• Consider arrays with negative numbers or zeros.

Constraints:

• Handle arrays with both positive and negative values.

int pivotIndex(vector<int>& nums) {
    int left = 0;
    int right = accumulate(nums.begin(), nums.end(), 0);
    for(int i = 0; i < nums.size(); i++) {
        right -= nums[i];
        if(right == left) return i;
        left  += nums[i];
    }
    return -1;
}

1 : Function Definition

int pivotIndex(vector<int>& nums) {

Defines a function called pivotIndex that accepts a reference to a vector of integers.

2 : Variable Initialization

    int left = 0;

Initializes a variable 'left' to 0, representing the sum of elements to the left of the pivot.

3 : Variable Initialization

    int right = accumulate(nums.begin(), nums.end(), 0);

Initializes 'right' to the total sum of all elements in the vector 'nums'.

4 : Loop

    for(int i = 0; i < nums.size(); i++) {

Starts a loop that iterates through each element of the vector 'nums'.

5 : Operation

        right -= nums[i];

Subtracts the current element from the 'right' sum to exclude it from the right side of the pivot.

6 : Condition

        if(right == left) return i;

Checks if the sum of elements to the left is equal to the sum of elements to the right. If so, returns the index.

7 : Operation

        left  += nums[i];

Adds the current element to the 'left' sum to include it in the left side of the pivot.

8 : Return

    return -1;

Returns -1 if no pivot index is found.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear because we need to traverse the array once to compute the total sum and then once more to find the pivot index.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant, as we only use a few extra variables for sum calculations.

Leetcode 724: Find Pivot Index

Solution to LeetCode 724: Find Pivot Index Problem

Explore →