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

• 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;
}

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

• 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.

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

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