Find Pivot Index: a linear solution
Another LeetCode, right here: https://leetcode.com/problems/find-pivot-index/description/
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].
The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].
Given the length of nums as 10000, an N^2 solution becomes a little too much (100,000,000). It will work, but painfully so. There is a better approach if we're willing to use some extra memory:
- Have 2 extra arrays, with the same length
- One of the arrays will keep track of the sum of the elements from 0..i. I call it SumLeft
- The other one will keep track of the sum of the elements from i..N-1. I call it SumRight
- Do another final run checking whether SumLeft[i] == SumRight[i]
Due to (1) we know this will be an O(N)-space algorithm. (2) takes 1N. So does (3). And so does (4), for a grand total of O(3N)-time, also known as O(N)-time. For an N=10000, 3N will fly fast. Code is down below, many cheers and hugs! Marcelo
public class Solution
{
public int PivotIndex(int[] nums)
{
if (nums == null || nums.Length == 0) return -1;
int[] sumLeft = new int[nums.Length];
int[] sumRight = new int[nums.Length];
sumLeft[0] = nums[0];
for (int i = 1; i < nums.Length; i++)
sumLeft[i] = sumLeft[i - 1] + nums[i];
sumRight[nums.Length - 1] = nums[nums.Length - 1];
for (int i = nums.Length - 2; i >= 0; i--)
sumRight[i] = sumRight[i + 1] + nums[i];
for (int i = 0; i < nums.Length; i++)
if (sumLeft[i] == sumRight[i]) return i;
return -1;
}
}
You can avoid an extra pass by exploiting a fact that sumRight[i] = totalSum - sumLeft[i] + nums[i]. You can also use a constant space since at any point of time you only need a single value of sumLeft[i], so you can replace it with a running sum. After these simple optimizations we get O(N) time and O(1) space complexity with:
ReplyDeleteclass Solution {
public:
int pivotIndex(const vector& nums) {
int sum = accumulate(nums.cbegin(), nums.cend(), 0);
int runningSum = 0;
for (int i = 0; i < nums.size(); runningSum += nums[i], i += 1) {
if (runningSum * 2 == sum - nums[i]) {
return i;
}
}
return -1;
}
};
a slightly more compact version, since Blogger hates code:
Deleteclass Solution {
public:
int pivotIndex(const vector& nums) {
int sum = accumulate(nums.cbegin(), nums.cend(), 0);
for (int i = 0, runningSum = 0; i < nums.size(); runningSum += nums[i], i += 1) {
if (runningSum * 2 == sum - nums[i]) return i;
}
return -1;
}
};