# Simple DP with Explanation

• Pre-calculate the `sums` from left-to-right at each index, then iterate through those pre-calculated `sums` from left-to-right trying to find the pivot. Return the pivot index `i` if found, `-1` otherwise.

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

Note: one of the "trickiest" parts of this solution is that `i` is used differently between the vectors `nums` and `sums`.

Use case example:

``````      i =  0  1  2  3  4  5
nums = [   1, 7, 3, 6, 5, 6]

i =  0  1  2  3  4  5  6
sums = [0, 1, 8,11,17,22,28]
``````

For above use case example, the pivot index is found when `i=3`:
`sum[3]=11`, `sum[4]=17`. `n=6`, so `sum[6]=28`. And `11+17=28`.

Note: another "tricky" part of this solution is the calculation of the `sums` at each index `i`. Let's walk through it from left-to-right for the above use case example for each `sum[i]`:

``````sum[0]=0
sum[1]=sum[0]+nums[0]= 0+1= 1
sum[2]=sum[1]+nums[1]= 1+7= 8
sum[3]=sum[2]+nums[2]= 8+3=11
sum[4]=sum[3]+nums[3]=11+6=17
sum[5]=sum[4]+nums[4]=17+5=22
sum[6]=sum[5]+nums[5]=22+6=28
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.