Maximum Of All Subarrays Of Size k.
You are given an array consisting of N non-negative integers, and an integer K denoting the length of a subarray, your task is to determine the maximum elements for each subarray of size K.

Note:

A subarray is a contiguous subset of an array. The array may contain duplicate elements. The given array follows 0-based indexing. It is guaranteed that there exists at least one subarray of size K.

Input Format:

The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains two space-separated integers N and K, as described in the problem statement. 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 in a new line, X space-separated integers, where X is the number of possible subarrays of size K, and the ith integer denote the maximum element of the ith possible subarray of size K starting from the left.

Note:

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

Constraints:

1

Question

Maximum Of All Subarrays Of Size k.

You are given an array consisting of N non-negative integers, and an integer K denoting the length of a subarray, your task is to determine the maximum elements for each subarray of size K.

Note:

A subarray is a contiguous subset of an array.

The array may contain duplicate elements.

The given array follows 0-based indexing.

It is guaranteed that there exists at least one subarray of size K.

Input Format:

The first line of the input contains an integer T denoting the number of test cases. 

The first line of each test case contains two space-separated integers N and K, as described in the problem statement.

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 in a new line, X space-separated integers, where X is the number of possible subarrays of size K, and the ith integer denote the maximum element of the ith possible subarray of size K starting from the left.

Note:

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

Constraints:

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

Time Limit: 1sec

Accepted Answer

Brute force approach

The Idea behind this brute force approach is to consider each subarray of size K by fixing a point i in the array and then consider all the points after it till we have considered K elements from the starting point i and finding the maximum element in it and then storing it.
Now, run a loop(say, loop variable i) till (N-K) elements of the array:
- Run a nested loop(say, loop variable j) through the elements starting from index i up to the next k elements.
- At each iteration of the inner loop keep a track of the maximum element in that subarray and finally after the nested loop ends store the answer for this subarray and continue the process for next i.

Space Complexity: OtherExplanation:

O(X), where X is the number of possible subarrays of size K.

We are storing the maximum of all the subarrays of size K, so the space complexity is O(X).

Time Complexity: OtherExplanation:

O(N * K), where N is the number of elements in the array and K is the length of the subarray.

The time complexity is O(N * K) because the outer loop will run for the order of O(N) and the inner loop will run for the order of O(K), So the total complexity is O(N * K).

Python (3.5)

'''
    Time Complexity: O(N*K)
    Space Complexity: O(X),

    Where N is the number of elements in the array, K is the size of the subarray and X is the number of possible subarray of size K.
'''

def maxOfSubarray(nums, n, k): 

    # Vector to store the answer
    ans=[]
    for i in range(n-k+1):

        # Variable to calculate the maximum of current subarray
        maximum = 0
        for j in range(i,i+k):
            maximum = max(maximum, nums[j])
        ans.append(maximum)
    return ans

Java (SE 1.8)

/*
    Time Complexity : O(N^2)
    Space Complexity : O(N)

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

import java.util.ArrayList;

public class Solution 
{

    public static ArrayList maxOfSubarray(ArrayList arr, int n, int k) 
    {
        //    Initialise a ArrayList to store the maximum element of subarrays.
        ArrayList subarrayMax = new ArrayList(n - k + 1);

        //    Start traversing the array. "low" denotes the lower end of the window.
        for (int low = 0; low <= n - k; low++) 
        {
            //    To store the maximum element of window.
            int curMax = 0;

            for (int high = low; high < low + k; high++) 
            {
                curMax = Math.max(curMax, arr.get(high));
            }

            //    Store the maximum of the current window i.e. maximum of subarray [low, low + k - 1].
            subarrayMax.add(curMax);
        }

        return subarrayMax;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N*K)
    Space Complexity: O(X),

    Where N is the number of elements in the array, K is the size of the subarray and X is the number of possible subarray of size K.
*/

vector maxOfSubarray(vector &nums, int n, int k) 
{
    // Vector to store the answer
    vector ans;
    for (int i = 0; i <= n - k; i++) 
    {
        // Variable to calculate the maximum of current subarray
        int maximum = 0;
        for (int j = i; j < i + k; j++) 
        {
            maximum = max(maximum, nums[j]);
        }

        ans.push_back(maximum);
    }

    return ans;
}

Accepted Answer

Set Based Approach

In the previous approach for finding the maximum element in the subarray we were iterating in the subarray of length K one by one, but we can optimize this step simply by using some data structure.
In this approach, we will be using a set that will be storing the current element and its index (i.e. pair where first is element and second is the index).
Now at each point, our set will contain K elements and the last element will be the maximum element as the set contains elements in ascending order.
So firstly, we will keep the first K element and its index in the set and iterate from the (K+1)th element to the last and simply remove the last element of the current window and insert the next element and its index in the set and at each iteration, the biggest element of the set is our answer for this window. I.e. remove {arr[i-K],i-K} from the set and insert {arr[i],i} in the set and the answer for this window will be (*st.rbegin()).first .

