What's the time complexity of this algorithm?


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

    This is O(N) or O(N * N)?


  • 0
    H

    The complexity is O(N) , and more precisely it's 2N since both i and j are increasing and not coming back.
    If the j in the while loop restarts as the current value of i, then it's O(N^2) where you are doing an exhaustive search(i.e. search all possible "intervals).


Log in to reply
 

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