O(n) or O(n*k)??


  • 0
    M

    Below is my code and it performs pretty well...(Beats 98%) However I am a beginner in asymptotic analysis and I don't think it's an O(n) solution, especially when the input array is sorted in descending order. I think it's O(n*k). Am I wrong?

    
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length == 0) 
            		return new int[0];
            int[] res = new int[nums.length - k + 1];
            int max = Integer.MIN_VALUE;
            
            for(int i = 0; i < k; i++){
                if(nums[i] > max){
                    max = nums[i];
                }
            }
            
            for(int i = k; i < nums.length; i++){
                res[i - k] = max;
                if(nums[i] >= max){
                    max = nums[i];
                }
                else if(nums[i - k] == max){
                    max = Integer.MIN_VALUE;
                    for(int j = i - k + 1; j <= i; j++){
                        if(nums[j] >= max){
                            max = nums[j];
                        }
                    }
                }
            }
            
            res[res.length - 1] = max;
            
            return res;
        }
    

Log in to reply
 

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