Find Pivot Index problem results
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.
This problem is related to the running sum of 1d array.
First Blood
I used a silly brute force method but failed to be accepted. For each element in the vector, I calculated the left sum and right sum to check the equality.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
{
int pivotIndex(vector<int>& nums) {
int left_sum = 0;
int right_sum = 0;
for(int i = 0; i < nums.size(); i++)
{
//calculate left sum
for(int j = 0; j < i; j++)
{
left_sum += nums[j];
}
//calculate right sum
for(int k = i+1; k < nums.size(); k++)
{
right_sum += nums[k];
}
if(left_sum == right_sum)
{
return i;
}
left_sum = 0;
right_sum = 0;
}
return -1;
}
}
Double Kill
My second try was calculating the sum of the given array, for each element in the array, calculate the left sum, then right sum = sum - left_sum - nums[i]. This passed the test but still with a bad performance.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
{
int pivotIndex(vector<int>& nums) {
int left_sum = 0;
int right_sum = 0;
int sum = 0;
//calculate sum
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];
}
for(int i = 0; i < nums.size(); i++)
{
//calculate left sum
for(int j = 0; j < i; j++)
{
left_sum += nums[j];
}
right_sum = sum - left_sum - nums[i];
if(left_sum == right_sum)
{
return i;
}
left_sum = 0;
right_sum = 0;
}
return -1;
}
}
Triple Kill
After checking the Discussion, I got an acceptable submission. By calculating the left_sum as the running sum of the given array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
{
int pivotIndex(vector<int>& nums) {
int left_sum = 0;
int right_sum = 0;
int sum = 0;
//calculate sum
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];
}
for(int i = 0; i < nums.size(); i++)
{
right_sum = sum - left_sum - nums[i];
if(left_sum == right_sum)
{
return i;
}
//calculate running sum
left_sum += nums[i];
}
return -1;
}
}