## Problem Statement

Given an array of integers A. 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 **w** numbers in the window. Each time the sliding window moves rightwards by one position. You have to find the maximum for each window.

Return an array C, where C[i] is the maximum value from **A[i]** to **A[i+K-1]**.

Note: If **k > length** of the array, return **1** element with the max of the array.

**Examples:****Input: **A[] = {1, 3, -1, -3, 5, 3, 6, 7}, K = 3**Output: **{3, 3, 5, 5, 6, 7}**Explanation:**

Window position | Max |

[1 3 -1] -3 5 3 6 7 | 3 |

1 [3 -1 -3] 5 3 6 7 | 3 |

1 3 [-1 -3 5] 3 6 7 | 5 |

1 3 -1 [-3 5 3] 6 7 | 5 |

1 3 -1 -3 [5 3 6] 7 | 6 |

1 3 -1 -3 5 [3 6 7] | 7 |

**Input: **A[] = {1, -1}, k = 1**Output:** {1, -1}

## Brute Force Approach

The simplest approach to solve this problem is to iterate over all possible sliding windows and find the maximum for each window.

There can be a total of N – K + 1 sliding window and there are **K** elements in each window.

**Algorithm:**

- Run a loop
**i**from**0**to**N – K + 1**, denoting the current window. - Initialise a variable
**max**to**INT_MIN**to find the maximum value of each window. - Run a nested loop from
**j**from**i**to**i + K**to iterate over the elements of the current window and maximize**max**. - Store the value of
**max**for each window and return.

### C++ Implementation

vector<int> SlidingWindowMaximum(int A[], int n, int K) { if (n * K == 0){ return {}; } vector<int> output(n - K + 1, 0); for (int i = 0; i < n - K + 1; i++) { int max = INT_MIN; for(int j = i; j < i + K; j++) max = max(max, A[j]); output[i] = max; } return output; }

### Java Implementation

public int[] SlidingWindowMaximum(int[] A, int K) { int n = nums.length; if (n * K == 0) return new int[0]; int [] output = new int[n - K + 1]; for (int i = 0; i < n - K + 1; i++) { int max = Integer.MIN_VALUE; for(int j = i; j < i + K; j++) max = Math.max(max, A[j]); output[i] = max; } return output; }

### Python Implementation

def SlidingWindowMaximum(A, K): n = len(nums) if n * K == 0: return [] return [max(A[i:i + K]) for i in range(n - K + 1)]

**Time Complexity:**O(N * K) where N is the size of the array **A[]**.**Space Complexity:**O(N – K + 1), as extra space is used.

## Efficient Approach: Using Deque

The previous approach takes O(N * K) time, which would give a Time Limit Exceeded error for large values of **K.**

One of the ideas to reduce the time complexity could be to use a max heap, since the maximum element is always present at the top of the heap, but an insertion in a **max heap **of size **K **takes O(log K) time. Therefore, the time complexity becomes O(N log K), which is efficient. Can we reduce it further?

The idea is to use a **deque** i.e. **double ended queue** which performs the **push()** and **pop()** operations in **O(1)** **constant **time.

**Algorithm: **

- Initialise the first
**K**elements of the array into the**deque.** - Iterate over the input array and for each step:
- Consider only the indices of the elements in the current window.
- Pop-out all the indices of elements smaller than the current element, since their value will be less than the current element.
- Push the current element into the deque.
- Push the first element of the deque i.e.
**deque[0]**into the output array.

### C++ Code for Deque Method

vector<int> SlidingWindowMaximum(vector<int>& A, int K) { deque<int> dq; vector<int> ans; for (int i=0; i<nums.size(); i++) { if (!dq.empty() && dq.front() == i-K) dq.pop_front(); while (!dq.empty() && A[dq.back()] < A[i]) dq.pop_back(); dq.push_back(i); if (i>=K-1) ans.push_back(nums[dq.front()]); } return ans; }

### Java Code for Deque Method

ArrayDeque<Integer> deq = new ArrayDeque<Integer>(); int [] A; public void clean_deque(int i, int K) { if (!deq.isEmpty() && deq.getFirst() == i - K) deq.removeFirst(); while (!deq.isEmpty() && nums[i] > A[deq.getLast()]){ deq.removeLast(); } } public int[] SlidingWindowMaximum(int[] A, int K) { int n = A.length; if (n * B=K == 0) return new int[0]; if (K == 1) return A; this.A = A; int max_idx = 0; for (int i = 0; i < K; i++) { clean_deque(i, K); deq.addLast(i); if (A[i] > A[max_idx]) max_idx = i; } int [] output = new int[n - K + 1]; output[0] = A[max_idx]; for (int i = K; i < n; i++) { clean_deque(i, K); deq.addLast(i); output[i - K + 1] = A[deq.getFirst()]; } return output; }

