Maximum In Sliding Windows Of Size K
Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ‘K’ numbers in a particular window at a time. For each of the 'N'-'K'+1 different windows thus formed, you are supposed to return the maximum element in each of them, from the given array/list.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases. The 'T' test cases follow. The first line of each test case contains two single space-separated integers ‘N’ and ‘K’ denoting the number of elements in the array/list and the size of the window size respectively. The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.

Output format :

For each test case, print the output array/list which contains the sliding window maximum in a separate line.

Note :

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

Constraints :

1

Question

Maximum In Sliding Windows Of Size K

Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ‘K’ numbers in a particular window at a time. For each of the 'N'-'K'+1 different windows thus formed, you are supposed to return the maximum element in each of them, from the given array/list.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains two single space-separated integers ‘N’ and ‘K’ denoting the number of elements in the array/list and the size of the window size respectively.

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.

Output format :

For each test case, print the output array/list which contains the sliding window maximum in a separate line.

Note :

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

Constraints :

1 <= T <= 50
1 <= N <= 10^4
1 <= K <= N
0 <= ARR[i] <= 10^5

Where, ARR[i] denotes the i-th element in the array/list.

Time Limit: 1 sec.

Accepted Answer

Brute Force

Our intuition here is to go through each sliding window and keep track of the maximum element in each sliding window. To implement the same we run two nested loops, where the outer loop which will mark the starting point of the subarray of length k, the inner loop will run from the starting INDEX to INDEX + K, K elements from starting index and store the maximum element among these K elements into the answer.

STEPS :

Use two nested loops.
The outer loop from starting INDEX = 0 to N - K th elements.
The inner loop will run for ‘K’ iterations for the window size of ‘K’.
Now create a variable to store the maximum of K elements that are traversed in the inner loop.
Find the maximum of K elements traversed by the inner loop.
Store the maximum element in every iteration of the outer loop which is nothing but the sliding window maximum of the current window.

Space Complexity: O(n)Explanation:

O(N), where N is the number of elements in the given array/list.

There is no extra space required in the implementation but we have to consider the space where we are storing the maximum elements of the windows of K length which in the worst case can go up to N elements in the output list/array. So the overall space complexity will be O(N).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*K), where N is the number of elements in the given array/list and ‘K’ is the given window size.

We are pivoting N-K+1 elements once and for every element, we are traversing the given array/list for K iterations (traversing the window) to find the maximum value. So there will be a total of N-K+1 elements to pivot and then traversing the window of size K in the array/list will take O(K) time. So the overall total time complexity will be O((N-K+1)*K) i.e O(N*K).

Python (3.5)

'''
    Time Complexity = O(N*K)
    Space Complexity = O(N)

    Where N is the number of elements in the given array/list and K is the given window size.
'''


def slidingWindowMaximum(nums, k):
    n = len(nums)
    result = []

    for i in range(n - k + 1):
        # Intially assigned to the first value of the window.
        maxValue = nums[i]

        # For the whole window we try to find out the maximum value among the array/list elements.
        for j in range(k):
            if nums[i + j] > maxValue:
                maxValue = nums[i + j]

        # Add maximum of the current window to the result.
        result.append(maxValue)

    return result

C++ (g++ 5.4)

/*
    Time Complexity = O(N*K)
    Space Complexity = O(N)

    Where N is the number of elements in the given array/list and K is the given window size.
*/

vector slidingWindowMaximum(vector &nums, int &k)
{

    int n = nums.size();

    vector result;

    for (int i = 0; i <= n - k; i++)
    {
        //    Intially assigned to the first value of the window.
        int maxValue = nums[i];

        //    For the whole window we try to find out the maximum value among the array/list elements.
        for (int j = 1; j < k; j++)
        {
            if (nums[i + j] > maxValue)
            {
                maxValue = nums[i + j];
            }
        }

        //    Add maximum of the current window to the result.
        result.push_back(maxValue);
    }

    return result;
}

Java (SE 1.8)

/*
    Time Complexity = O(N*K)
    Space Complexity = O(N)

    Where N is the number of elements in the given array/list and 'K' is the length of given window size.
*/


import java.util.ArrayList;

public class Solution
{

