Sliding Maximum
You are given an array 'ARR' of integers of length 'N' and a positive integer 'K'. You need to find the maximum elements for each and every contiguous subarray of size K of the array.

For example

'ARR' = [3, 4, -1, 1, 5] and 'K' = 3 Output = [4, 4, 5] Since the maximum element of the first subarray of length three ([3, 4, -1]) is 4, the maximum element of the second subarray of length three ([4, -1, 1]) is also 4 and the maximum element of the last subarray of length three ([-1, 1, 5]) is 5, so you need to return [4, 4, 5].

Input format:

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. Then the 'T' test cases follow. The first line of each test case contains two positive integers 'N' and 'K' which represent the length of the array and length of the subarray respectively. The Second line of each test case contains 'N' space-separated integers representing the elements of the array.

Output Format :

For each test case, print 'X' space-separated integer denoting maximum elements for each and every contiguous subarray of size 'K' of the array. Where 'X' is the number of subarray of size 'K' in array 'arr'. Output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraint :

1

Question

Sliding Maximum

You are given an array 'ARR' of integers of length 'N' and a positive integer 'K'. You need to find the maximum elements for each and every contiguous subarray of size K of the array.

For example

'ARR' =  [3, 4, -1, 1, 5] and 'K' = 3
Output =  [4, 4, 5]

Since the maximum element of the first subarray of length three ([3, 4, -1]) is 4, the maximum element of the second subarray of length three ([4, -1, 1]) is also 4 and the maximum element of the last subarray of length three ([-1, 1, 5]) is 5, so you need to return [4, 4, 5].

Input format:

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. Then the 'T' test cases follow.

The first line of each test case contains two positive integers 'N' and 'K' which represent the length of the array and length of the subarray respectively.

The Second line of each test case contains 'N' space-separated integers representing the elements of the array.

Output Format :

For each test case, print 'X' space-separated integer denoting maximum elements for each and every contiguous subarray of size 'K' of the array. Where 'X' is the number of subarray of size 'K' in array 'arr'.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraint :

1 <= T <= 10
1 <= N <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= K <= N

Time Limit: 1 sec

Accepted Answer

It was a standard problem so I know the exact solution, you can simply use dequeue + two pointers to solve this questions.

Accepted Answer

Brute Force

We know that an array of size ‘N’ will have in total ‘N’ - ‘K’ - 1 subarray of size ‘K'.
Thus, what a trivial solution suggests is that we traverse over all subarrays of size ‘K', and calculate the maximum element in each of these subarrays individually.
So, we can run two nested loops, the outer one will iterate over the starting index of the subarray, and the inner loop will be used to calculate the maximum element in the current subarray of size ‘K’.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space is used.

Time Complexity: OtherExplanation:

O(N * K), where ‘N’ is the length of the array and ‘K’ is the size of the subarray.

As we are calculating the maximum element of all the subarray of size ‘K’ and there are ‘N’ elements in the array. Hence the overall complexity will be O(N).

Accepted Answer

MaxHeap

Create a class pair where we will have two variables i.e elements of the given array and their corresponding indexes.
Create an array and of size ‘N’ - ‘K’ + 1 size to store the maximum element of each subarray of size ‘K'.
Create a maxheap and store the first ‘K’ pair of elements and their indexes in it.
Max-heapify the elements of the heap and store the top element in the array ‘ANS’.
Run a loop from ‘K’ to ‘N’ and in every iteration
1. Add the current element of the array with its index in the heap.
2. Keep removing all the top elements which got out of the window by checking the condition which is current index- ‘MAX_HEAP’.peek().index >= 'K', as it will tell which elements are not in the current window
3. Thus now the top element will be the maximum of current subarray . Add this maximum element of the subarray(top element of the heap) in the array ‘ANS’
Return the'ANS' array.

Space Complexity: O(n)Explanation:

O(K), where ‘K’ is the size of the subarray.

We are using heap and heap will store at max ‘K’ element at a time. Hence the overall space complexity will be O(K).

Time Complexity: OtherExplanation:

O(N * log(K)), where ‘N’ is the length of the array and ‘K’ is the size of the subarray.

We are pushing and popping out the elements from the heap only once and in each iteration we are heapifying the elements of heap that will take O(size of the heap), so the overall total time complexity will be O(N * log(K)).

Accepted Answer

Dequeue

The idea is to use the deque to hold the index of the maximum element and restrict the deque size to ‘K’. We can use a double-ended queue to keep only the indices of those elements which are useful. The use of deque is to add and drop elements from both ends of a queue. We will slide the window of ‘K’ elements by “dropping” the first element and “adding” the next element after the window to move it forward.

The steps are as follows:

Create a deque to store ‘K’ elements and an array of size ‘N’ - ‘K’ + 1 to store the answer of each subarray of size ‘K’.
Run a loop and insert the first ‘K’ elements in the deque. While inserting the element if the element at the back of the deque is smaller than the current element then remove all those elements and then insert the current element at the end of the deque.
Now, run a loop from ‘K’ to the end of the array.
Store the front element of the deque in the array.
Remove the element from the front of the deque if they are out of the current window.
Insert the next element in the deque. While inserting the element if the element at the back of the deque is smaller than the current element then remove all those elements and then insert the current element.
Before returning the final array, store the maximum element of the last window in the array ‘ARR’.
Return the ‘ARR’.

Space Complexity: O(n)Explanation:

O(K), where ‘K’ is the size of the subarray.

Since we are using a deque of size ‘K’ to store the current window elements. Hence the overall space complexity will be O(K).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the array and ‘K’ is the size of the subarray.

Since we are inserting and deleting every element of the array in the deque only once. Hence the overall time complexity is O(N).