Simple DP with Explanation


  • 0

    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
    

  • 0
    S
    This post is deleted!

Log in to reply
 

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