Space Complexity: OtherExplanation:

O(K + X), where K is the size of the subarray and X is the number of possible subarrays of size K.

Our set will contain K pairs at each moment and we will be storing the maximum element of each subarray of size K, so the space complexity will be O(K + X).

Time Complexity: OtherExplanation:

O(N * log(K)), where N is the number of elements in the array and K is the size of the subarray.

The complexity is O(N * log(K)) because we iterate in the array for the order of O(N) and for each window the set will be containing K element so insert and delete operation will take O(log(K)) time, So overall complexity will be O(N * log(K)).

Java (SE 1.8)

/*
   Time Complexity : O(N * log(K))
   Space Complexity : O(N)

   Where 'N' is the length of the given array/list.
   And 'K' is the length of the subarray.
*/

import java.util.ArrayList;
import java.util.TreeMap;

public class Solution 
{

	public static ArrayList maxOfSubarray(ArrayList arr,int n, int k) 
	{

		//    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(arr.get(i));
			if ( temp == null) 
			{
				temp = 0;
			}
			window.put(arr.get(i), temp + 1);
		}

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

		//    Start traversing the array.
		for (int high = k - 1; high < n; high++) 
		{
			//    Insert the current element in the window.

			Integer temp = window.get(arr.get(high));
			if ( temp == null) {
				temp = 0;
			}
			window.put(arr.get(high), temp + 1);

			//    Get the maximum of the current window i.e. maximum of subarray [high-k+1, high].
			subarrayMax.add(window.lastKey());

			temp = window.get(arr.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(arr.get(high - k + 1));
			} 
			else 
			{
				//    Decrement the frequency by 1.
				window.put(arr.get(high - k + 1), temp - 1);
			}
		}

		return subarrayMax;
	}
}

Python (3.5)

'''
    Time Complexity: O(N*log(K))
    Space Complexity: O(K+X),

    Where N is the number of elements in the array, K is the size of the subarray and X is the number of possible subarray of size K.
'''

from collections import defaultdict
import heapq

def maxOfSubarray(nums, n, k):

    # Vector to store the answer
    ans=[]
    
    # Set to store the elements and its indices
    st=[]
    freq=defaultdict(int)
    heapq.heapify(st)
    for i in range(k):
        heapq.heappush(st,-nums[i])
        freq[-nums[i]]+=1

    while(freq[st[0]]==0):
        heapq.heappop(st) 
    ans.append(-st[0])
    for i in range(k,n):
        
        # Variable to calculate the index of element that will be going out of the window
        freq[-nums[i-k]]-=1
        heapq.heappush(st,-nums[i])
        freq[-nums[i]]+=1
        while(freq[st[0]]==0):
            heapq.heappop(st) 
        ans.append(-st[0])
    return ans

C++ (g++ 5.4)

/*
    Time Complexity: O(N*log(K))
    Space Complexity: O(K+X),

    Where N is the number of elements in the array, K is the size of the subarray and X is the number of possible subarray of size K.
*/

#include

vector maxOfSubarray(vector &nums, int n, int k) 
{
    // Vector to store the answer
    vector ans;
    
    // Set to store the elements and its indices
    set> st;
    for (int i = 0; i < k; i++) 
    {
        st.insert({nums[i], i});
    }

    ans.push_back((*st.rbegin()).first);
    for (int i = k; i < n; i++) 
    {
        
        // Variable to calculate the index of element that will be going out of the window
        int prev = i - k;
        st.erase({nums[prev], prev});
        st.insert({nums[i], i});
        ans.push_back((*st.rbegin()).first);
    }
    return ans;
}

Accepted Answer

Deque Based Approach

