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.

LeetCode

• https://leetcode.com/problems/find-pivot-index/description/
• https://leetcode.com/problems/find-the-middle-index-in-array/description/

Constraints

1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000

Examples

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

Different Approaches

1️⃣ Brute Force Approach

Intuition:

For each index, compute:

• sum of elements to the left
• sum of elements to the right

If they are equal, return the index

for (int i = 0; i < n; i++) {
    leftSum = sum of elements from 0 to i-1
    rightSum = sum of elements from i+1 to n-1
    if (leftSum == rightSum) return i;
}

Code:

#include <vector>
using namespace std;

int pivotIndex(vector<int>& nums) {
    int n = nums.size();

    for (int i = 0; i < n; ++i) {
        int leftSum = 0;
        int rightSum = 0;

        // Calculate the sum of elements to the left of index i
        for (int j = 0; j < i; ++j) {
            leftSum += nums[j];
        }

        // Calculate the sum of elements to the right of index i
        for (int j = i + 1; j < n; ++j) {
            rightSum += nums[j];
        }

        // If left sum and right sum are equal, return i
        if (leftSum == rightSum) {
            return i;
        }
    }

    // No pivot index found
    return -1;
}

Complexity Analysis:

• Time Complexity:O(n^2)
  • Because of two nested loops. For each index, we calculate the left and right sums, which requires iterating over the array. This results in a quadratic time complexity.
• Space Complexity:O(1)
  • We are using only a few extra variables for sum calculations.

 2️⃣ Prefix Sum (Optimized)

Intuition:

Instead of recalculating the left and right sums multiple times, we can precompute the total sum of the array. As we iterate through the array, we can keep a running sum of elements to the left of the current index, and the sum to the right can be derived from the total sum and the left sum.

Let total = sum(nums).

Traverse array once while maintaining leftSum.

At index i, right sum is total - leftSum - nums[i]

If leftSum == rightSum, return i.

Approach:

1. Compute the total sum of the array.
2. As you iterate through the array, keep a running sum of elements to the left of the current index.
3. For each index i, calculate the right sum as total_sum - left_sum - nums[i].
4. If the left sum equals the right sum, return i as the pivot index.
5. If no pivot index is found, return -1.

Code:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        // Step 1: Calculate the total sum of all elements in the array
        int totalSum = 0;
        for (int elm : nums) {
            totalSum += elm;
        }

        // Step 2: Initialize leftSum to 0
        // This will keep track of the sum of elements to the left of the current index
        int leftSum = 0;
        int n = nums.size();

        // Step 3: Traverse the array to find the pivot index
        for (int i = 0; i < n; i++) {
            // Calculate the right sum using:
            // totalSum - leftSum - nums[i]
            // Because: rightSum = totalSum - leftSum - current element
            int rightSum = totalSum - leftSum - nums[i];

            // Step 4: If left sum equals right sum, we found the pivot index
            if (leftSum == rightSum) {
                return i;
            }

            // Step 5: Add the current element to leftSum before moving to the next index
            leftSum += nums[i];
        }

        // Step 6: If no pivot index is found, return -1
        return -1;
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • We calculate the total sum in one pass and then iterate through the array once more to find the pivot index
• Space Complexity:O(1)
  • Only a few extra variables are used (left sum and total sum).

3️⃣ Prefix Array

We can also precompute prefix sums (array of size n) and compare at each point.

Code:

int pivotIndex(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n, 0);

    // Step 1: Build prefix sum array where prefix[i] = sum of nums[0...i]
    prefix[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + nums[i];
    }

    // Step 2: Traverse the array and check for pivot index
    for (int i = 0; i < n; ++i) {
        int leftSum = (i == 0) ? 0 : prefix[i - 1];
        int rightSum = prefix[n - 1] - prefix[i];
        if (leftSum == rightSum) return i;
    }

    return -1;
}

Complexity Analysis:

• Time Complexity:O(n)
  • O(n): for building prefix array
  • O(n): for finding pivot index
• Space Complexity:O(n)
  • For prefix array