    public static ArrayList getMaximumOfSubarrays(ArrayList nums, int k)
    {
        int n = nums.size();

        //    Initialise a ArrayList to store the maximum element of subarrays.
        ArrayList result = new ArrayList(n - k + 1);

        //    Start traversing the array. "i" denotes the lower end of the window.
        for (int i = 0; i <= n - k; i++)
        {
            //    Intially assigned to the first value of the window.
            int maxValue = nums.get(i);


            //    For the whole window we try to find out the maximum value among the array/list elements.
            for (int j = 1; j < k; j++)
            {
                if (nums.get(i + j) > maxValue)
                {
                    maxValue = nums.get(i + j);
                }
            }

            //    Store the maximum of the current window i.e. maximum of result [i, i + k - 1].
            result.add(maxValue);
        }

        return result;
    }
}

Accepted Answer

Map Based Approach

The basic idea of this approach is to use an efficient data structure for querying the maximum element in the window.

We can use an ordered_map in C++ (TreeMap in java) to perform this task.

Consider the following figure to see what happens when we move the window.

We can observe that when we slide our window, which is currently denoting a subarray [0, 2], two things happen :

Element at index 0 is removed.
And the element at index 3 is added.

Now, we just want to get the maximum element in our updated window. The above task can easily be done using the ordered_map efficiently. Therefore we will use an ordered_map for storing the elements of the window. Since insertion, the deletion and query for the maximum element can be done in O(logN) time in the ordered_map. This approach would be more efficient than the previous one.

Consider the steps as follows :

Initialise an ordered_map window, which is used to store the frequency of elements. Iterate through the elements of the window [0, K-2] and store the frequencies in the window.
Create a loop and start iterating using a variable “high” which denotes the higher end of the window, which will be initially at ‘K’-1.
At each iteration :
1. Insert the element at index “high” in the window i.e . window[ARR[high]] = window[ARR[high]] + 1
2. Store the maximum of the current window which would be the first element, i.e. return window->begin().first.
3. Remove the element at index “high” - K + 1 from the window.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the given array/list.

Since we are using an ordered_map to store the elements of the window, and the length of the window is K. And also we are using an array/list to store the maximum element of each window of length K. And there can be N - K + 1 such window. So the overall space complexity will be O(N).

Time Complexity: O(nlogn)Explanation:

O(N * log(K)), where N is the number of elements in the given array/list. And K is the length of the required window.

Since we are using a sliding window technique where the window is moving through the array for N - K + 1 times, and we are finding the maximum element in the window of size ‘K’ every time using the ordered_map which takes O(log(K)). So the overall time complexity is O(N * log(K)).

Python (3.5)

'''
    Time Complexity = O(N* log(K))
    Space Complexity = O(N)

    Where N is the number of elements in the given array/list and K is the given window size.
'''


def slidingWindowMaximum(nums, k):
    n = len(nums)
    result = []

    # An ordered map to store the frequence of elements in the window.
    window = {}

    # Initialise the window with first 'k' - 1 elements.
    for i in range(k - 1):
        temp = 0
        if nums[i] in window:
            temp = window[nums[i]]
        window[nums[i]] = temp + 1

    # Initialise a vector to store the maximum element of subarrays.
    windowMax = [0] * (n - k + 1)

    # Start traversing the array.
    for high in range(k - 1, n):
        if nums[high] not in window:
            window[nums[high]] = 0
        # Insert the current element in the window.
        window[nums[high]] = window[nums[high]] + 1

        # Get the maximum of the current window i.e. maximum of subarray [high-k+1, high].
        windowMax[high - k + 1] = max(window.keys())

        # Remove the element at "high" - K + 1 from the window.
        if window[nums[high - k + 1]] == 1:
            # Remove the element from the window.
            window.pop(nums[high - k + 1])
        else:
            # Decrement the frequency by 1
            window[nums[high - k + 1]] -= 1

    # Return the final answer
    return windowMax

Java (SE 1.8)

/*

    Time Complexity = O(N* log(K))

    Space Complexity = O(N)

    

    Where N is the number of elements in the given array/list and K is the given window size.

*/





import java.util.ArrayList;

import java.util.TreeMap;



public class Solution 

{



	public static ArrayList getMaximumOfSubarrays(ArrayList nums, int k) 

