Divide and conquer approach for O(n logn)


  • 0
    V
    ublic class Solution {
        private static int MAX = Integer.MAX_VALUE;
        public int minSubArrayLen(int s, int[] nums) {
            int[] prefixSums = new int[nums.length];
            for(int i = 1; i < prefixSums.length; i++) {
                prefixSums[i] = nums[i];
                if (i > 0) {
                    prefixSums[i] += prefixSums[i - 1];
                }
            }
            
            int minlen = minLen(nums, prefixSums, s, 0, nums.length - 1);
            return (minlen == MAX) ? 0 : minlen;
        }
        
        private int minLen(int[] A, int[] prefixSums, int sum, int start, int end) {
            if (end < start) return 0;
            
            if (start == end) {
                return (A[start] >= sum) ? 1 : MAX;
            }
            
            int mid = start + ((end - start) >> 1);
            int minlen = Math.min(minLen(A, prefixSums, sum, start, mid), minLen(A, prefixSums, sum, mid + 1, end)), i = start, j = mid + 1;
            while(i <= mid && j <= end) {
                while (i <= mid && A[i] + prefixSums[j] - prefixSums[i] >= sum) {
                    minlen = Math.min(minlen, j - i + 1);
                    i++;
                }
                j++;
            }
            
            return minlen;
        }
    }
    

Log in to reply
 

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