Simple O(n) time ,space O(1) java solution using DP.


  • 0
    E

    For anyone who wants to practice DP.
    Let's say the input is [1, 7, 3, 6, 5, 6] we want to store the results of the sum starting from the left to dp and the result starting from the right to dp1.
    The first for loop compute the sum to both our dp arrays.

    dp starts with [0,1] where 1 is the element at index 0. Then compute the remaining sum using the previous results stored in the dp array. At then end the content of dp is
    [0, 1, 8, 11, 17, 22, 28]
    Similarly, the loop will also compute dp1 just like that of dp and here is the content of dp1 using the above example
    [28, 27, 20, 17, 11, 6, 0]
    Now that we have the dp arrays then it's easy to accomplish the task.
    Loop and check if dp[i-1] == dp1[i] if so return i-1;

         public int pivotIndex(int[] nums) {
           int len = nums.length;
         if(len ==0) return -1;
            int[] dp = new int[len+1];
            int[] dp1 = new int[len+1];
             dp[0] =0;  //to handle edge cases
             dp1[len] = 0;
             dp[1] = nums[0];
             dp1[len-1] = nums[len-1];
        for(int i=2,j=len-2; i<=len; i++,j--){
            dp[i] = dp[i-1]+nums[i-1];
            dp1[j] = dp1[j+1]+nums[j];
        }
        for(int i=1; i<=len; i++){
                if(dp[i-1]==dp1[i]) return i-1;
        }
        
        return -1;
    }

Log in to reply
 

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