O(kn) solution w/ O(1) space complexity


  • 0
    S

    Iterate the array twice while dynamically update the index of the max element inside current window.

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

  • 0

    That's quite clearly not O(n) but O(nk).


  • 0
    S

    Yeah.. I think you are right. But the inner loop is not always executed fully, especially when the new element is the biggest one in the sliding window.


  • 0

    But it can be executed fully every time, just takes a decreasing input.


Log in to reply
 

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