# Leetcode 239. Sliding Window Maximum [Hard]

Not so hard for people familiar with streaming processing: *You are given an array of integers **nums**, there is a sliding window of size **k**which is moving from the very left of the array to the very right. You can only see the **k** numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.*

**Input:** nums = [1,3,-1,-3,5,3,6,7], k = 3

**Output:** [3,3,5,5,6,7]

Solution is based on using Deque where we keep only indeces of elements that are max in given window and remove everything smaller on each iteration. Intuitive implementation is:

`class Solution {`

public int[] maxSlidingWindow(int[] nums, int k) {

if (nums.length * k == 0) return new int[0];

int l = 0, r = k-1;

int[] ans = new int[nums.length-k+1];

Deque<Integer> dq = new LinkedList<>(); // keep indeces

// create 1st window

for(int i = l; i <= r; i++) {

// remove what is smaller than index r

while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();

dq.offerLast(i);

}

ans[0] = nums[dq.peekFirst()];

l++; r++;

while(r<nums.length) {

// remove the left most element if available

while(!dq.isEmpty() && dq.peekFirst() < l) dq.pollFirst();

// remove what is smaller than index r

while(!dq.isEmpty() && nums[dq.peekLast()] < nums[r]) dq.pollLast();

dq.offerLast(r);

ans[l] = nums[dq.peekFirst()];

l++; r++;

}

return ans;

}

}

Each step can be visualized as: [l; r] -> [dequeue for this window]

`[0;2]: [1, 2]`

[1;3]: [1, 2, 3]

[2;4]: [4]

[3;5]: [4, 5]

[4;6]: [6]

[5;7]: [7]