Simple to Understand -- Java Brute Force + DP Solution


  • 0
    S

    Brute Force O(n^2):
    For each index i, we compute the left_sum and right_sum and check if they are equal. If they are equal, we return i, otherwise we keep iterating.

    class Solution {
        public int pivotIndex(int[] nums) {
            if(nums == null || nums.length == 0)
                    return -1;
            for(int i = 0; i < nums.length; i++) {
                long sum_left = 0;
                long sum_right = 0;
                for(int j = 0; j < i; j++) {
                    sum_left += nums[j];
                }
                for(int j = i + 1; j < nums.length; j++) {
                    sum_right += nums[j];
                }
                if(sum_left == sum_right) return i;
                
            }
            return -1;
        }
    }
    

    Dynamic Programming O(n):
    Since we need to compute the left sum and right sum for each index, you notice that it is wasteful to compute it on each iteration. You notice that there is a lot of overlap in left_sum from i to i+1. The left_sum[i] = left_sum[i-1] + nums[i] and right_sum[i] = right_sum[i+1] + nums[i]. So you just need to create left_sum and right_sum arrays ahead of time and then you can use their values to get the left and right sum of any index in O(1).

    Code is a bit more verbose, but solves the problem well :)

    class Solution {
        public int pivotIndex(int[] nums) {
            if(nums == null || nums.length == 0){
                return -1;
            }
            if(nums.length == 1){
                return 0;
            }
            
            int len = nums.length;
            int[] left_sum = new int[len];
            int[] right_sum = new int[len];
            
            left_sum[0] = nums[0];
            right_sum[len-1] = nums[len-1];
            
            for(int i = 1; i < len; i++){
                left_sum[i] = nums[i] + left_sum[i-1];
            }
            
            for(int i = len-2; i >= 0; i--){
                right_sum[i] = nums[i] + right_sum[i+1];
            }
            
            if(right_sum[1] == 0){
                return 0;
            }
            
            for(int i = 1; i < len-1; i++){
                if(left_sum[i-1] == right_sum[i+1]){
                    return i;
                }
            }
            
            if(left_sum[len-2] == 0){
                return len-1;
            }
            return -1;
        }
    }
    

Log in to reply
 

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