	{

		int n = nums.size();



		//    An ordered map to store the frequence of elements in the window.

		TreeMap window = new TreeMap();



		//    Initialise the window with first 'k' - 1 elements.

		for (int i = 0; i < k - 1; i++) 

		{



			Integer temp = window.get(nums.get(i));

			if ( temp == null) 

			{

				temp = 0;

			}

			window.put(nums.get(i), temp + 1);

		}



		//    Initialise a ArrayList to store the maximum element of subarrays.

		ArrayList subarrayMax = new ArrayList(n - k + 1);



		for (int i = 0; i < (n - k + 1); i++) 

		{

			subarrayMax.add(0);

		}



		//    Start traversing the array.

		for (int high = k - 1; high < n; high++) 

		{

			//    Insert the current element in the window.



			Integer temp = window.get(nums.get(high));

			if ( temp == null) {

				temp = 0;

			}

			window.put(nums.get(high), temp + 1);



			//    Get the maximum of the current window i.e. maximum of subarray [high-k+1, high].

			subarrayMax.set(high - k + 1, window.lastKey());



			temp = window.get(nums.get(high - k + 1));



			//    Remove the element at "high" - K + 1 from the window.

			if (temp == 1) 

			{

				//    Remove the element from the window.

				window.remove(nums.get(high - k + 1));

			} 

			else 

			{

				//    Decrement the frequency by 1.

				window.put(nums.get(high - k + 1), temp - 1);

			}

		}



		return subarrayMax;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity = O(N* log(K))

    Space Complexity = O(N)

    

    Where N is the number of elements in the given array/list and K is the given window size.

*/



#include 



vector slidingWindowMaximum(vector &nums, int &k)

{

    int n = nums.size();



    //    An ordered map to store the frequence of elements in the window.

    map window;



    //    Initialise the window with first 'k' - 1 elements.

    for (int i = 0; i < k - 1; i++)

    {

        window[nums[i]]++;

    }



    //    Initialise a vector to store the maximum element of subarrays.

    vector windowMax(n - k + 1, 0);



    //    Start traversing the array.

    for (int high = k - 1; high < n; high++)

    {

        //    Insert the current element in the window.

        window[nums[high]] = window[nums[high]] + 1;



        //    Get the maximum of the current window i.e. maximum of subarray [high-k+1, high].

        windowMax[high - k + 1] = (window.rbegin())->first;



        //    Remove the element at "high" - K + 1 from the window.

        if (window[nums[high - k + 1]] == 1)

        {

            //    Remove the element from the window.

            window.erase(nums[high - k + 1]);

        }

        else

        {

            //    Decrement the frequency by 1.

            window[nums[high - k + 1]]--;

        }

    }



    return windowMax;

}

Accepted Answer

Deque Based Approach

The basic idea of this approach is to use a deque to store the elements of the window. We will maintain a deque that will store elements in non-increasing order such that the maximum element of the window is at the front of the deque. We will store the index of the elements of the given array/list.

STEPS:

Initialize a deque window that stores the index of the element in the given array/list. And insert the first K - 1 element in the deque. While inserting in the back of the deque, check if the last element is less than the current element, if it is so, removes the element from the back of the deque until all elements are greater than the current element. Then, insert the current element at the back of the deque.
Start traversing the array from the front using an index i which denotes the end of the current window such that K - 1 <= i <= N - 1.
- Remove the front element from the deque if its index lies outside the boundary of the current window because the deque is used to store the index of the current window.
- Now, remove the elements from the back of the deque until the last element is greater than or equal to the current element because we want to maintain a non-increasing deque.
- Insert the index of the current element at the end of the deque.
- Get the maximum element of the current window which is at the front of the deque. Store the maximum element of the current window.
Return the final answer.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the given array/list.

Since we are using a deque to store the elements of the window, and the length of the window is K. And also we are using an array/list to store the maximum element of each window of length K. And there can be N - K + 1 such window. So the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the given array/list.

Since we will be adding and removing every element of the array in the window at most once during the whole process and in the deque, push and the pop operation from the front or back operation takes O(1) time. So the overall time complexity will be O(N).

C++ (g++ 5.4)

/*
    Time Complexity = O(N)
    Space Complexity = O(N)

    Where N is the number of elements in the given array/list.
*/

#include 

vector slidingWindowMaximum(vector &nums, int &k)
{

    //    Create a Double Ended Queue of capacity K.
    deque window(k);

    int n = nums.size();

    vector result;

    //    For the first window.
    for (int i = 0; i < k; i++)
    {

        //    For every element, the previous smaller elements are of no use so remove them from q.
        while ((!window.empty()) && nums[i] >= nums[window.back()])
        {
            //    Remove from rear
            window.pop_back();
        }

        //    Add new element at rear of queue.
        window.push_back(i);
    }

    //    For rest of the elements from nums[k] to nums[n-1]
    for (int i = k; i < n; i++)
    {

        //    The element at the front of the queue is the largest element of previous window, so add it to the result.
        result.push_back(nums[window.front()]);

        //    Remove the elements which are out of this window
        while ((!window.empty()) && window.front() <= i - k)
        {
            //    Remove from front of queue
            window.pop_front();
        }

        //    Remove all elements smaller than the currently being added element.
        while ((!window.empty()) && nums[i] >= nums[window.back()])
        {
            window.pop_back();
        }

        //    Add current element at the rear of queue.
        window.push_back(i);
    }

    //    Add the maximum element of the last window.
    result.push_back(nums[window.front()]);

    return result;
}

Java (SE 1.8)

/*
    Time Complexity = O(N)
    Space Complexity = O(N)

    Where N is the number of elements in the given array/list.
*/

import java.util.Deque;
import java.util.ArrayList;
import java.util.LinkedList;

public class Solution
{

	public static ArrayList getMaximumOfSubarrays(ArrayList nums, int k)
	{

		int n = nums.size();

		//    Create a deque window to store the index of elements.
		Deque window = new LinkedList();

		//    Initialise a ArrayList to store the maximum element of subarrays.
		ArrayList result = new ArrayList(n - k + 1);

		//    Initialise the deque with first 'k' - 1 elements.
		for (int i = 0; i < k - 1; i++)
		{

			//    For every element, the previous smaller elements are of no use so remove them from the window.
			while (!window.isEmpty() && nums.get(window.getLast()) < nums.get(i))
			{
				window.pollLast();
			}

			//    Add new element at rear of queue.
			window.addLast(i);
		}

		//    For rest of the elements from nums[k] to nums[n-1]
		for (int i = k - 1; i < n; i++)
		{
			//    The element at the front of the queue is the largest element of previous window, so add it to the result.
			if (!window.isEmpty() && window.getFirst() <= i - k)
			{
				window.pollFirst();
			}

			//    Remove the last element if it is smaller than the current element.
			while (!window.isEmpty() && nums.get(window.getLast()) < nums.get(i))
			{
				window.pollLast();
			}

			//    Insert the index of current element at the back of the deque.
			window.addLast(i);

			//    Get the maximum of the current window i.e. maximum of subarray [i-k+1, i].
			result.add( nums.get(window.getFirst()));
		}

		return result;
	}
}

Python (3.5)

'''
    Time Complexity = O(N)
    Space Complexity = O(N)

    Where N is the number of elements in the given array/list.
'''

from collections import deque


def slidingWindowMaximum(nums, k):
    n = len(nums)
    result = []

    # Create a Double Ended Queue of capacity K.
    window = deque()

    # For the first window
    for i in range(k):
        # For every element, the previous smaller elements are of no use so remove them from q.
        while len(window) and nums[i] >= nums[window[-1]]:
            window.pop()

        # Add new element at rear of queue.
        window.append(i)

    # For rest of the elements from nums[k] to nums[n-1]
    for i in range(k, n):
        # The element at the front of the queue is the largest element of previous window, so add it to the result.
        result.append(nums[window[0]])

        # Remove the elements which are out of this window
        while len(window) and window[0] <= i - k:
            window.popleft()

        # Remove all elements smaller than the currently being added element.
        while len(window) and nums[i] >= nums[window[-1]]:
            window.pop()

        window.append(i)

    # Add the maximum element of the last window.
    result.append(nums[window[0]])

    # Return the final answer
    return result

Input format :

Output format :

Note :

Constraints :

Top Lifesight Software Developer interview questions & answers

Popular interview questions of Software Developer