Java O(N) and O(NlogN) Solution with explanation


  • 0
    S

    There are lots of explanations for the following O(N) approach and I think the code is self-explanatory:

    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int lo=0, hi=0, sum=0, minLen=nums.length;
            boolean hasMin=false;
            while(hi<nums.length){
                while(sum<s&&hi<nums.length)
                    sum+=nums[hi++];
                while(sum-nums[lo]>=s)
                    sum-=nums[lo++];
                if(!hasMin&&sum>=s)     hasMin=true;
                minLen=Math.min(minLen, hi-lo);
                sum-=nums[lo++];
            }
            return hasMin? minLen:0;
        }
    }
    

    For the O(NlogN) approach, we have to use divide-and-conquer. Divide the array into 2 halves at the middle and exluding the middle element, the left subarray will have indices from 0 to middle-1, and the right subarray will have indices from middle+1 to nums.length-1.

    Now the mininum length can come from 3 places: 1) the left subarray 2) the right subarray and 3) the subarray which contains the middle element. For case 1) and 2), we can call recursively to get the min lengths. However, for 3), we need to apply the O(N) approach above (so the O(NlogN) approach is slower, uses more space and harder to code......) and make sure that we always include the middle element. The complexity is T(N)=2T(N/2)+O(N) so T(N)=O(NlogN). My O(NlogN) approach will lead to TLE for the largest test case, but I tested it myself using some small test cases. Let me know if you find any errors and thanks in advance.

    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int minLen=minSubArrayLen(s, nums, 0, nums.length-1);
            return minLen==Integer.MAX_VALUE? 0:minLen;
        }
        private int minSubArrayLen(int s, int[] nums, int lo, int hi){
            if(hi<lo||hi==lo&&nums[hi]<s)   return Integer.MAX_VALUE;
            if(hi==lo&&nums[hi]>=s) return 1;
            int mid=(lo+hi)/2;
            int left=minSubArrayLen(s, nums, lo, mid-1), right=minSubArrayLen(s, nums, mid+1, hi);
            int sum=nums[mid], start=mid, end=mid+1, minLen=Integer.MAX_VALUE;
            while(sum<s&&start>0)
                sum+=nums[--start];
            if(sum>=s)  minLen=Math.min(minLen, end-start);
            while(start<=mid){
                sum-=nums[start++];
                while(sum<s&&end<nums.length)
                    sum+=nums[end++];
                if(sum>=s)  minLen=Math.min(minLen, end-start);
            }
            return Math.min(minLen, Math.min(left, right));
        }
    }

  • 0
    J

    your code should be O(N*N), not the O(nlgn) because you always use the 0 and array size to get the min len, you should use the begin and end which is the half size


  • 0
    S

    Are you talking about getting the min length from case 3)? Yes, it takes O(N) time each recursion, but there are only O(logN) recursions.


  • 0
    J

    Yes, you are right, sorry for misunderstanding.


  • 0
    L

    Hey, did you Divide and conquer code work now ? My solution using divide and conquer failed this test case and maybe even more. Expected out put is 132, mine is 136. Smaller cases worked

    "697439, [5334,6299,4199,9663,8945,3566,9509,3124,6026,6250,7475,5420,9201,9501,38,5897,4411,6638,9845,161,9563,8854,3731,5564,5331,4294,3275,1972,1521,2377,3701,6462,6778,187,9778,758,550,7510,6225,8691,3666,4622,9722,8011,7247,575,5431,4777,4032,8682,5888,8047,3562,9462,6501,7855,505,4675,6973,493,1374,3227,1244,7364,2298,3244,8627,5102,6375,8653,1820,3857,7195,7830,4461,7821,5037,2918,4279,2791,1500,9858,6915,5156,970,1471,5296,1688,578,7266,4182,1430,4985,5730,7941,3880,607,8776,1348,2974,1094,6733,5177,4975,5421,8190,8255,9112,8651,2797,335,8677,3754,893,1818,8479,5875,1695,8295,7993,7037,8546,7906,4102,7279,1407,2462,4425,2148,2925,3903,5447,5893,3534,3663,8307,8679,8474,1202,3474,2961,1149,7451,4279,7875,5692,6186,8109,7763,7798,2250,2969,7974,9781,7741,4914,5446,1861,8914,2544,5683,8952,6745,4870,1848,7887,6448,7873,128,3281,794,1965,7036,8094,1211,9450,6981,4244,2418,8610,8681,2402,2904,7712,3252,5029,3004,5526,6965,8866,2764,600,631,9075,2631,3411,2737,2328,652,494,6556,9391,4517,8934,8892,4561,9331,1386,4636,9627,5435,9272,110,413,9706,5470,5008,1706,7045,9648,7505,6968,7509,3120,7869,6776,6434,7994,5441,288,492,1617,3274,7019,5575,6664,6056,7069,1996,9581,3103,9266,2554,7471,4251,4320,4749,649,2617,3018,4332,415,2243,1924,69,5902,3602,2925,6542,345,4657,9034,8977,6799,8397,1187,3678,4921,6518,851,6941,6920,259,4503,2637,7438,3893,5042,8552,6661,5043,9555,9095,4123,142,1446,8047,6234,1199,8848,5656,1910,3430,2843,8043,9156,7838,2332,9634,2410,2958,3431,4270,1420,4227,7712,6648,1607,1575,3741,1493,7770,3018,5398,6215,8601,6244,7551,2587,2254,3607,1147,5184,9173,8680,8610,1597,1763,7914,3441,7006,1318,7044,7267,8206,9684,4814,9748,4497,2239]"


  • 0
    S

    No, it still got TLE for the case in which s==120331635.


  • 0

    you miss a situation! For instance, the biggest number A is at place i, and the number on A's left is one bigger than A's right side. However, there is a second biggest number appear at A's right, which means the numbers at A's left is useless.


Log in to reply
 

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