### Python Code for Deque Method

from collections import deque def SlidingWindowMaximum(A, K): n = len(A) if n * K == 0: return [] if K == 1: return A def clean_deque(i): if deq and deq[0] == i - K: deq.popleft() while deq and A[i] > A[deq[-1]]: deq.pop() deq = deque() max_idx = 0 for i in range(B): clean_deque(i) deq.append(i) if A[i] > A[max_idx]: max_idx = i output = [A[max_idx]] for i in range(K, n): clean_deque(i) deq.append(i) output.append(A[deq[0]]) return output

**Time Complexity:**O(N) where N is the size of the array **A[]**.**Space Complexity:**O(N), as extra space is used.

## Dynamic Programming Approach

The problem can be solved using **Dynamic Programming**. The approach is to divide the given array into different blocks each containing **K** elements. Let us understand the illustration with the below example.

**A[]** = {1, 3, -1, -3, 5, 3, 6, 7}**K** = 3

The given array has been divided into parts, each containing **K **elements. SInce, the size of the array is not divisible by **K**, the last block contains elements less than **K**.

Two elements can be placed into two different sliding windows, while iterating as follows:

To solve **problem** **1**, consider an auxiliary array **left[]** which denotes the maximum element obtained so far until index **j**.

Similarly to solve **problem 2**, consider an auxiliary array **right[]** which denotes the maximum element obtained so far until index **j**.

Now, since we have obtained all the maximum integers uptil **index i** from both directions, the maximum element in the sliding window from **index i **to **index j** is **max(left[i], right[i]).**

**Algorithm:**

- Construct an array
**left[]**, which contains the maximum element till index**i**iterating from**left**to**right.** - Construct an array
**right[]**, which contains the maximum element till index**i**iterating from**right**to**left.** - For each window size of
**N – K + 1**, the maximum element will be**max(left[i], right[N – i + 1])**.

### C++ Code for DP Approach

vector<int> SlidingWindowMaximum(vector<int>& A, int K) { deque<int> dq; vector<int> ans; for (int i=0; i<nums.size(); i++) { if (!dq.empty() && dq.front() == i-K) dq.pop_front(); while (!dq.empty() && A[dq.back()] < A[i]) dq.pop_back(); dq.push_back(i); if (i>=K-1) ans.push_back(nums[dq.front()]); } return ans; }

### Java Code for DP Approach

public int[] SlidingWindowMaximum(int[] A, int K) { int n = A.length; if (n * K == 0) return new int[0]; if (K == 1) return nums; int [] left = new int[n]; left[0] = nums[0]; int [] right = new int[n]; right[n - 1] = nums[n - 1]; for (int i = 1; i < n; i++) { if (i % K == 0) left[i] = nums[i]; else left[i] = Math.max(left[i - 1], A[i]); int j = n - i - 1; if ((j + 1) % K == 0) right[j] = A[j]; // block_end else right[j] = Math.max(right[j + 1], A[j]); } int [] output = new int[n - K + 1]; for (int i = 0; i < n - K + 1; i++) output[i] = Math.max(left[i + K - 1], right[i]); return output; }

### Python Code for DP Approach

def SlidingWindowMaximum(A, K): n = len(A) if n * K == 0: return [] if K == 1: return A left = [0] * n left[0] = A[0] right = [0] * n right[n - 1] = A[n - 1] for i in range(1, n): # from left to right if i % k == 0: left[i] = A[i] else: left[i] = max(left[i - 1], A[i]) j = n - i - 1 if (j + 1) % K == 0: right[j] = A[j] else: right[j] = max(right[j + 1], A[j]) output = [] for i in range(n - K + 1): output.append(max(left[i + K - 1], right[i])) return output

**Time Complexity:**O(N) where N is the size of the array **A[]**.**Space Complexity:**O(N), as extra space is used.

## Practice Questions:

## Frequently Asked Questions

**What is the time complexity of finding maximum for each window of size K**The time complexity is

**O(N)**using a dynamic programming approach.

**Can we use a heap to solve the problem?**Yes, a max heap can be used to solve the problem, but in that case, the time complexity would be O(N log K), since insertion in a max heap takes log(K) time. Here K denotes the size of the sliding window.