Two AC solutions in Java with time complexity of N and NLogN with explanation


  • 98
    L
    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            return solveNLogN(s, nums);
        }
        
        private int solveN(int s, int[] nums) {
            int start = 0, end = 0, sum = 0, minLen = Integer.MAX_VALUE;
            while (end < nums.length) {
                while (end < nums.length && sum < s) sum += nums[end++];
                if (sum < s) break;
                while (start < end && sum >= s) sum -= nums[start++];
                if (end - start + 1 < minLen) minLen = end - start + 1;
            }
            return minLen == Integer.MAX_VALUE ? 0 : minLen;
        }
    
        private int solveNLogN(int s, int[] nums) {
            int[] sums = new int[nums.length + 1];
            for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1];
            int minLen = Integer.MAX_VALUE;
            for (int i = 0; i < sums.length; i++) {
                int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
                if (end == sums.length) break;
                if (end - i < minLen) minLen = end - i;
            }
            return minLen == Integer.MAX_VALUE ? 0 : minLen;
        }
        
        private int binarySearch(int lo, int hi, int key, int[] sums) {
            while (lo <= hi) {
               int mid = (lo + hi) / 2;
               if (sums[mid] >= key){
                   hi = mid - 1;
               } else {
                   lo = mid + 1;
               }
            }
            return lo;
        }
    }
    

    Since the given array contains only positive integers, the subarray sum can only increase by including more elements. Therefore, you don't have to include more elements once the current subarray already has a sum large enough. This gives the linear time complexity solution by maintaining a minimum window with a two indices.

    As to NLogN solution, logN immediately reminds you of binary search. In this case, you cannot sort as the current order actually matters. How does one get an ordered array then? Since all elements are positive, the cumulative sum must be strictly increasing. Then, a subarray sum can expressed as the difference between two cumulative sum. Hence, given a start index for the cumulative sum array, the other end index can be searched using binary search.


  • 0
    S

    a little bug in solveN() function if the input is 7 {2,5}, then it outputs 0 , but expected 2


  • 0
    P

    I think it would be better if whenever minLen reaches 1 just return immediately.


  • 0
    M
    This post is deleted!

  • 0
    D

    For solveN() method, if the input is (6, {2,3,1,7,1,5}) the result would be 1. But the answer should be 2. Is that a bug?


  • 6
    S
    public class Solution {
    
    public int minSubArrayLen(int s, int[] nums) {
        
        if (nums == null) return 0;
        
        int first = 0;
        int last = 0;
        int min = Integer.MAX_VALUE;
        int sum = 0;
        
        //find the shortest length subarray from last[0] to nums[last]
        while (last < nums.length){
            
            sum += nums[last++]; // this statement is processed only when sum is smaller then s.
            
            //first will never be greater than last here, since when first meet last-1 (since last is increased in the last step), sum will reach zero.
            while (sum >= s) {
                min = Math.min(min, last-first);
                sum -= nums[first++];
                if(sum == 0) return 1; //This means nums[first-1] = s, thus the shortest length is 1.
            }
    
        }
        return min == Integer.MAX_VALUE?  0 : min;
        
    }
    

    }

    I optimized the O(n) answer with fewer judgements.


  • 0
    H

    How can we say 2-pointer approach is a O(n) solution? Should it be O(2n) as each pointer will have to travel entire array? Or O(2n) equals to O(n) in Big-O notation?


  • 0
    Y

    Yes, O(2n)=O(n)...


  • 0
    O

    I think your o(n) solution has bug, what if nums = [1,2,1,4,1,1] and s = 7?


  • -13
    S

    Hey, I don't think initialize minLen to Integer.MAX_VALUE is safe. What if the input array is an all 1's array with length Integer.MAX_VALUE, and s is Integer.MAX_VALUE? The result should be Integer.MAX_VALUE, but you will return 0. One option is initialize minLen to some illegal value like -1.


  • 0
    E

    you can set a boolean value to identify it get the subarray or not


  • 0
    S

    This line: if(sum == 0) return 1; //This means nums[first-1] = s, thus the shortest length is 1.

    I think it means nums[first-1]>=s


  • 0
    S

    Ix223, thanks for the solution, one thing I wonder is that somehow I felt this line may 'over-shoot' your start idx by 1 in usual cases. Am I missing something? thanks!

    while (start < end && sum >= s) sum -= nums[start++];


  • -1
    H

    Test: nums = {4,-1,-1,-1,7}; s = 6;
    Should be: 1
    Output: 5


  • 0
    C

    Time limited exceeded using your NlogN solution.


  • 0

    @hui34 based on the statement of question, ONLY positive integers are allowed in the original nums.


  • 0
    C
    private static int minSubArrayLen1(int s, int[] nums) {
    	int[] sums = new int[nums.length + 1];
    	
    	for(int i = 1; i < sums.length; i++) {
    		sums[i] = sums[i - 1] + nums[i - 1];
    	}
    	int minLen = Integer.MAX_VALUE;
    	
    	for(int i = 0; i < sums.length; i++) {
    		int end = Arrays.binarySearch(sums,i + 1, sums.length, sums[i] + s);
    		if(end < 0) end = -(end + 1);
    		if(end == sums.length) break;
    		if(end - i < minLen) minLen = end - i;
    		
    	}
    	
    	return minLen == Integer.MAX_VALUE ? 0 : minLen;
    	
    }

  • 0
    C

    In the solveNLogN part:

    for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1];

    the complexity of this part is : O(n);

    for (int i = 0; i < sums.length; i++) {
    int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);

    here is O(n log n),

    then total complexity is: O(n) + O(n log n) ?

    Actually, solveN solution can beat 17%, solveNLogN only can beat 8.17%, one case is time out.


  • 0
    G

    In our Algorithms course, we have been taught that these kinda problems are "incomplete solutions", which means like DP but simpler than DP. Because of the condition that we want the min length of contiguous subarray so that we dare to always move forward and never look back.


  • 0
    Y

    @lx223 Thanks! Very nice explanation.


Log in to reply
 

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