O(nlogn) solution that I've not seen here.. with some explanation


  • 0
    K

    The idea is to find the size of subarray using binary search and a func to check for subarray of constant size.

    bool check(int s, vector<int>& a, int n){ // true if there is subarray of size 'n' and sum >= s
        int sum(0);
        if(n < 1)return false;
        for(int i = 0; i< a.size(); i++){
            
            if(sum >= s) return true;
            sum += a[i];
            if(i >= n) sum -= a[i - n];
        }
        return sum  >= s;
    }
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
        
        if(nums.size() < 1) return 0;
        int left(0), right = nums.size()-1,mid(0),prev = -1;
        
        while(true){
            mid = (right + left)/2;
            
            if(check(s, nums,mid)){
                right = mid;
            } else {
                left = mid + 1;
            }
            if(mid == prev)break;
            prev = mid;
            
        }
        
        if( check(s, nums, mid )) return mid;
        return 0;
    }

Log in to reply
 

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