What is wrong with this Divide and Conquer Solution?


  • 0
    B
    public static int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int result = helper(s, nums);
        return result == Integer.MAX_VALUE ? 0 : result;
    }
    
    private static int helper(int s, int[] nums) {
        if (nums.length == 1) {
            return nums[0] >= s ? 1 : Integer.MAX_VALUE;
        }
        int mid = nums.length/2;
        int[] left = new int[mid];
        int[] right = new int[nums.length-mid];
        for (int i = 0; i < mid; i++) {
            left[i] = nums[i];
        }
        for (int i = mid; i < nums.length; i++) {
            right[i-mid] = nums[i];
        }
        int leftResult = helper(s, left);
        int rightResult = helper(s, right);
        int mergeResult = merge(s, left, right);
        return Math.min(leftResult, Math.min(rightResult, mergeResult));
    }
    
    private static int merge(int s, int[] left, int[] right) {
        int l = left.length-1;
        int r = 0;
        int sum = 0;
        int count = 0;
        while (l >= 0 && r < right.length) {
            if (left[l] > right[r]) {
                sum += left[l];
                l--;
            } else {
                sum += right[r];
                r++;
            }
            count++;
            if (sum >= s) {
                return count;
            }
        }
        while (l >= 0) {
            sum += left[l];
            l--;
            count++;
            if (sum >= s) {
                return count;
            }
        }
        while (r < right.length) {
            sum += right[r];
            r++;
            count++;
            if (sum >= s) {
                return count;
            }
        }
        return Integer.MAX_VALUE;
    }

  • 0
    B

    I can't seem to figure out what is wrong with my solution (n log n). I output 136, but the correct answer is 132. Any help would be appreciated. Thanks!

    Output:
    136
    Expected:
    132


Log in to reply
 

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