How to Find Pivot Index of 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.

Example 1:
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.

Example 2:
Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

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

C++ Finding Pivot Index of Array Algorithm

We can compute the accumulated sums from both ends and store them in two arrays namely e.g. sum_left and sum_right. Both steps take O(N) in time and complexity. Then we need another O(N) step to go through N indices and find out if there is a index such that sum_left[i] = sum_right[i].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        vector<int> sum_left = nums, sum_right = nums;
        for (int i = 1; i < sum_left.size(); ++ i) {
            sum_left[i] += sum_left[i - 1];
        }
        for (int i = sum_right.size() - 2; i >= 0; -- i) {
            sum_right[i] += sum_right[i + 1];
        }
        for (int i = 0; i < nums.size(); ++ i) {
            if (sum_left[i] == sum_right[i]) {
                return i;
            }
        }
        return -1;            
    }
};

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        vector<int> sum_left = nums, sum_right = nums;
        for (int i = 1; i < sum_left.size(); ++ i) {
            sum_left[i] += sum_left[i - 1];
        }
        for (int i = sum_right.size() - 2; i >= 0; -- i) {
            sum_right[i] += sum_right[i + 1];
        }
        for (int i = 0; i < nums.size(); ++ i) {
            if (sum_left[i] == sum_right[i]) {
                return i;
            }
        }
        return -1;            
    }
};

The above implementation is straightforward, at the cost of two O(N) additional space which can be avoided if we go with the following approach: first we need O(N) time to compute the sum. Then, we need to store the current partial sum (prefix-sum) from the begining of the array. Then we can compute the sum from the end by using the math equation (sum – prefix_sum – current element).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        for (const auto &n: nums) sum += n;
        int psum = 0;
        for (int i = 0; i < nums.size(); ++ i) {
            if (sum - psum - nums[i] == psum) {
                return i;
            }
            psum += nums[i];            
        }
        return -1;
    }
};

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        for (const auto &n: nums) sum += n;
        int psum = 0;
        for (int i = 0; i < nums.size(); ++ i) {
            if (sum - psum - nums[i] == psum) {
                return i;
            }
            psum += nums[i];            
        }
        return -1;
    }
};

O(N) time complexity and O(1) space complexity.

–EOF (The Ultimate Computing & Technology Blog) —