O(N),O(NLogN) solutions, both O(1) space


  • 67
    C

    O(N) - keep a moving window expand until sum>=s, then shrink util sum<s. Each time after shrinking, update length. (similar to other solutions, just removed unnecessary min value assignment)

    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
            while (j < nums.length) {
                while (sum < s && j < nums.length) sum += nums[j++];
                if(sum>=s){
                    while (sum >= s && i < j) sum -= nums[i++];
                    min = Math.min(min, j - i + 1);
                }
            }
            return min == Integer.MAX_VALUE ? 0 : min;
        }
    }
    

    O(NLogN) - search if a window of size k exists that satisfy the condition

    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int i = 1, j = nums.length, min = 0;
            while (i <= j) {
                int mid = (i + j) / 2;
                if (windowExist(mid, nums, s)) {
                    j = mid - 1;
                    min = mid;
                } else i = mid + 1;
            }
            return min;
        }
    
    
        private boolean windowExist(int size, int[] nums, int s) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i >= size) sum -= nums[i - size];
                sum += nums[i];
                if (sum >= s) return true;
            }
            return false;
        }
    }
    

    Another O(NLogN) solution that first calculate cumulative sum and then for each starting point binary search for end position. This uses O(N) space

    public class Solution {
     public int minSubArrayLen(int s, int[] nums) {
            int sum = 0, min = Integer.MAX_VALUE;
    
            int[] sums = new int[nums.length];
            for (int i = 0; i < nums.length; i++)
                sums[i] = nums[i] + (i == 0 ? 0 : sums[i - 1]);
    
            for (int i = 0; i < nums.length; i++) {
                int j = findWindowEnd(i, sums, s);
                if (j == nums.length) break;
                min = Math.min(j - i + 1, min);
            }
            
            return min == Integer.MAX_VALUE ? 0 : min;
        }
    
        private int findWindowEnd(int start, int[] sums, int s) {
            int i = start, j = sums.length - 1, offset = start == 0 ? 0 : sums[start - 1];
            while (i <= j) {
                int m = (i + j) / 2;
                int sum = sums[m] - offset;
            if (sum >= s) j = m - 1;
            else i = m + 1;
        }
        return i;
    }
    

    }


  • 0

    Excellent answer! Thanks you for sharing!


  • 0
    D

    the 2nd O(N*lgN) is innovative!


  • 0
    Z

    Amazing, are you binary search the size of the window? It's really a out of the box idea!


  • 0
    W

    @crackAlgo The two pointer solution : while (sum < s && j < nums.length) this can be removed


  • 0
    Y

    @crackAlgo the second solution is not O(NlogN); it need visit from 1 to n, and find the sum great than s is not constant value. (depends on the min length).


  • 0

    I love your second solution! I rewrite it in C++:

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int left = 1, right = nums.size(), min_len = 0;
            while(left <= right) {
                int mid = left + (right - left) / 2;
                // if the current window size satisfy, we can try to find smaller window size;
                if(windowExist(mid, nums, s)) {
                    right = mid - 1;
                    min_len = mid;
                }
                else {
                    left = mid + 1;
                }
            }
            return min_len;
        }
        
        bool windowExist(int size, vector<int>& nums, int s) {
            int sum = 0;
            for(int i = 0; i < nums.size(); ++i) {
                if(i >= size) sum -= nums[i - size];
                sum += nums[i];
                if(sum >= s) return true;
            }
            return false;
        }
    };
    

  • 0

    Very nice O(NlogN) solution. Learned a lot! Thanks!


  • 0
    H

    I think the third version is more efficient in time since it utilize more space compared to version 2 which is O(1) space. Essentially, they are the "same", we are just changing the order of two loops. Anyway, as a practice, the following is a c++ implementation. I like to use left < right in while-loop. Finally, just test whether the last number we found is valid or not.

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int left = 1, right = nums.size();
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (existWindow(nums, mid, s)) right = mid;
                else left = mid + 1;
            }
            return existWindow(nums, right, s) ? right : 0;
        }
        bool existWindow(vector<int> &nums, int size, int s) {
            int sum = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (i >= size) sum -= nums[i-size];
                sum += nums[i];
                if (sum >= s) return true;
            }
            return false;
        }
    };
    

Log in to reply
 

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