Find Pivot Index ( Equilibrium index of an array )

Given an array of integers nums, write a method that returns the "pivot" index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Input: nums = [1, 7, 3, 6, 5, 6] Output: 3 Explanation: The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3. Also, 3 is the first index where this occurs.

Method 1: Using two for loop

Using two hash map to store the left sum and right sum for all indexes.

int pivotIndex(vector<int>& nums) {
    unordered_map<int, int> leftSum;
    unordered_map<int, int> rightSum;

    int temp = 0;
    for(int i=0; i<nums.size(); i++) {
        leftSum[i] = temp;
        temp += nums[i];
    }

    temp = 0;
    for(int j=nums.size()-1; j>=0; j--) {
        rightSum[j] = temp;
        temp += nums[j];
    }

    for(int i=0; i<nums.size(); i++) {
        if(leftSum[i] == rightSum[i]) return i;
    }

    return -1;
}

Method 2: Using total sum

The idea is to get total sum of array first. Then Iterate through the array and keep updating the left sum which is initialized as zero. In the loop, we can get right sum by subtracting the elements one by one.

int pivotIndex(vector<int>& nums) {
    int sum = 0;
    for (auto num: nums) sum += num;

    int temp = 0;
    for(int i=0; i<nums.size(); i++) {
        sum -= nums[i];
        if(temp == sum) return i;
        temp += nums[i];
    }

    return -1;
}