In this approach, we will be using deque as we can further optimize the solution by deque.
The idea for this approach is that we will keep only those elements that are candidates for our answer. The deque will always keep the index of the element in the sorted order from first to last i.e., the biggest element at the front and the smallest element at the last.
We keep at max K element (i.e. the size of our window) in our deque and the current element is placed at its sorted place by popping all the smaller elements from the last so that the front element will always be the answer for this window.
Since we also have to remove those elements from the deque which are now out of the current window, so we will compare the front element of the deque with the starting position of the current window and if the front element of the deque is smaller than the starting position of the window then we pop the front element. We do this till no element which is out of the current window is there.
So we iterate the first K elements and keep the index of the maximum element of the first K elements from the array in our deque. Then iterate through the array from (K+1)th element till the last element and pop elements from the deque by comparing the last element of the deque to the current element (i.e. we pop the elements from the deque from the back till they are smaller than the current element (if(q.back()
Example - let the given array is [1,3,6,2,7] and K = 3
So initially our deque will have [2], as the maximum element in the first subarray of length K is 6 and its index is 2 and 6 will be our answer for the subarray [1,3,6].
Now we iterate from index 3 to last. So our current window will be [3,6,2] and our current element will be 2 and q = [2].
Firstly we check from the first if any element which is out of the window should not be present in the deque, so we check if the deque is containing elements smaller than 1 or not as our current window is from index [1,3].
After that, we will compare our current element with the element whose index is denoted by the last element of the deque and if the element of the deque is smaller then we pop it. So our current element is 2 and the last element of deque is the element at the 2nd index i.e. 6, so we will not pop the element.
And finally, we will push the index of the current element at the last. Therefore our deque will be, q = [2,3], so our answer for the subarray [3,6,2] will be 6 as it is the first element of the deque. After that our current window will become [6,2,7] and our current element will become 7.
Finally again we check if any element is present in our deque which out of our current window i.e. [2,4] and after this checking we again check if our current element is bigger than the element represented by the last element of the deque. So firstly a comparison will be made between the current element = 7 and the last element of the deque = 2 so the last element of the deque will be popped. Now our deque q = [2].
After that again a comparison will be made between the last element of the deque = 6 and the current element = 7, and again the last element of the deque will be popped. So now our deque will be empty ,q = []. So we will stop when our deque will become empty and finally push the current element in the deque, so our deque will be q = [4] and this element will be the answer of our current window i.e. 7.
Therefore our answer will be [6,6,7].

Space Complexity: OtherExplanation:

O(K + X), where K is the size of the subarray and X is the number of possible subarrays of size K.

Our deque will contain only at max K element at each moment and we will be storing the maximum element of each subarray of size K, so the space complexity will be O(K + X).

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array and K is the size of the subarray.

The complexity is O(N) because we iterate each element of the array only once and we simply process each element once in the deque.

Python (3.5)

'''
    Time Complexity: O(N)
    Space Complexity: O(K + X),

	Where N is the number of elements in the array, K is the size of the subarray and X is the number of possible subarray of size K.
'''

from collections import deque


def maxOfSubarray(nums, n, k):
    # Vector to store the answer
    ans = []

    # Deque to store the indices in sorted
    q = deque([])
    for i in range(k):
        # Store elements in the deque in a sorted manner.
        while (len(q) > 0 and nums[q[-1]] < nums[i]):
            q.pop()
        q.append(i)

    # Store the first element in the deque which is the maximum element.
    ans.append(nums[q[0]])
    for i in range(k, n):

        # Elements not in the sub-array of length k are popped.
        while (len(q) > 0 and q[0] <= (i - k)):
            q.popleft()

        # Store elements in the deque in a sorted manner.
        while (len(q) > 0 and nums[q[-1]] < nums[i]):
            q.pop()
        q.append(i)

        # Store the first element in the deque which is the maximum element.
        ans.append(nums[q[0]])
    return ans

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(K + X),

	Where N is the number of elements in the array, K is the size of the subarray and X is the number of possible subarray of size K.
*/

#include
#include

vector maxOfSubarray(vector &nums, int n, int k) 
{
	// Vector to store the answer
	vector ans;
	
    // Deque to store the indices in sorted
	deque q;
	for (int i = 0; i < k; i++) 
    {
        // Store elements in the deque in a sorted manner.
        while (!q.empty() && nums[q.back()] < nums[i]) 
        {
            q.pop_back();
        }

        q.push_back(i);
    }

    // Store the first element in the deque which is the maximum element.
    ans.push_back(nums[q.front()]);
	for (int i = k; i < n; i++) 
    {
        // Elements not in the sub-array of length k are popped.
		while (!q.empty() && q.front() <= (i - k)) 
        {
			q.pop_front();
		}

        // Store elements in the deque in a sorted manner.
		while (!q.empty() && nums[q.back()] < nums[i])
        {
			q.pop_back();
		}

		q.push_back(i);

        // Store the first element in the deque which is the maximum element.
		ans.push_back(nums[q.front()]);
	}
	
	return ans;
}

Java (SE 1.8)

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

   Where 'N' is the length of the given array/list.
*/

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

public class Solution 
{

	public static ArrayList maxOfSubarray(ArrayList arr, int n, int k) 
	{

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

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

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

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

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

		//    Start traversing the array.
		for (int i = k - 1; i < n; i++) 
		{
			//    Remove the front element from the deque if its index lies outside the boundary of the current window.
			if (!window.isEmpty() && window.getFirst() <= i - k) 
			{
				window.pollFirst();
			}

			//    Remove the last element if it is smaller than the current element.
			while (!window.isEmpty() && arr.get(window.getLast()) < arr.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].
			subarrayMax.add(arr.get(window.getFirst()));
		}

		return subarrayMax;
	}
}

You are given an array consisting of N non-negative integers, and an integer K denoting the length of a subarray, your task is to determine the maximum elements for each subarray of size K.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Travclan Technology India Technical Trainee interview questions & answers

Popular interview questions of Technical Trainee