Maximum of all subarrays of size k

Hello Coders, in this post we will discuss the “Maximum of all subarrays of size k” problem, also known as the Sliding Window Problem. So without wasting time, let’s look at the problem statement!

Understanding the Problem:

You are given an array consisting of N integers, and an integer K which denotes the length of a subarray, your task is mainly to determine the maximum element for each subarray of size K.

Note:

1. A subarray is basically a contiguous subset of a given array.
2. The array can also include duplicate elements.
3. The given array always follows 0-based indexing.
4. It is always guaranteed that there exists at least one subarray of size K.

Lets have a look at an example:

Input: arr= [4, 5, 6, 7, 8, 9, 10, 11, 12, 13], K = 3 
Output:6 7 8 9 10 11 12 13
Explanation: 
Maximum of 4, 5, 6 is 6
Maximum of 5, 6, 7 is 7
Maximum of 6, 7, 8 is 8
Maximum of 7, 8, 9 is 9
Maximum of 8, 9,10 is 10 
Maximum of 9,10,11 is 11
Maximum of 10,11,12 is 12

Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4 
Output: 10 10 10 15 15 90 90
Explanation:
Maximum of first 4 elements is 10, similarly for next 4 
elements (i.e from index 1 to 4) is 10, So the sequence 
generated is 10 10 10 15 15 90 90

Now, we will discuss various methods to solve the above problem.

The solution to Maximum of all subarrays of size k

#Method1

This is a very basic and simple method to solve the given problem.

Approach: We will run a basic nested loop in which the outer loop will mark the starting point of the subarray of length k and the inner loop will run from the starting index to index+k. We will consider the elements from starting index and print the maximum element among these k elements. 

Algorithm:

  1. First, you need to create a nested loop where the outer loop will start from starting index to n – k th elements. The inner loop will run for k iterations as k is the max number of elements required in the subarray.
  2. Then we proceed to create a variable that will store the maximum of k elements traversed by the inner loop.
  3. Finally, we find the maximum of these k elements that are traversed by the inner loop.
  4. Then, we print the maximum element after each and every iteration of the outer loop.

Code:

def printMax(arr, n, k):
    max = 0
   
    for i in range(n - k + 1):
        max = arr[i]
        for j in range(1, k):
            if arr[i + j] > max:
                max = arr[i + j]
        print(str(max) + " ", end = "")
 
# Driver method
if __name__=="__main__":
    n = int(input())   //Number of elements in arrayi.e the length of the array

    for i in range(0,n):
       ele = int(input())
  
     arr.append(ele)
    k = int(input())
  //Value of subarray
    printMax(arr, n, k)

Complexity Analysis: 

  1. Time Complexity: O(N * K). 
    The outer loop runs n-k+1 times i.e for 7 elements it will run (7-3+1=5) times where subarray(k) is 3. The inner loop will run for k times after every iteration of outer loop. So time complexity is O((n-k+1)*k) which can also be written as O(N * K).
  2. Space Complexity: O(1). No extra space is required.

#Method2

Approach:

This method uses Deque to solve the above problem. There are many varieties of different algorithms for this problem. The most difficult, but most efficient use idea of the decreasing deque where on each moment of time we will keep only decreasing numbers in it.

Let us consider the following example: nums = [1,3,-1,-3,5,3,6,7], k = 3. Let us process numbers one by one: (We will print numbers and keep indexes in our stack):

Algorithm:

  1. We put 1 into empty deque: [1].
  2. The new element is bigger than the previous one, so we remove the previous element and put a new one: [3].
  3. The next element is smaller than the previous, put it to the end of deque: [3, -1].
  4. Similar to the previous step: [3, -1, -3].
  5. Now, let us look at the first element 3, it has an index 1 in our data, what does it mean? It was too far ago, and we need to delete it: so we pop-left it. So, now we have [-1, -3]. Then we check that the new element is bigger than the top of our deque, so we remove two elements and have [5] in the end.
  6. The new element is smaller than the previous, just add it to the end: [5, 3].
  7. The new element is bigger, so we remove elements from the end until we can put: [6].
  8. Similarly remove elements from the end until we can put: [7]

So, once again we have the following rules:

  1. Elements in deque are always in decreasing order.
  2. They are always elements from the last sliding window of k elements.
  3. It follows from here, that the biggest element in the current sliding window will be the 0th element in it.

This method can be easily understood by the following representation.

maximum of all subarrays of size k
Flow of the given approach

Code:

class Solution:
    def maxSlidingWindow(self, nums, k):
        deq, n, ans = deque([0]), len(nums), []

        for i in range (n):
            while deq and deq[0] <= i - k:
                deq.popleft()
            while deq and nums[i] >= nums[deq[-1]] :
                deq.pop()
            deq.append(i)
            
            ans.append(nums[deq[0]])
            
        return ans[k-1:]

Now lets understand the code with an example:

Example:

print(Solution().maxSlidingWindow([8,3,-1,-3,5,3,6,7], 3))

i = 0, curr element = 8, d = deque([]) and out = []
	 Added i to d
i = 1, curr element = 3, d = deque([0]) and out = []
	 Added i to d
i = 2, curr element = -1, d = deque([0, 1]) and out = []
	 Added i to d
	 Append nums[d[0]] = 8 to out
i = 3, curr element = -3, d = deque([0, 1, 2]) and out = [8]
	 Added i to d
	 Popped left from d because it's outside the window's leftmost (i-k)
	 Append nums[d[0]] = 3 to out
i = 4, curr element = 5, d = deque([1, 2, 3]) and out = [8, 3]
	 Popped from d because d has elements and nums[d.top] < curr element
	 Popped from d because d has elements and nums[d.top] < curr element
	 Popped from d because d has elements and nums[d.top] < curr element
	 Added i to d
	 Append nums[d[0]] = 5 to out
i = 5, curr element = 3, d = deque([4]) and out = [8, 3, 5]
	 Added i to d
	 Append nums[d[0]] = 5 to out
i = 6, curr element = 6, d = deque([4, 5]) and out = [8, 3, 5, 5]
	 Popped from d because d has elements and nums[d.top] < curr element
	 Popped from d because d has elements and nums[d.top] < curr element
	 Added i to d
	 Append nums[d[0]] = 6 to out
i = 7, curr element = 7, d = deque([6]) and out = [8, 3, 5, 5, 6]
	 Popped from d because d has elements and nums[d.top] < curr element
	 Added i to d
	 Append nums[d[0]] = 7 to out
[8, 3, 5, 5, 6, 7]

Complexity Analysis:

  1. Time complexity is O(n) because we iterate over our elements and for each element, it can be put inside and outside of our deque only once.
  2. Space complexity is O(k), which is the maximum size of our deque.

#Method3

This method uses the uses the Self-Balancing BST(AVL Tree) to solve the above problem.

Approach: 
To find maximum among k elements of the subarray the #method1 uses a loop traversing through the elements. In order to reduce the time the idea is to use an AVL Tree that will return the maximum element in a log N time.

So basically, we traverse through the array and keep k elements in the BST and print the maximum in every iteration. BST Tree is a suitable data structure for lookup, insertion, and deletion. It takes O(log n) time in both the average and worst cases, where N is the number of nodes in the tree.

Algorithm: 

  1. First, we create a Self-balancing BST (AVL tree) to store and find the maximum element of the array.
  2. The next step is to traverse through the array from start to end.
  3. Then we insert the element in the AVL tree.
  4. If the loop counter is greater than or equal to k then we delete i-k th element from the BST(AVL Tree)
  5. Last but not least we print the maximum element of the BST.

Code:

class Solution {
    public int[] maxSlidingWindow(int[] arr, int k) {
        int n = arr.length, j = 0;
        int[] ans = new int[n - k + 1];
        TreeMap<Integer, Integer> bst = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            bst.put(arr[i], bst.getOrDefault(arr[i], 0) + 1);
            if (i + 1 >= k) {
                ans[j++] = bst.lastKey(); // return max element in BST
                removeElement(bst, arr[i+1-k]);
            }
        }
        return ans;
    }
    void removeElement(TreeMap<Integer, Integer> bst, int x) {
        bst.put(x, bst.getOrDefault(x, 0) - 1);
        if (bst.get(x) == 0) bst.remove(x);
    }
}

Complexity Analysis:

  1. Time Complexity: O(N log k), each operation of BST of size K costs O(logk). Also, Insertion, deletion, and search take log k time in an AVL tree.
  2. Space Complexity: The space required to store k elements in a BST O(k)

#Method4

This method uses Max-Heap to solve the above problem.

Approach: 
In the above-mentioned methods to solve the given problem statement, #Method 3 was using AVL tree right. The Max-Heap approach is very similar to the AVL Tree approach.

Max-heap is a suitable data structure as it provides constant-time retrieval and logarithmic time removal of both the minimum and maximum elements in it, i.e. it takes constant time to find the maximum element and insertion and deletion takes log n time. 

Algorithm:

 We can keep the running window of elements and their positions in a heap and get the largest one at every timestep, cleaning up the heap lazily as we see stale elements in there. This would give us O(logN) solution:

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	if k == 1: return nums
	rwindow = [(-val, i) for i, val in enumerate(nums[:k])]
	heapq.heapify(rwindow)
	res = [-rwindow[0][0]]

	for i in range(k, len(nums)):
		while rwindow[0][1] <= i - k: heapq.heappop(rwindow)
		heapq.heappush(rwindow, (-nums[i], i))
		res.append(-rwindow[0][0])

	return res

To achieve the 0(N) solution we can mainly use a deque of indices of up to k last observed elements as a window. While iterating over the array:

  1. We clean up the stale elements from the tail of the deque, and
  2. If we see a new element that is larger than or equal to the one at the head, it kicks out smaller elements since they can no longer be the max value in the current window.
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	minqueue = deque()

	# initialize the window
	for i in range(min(k, len(nums))):
		while minqueue and nums[minqueue[-1]] <= nums[i]: minqueue.pop()
		minqueue.append(i)

	res = [nums[minqueue[0]]]  # results

	for i in range(k, len(nums)):
		while minqueue and minqueue[0] <= i - k:  # clean up stale elements
			minqueue.popleft()
		while minqueue and nums[minqueue[-1]] <= nums[i]:  # kick out smaller ones
			minqueue.pop()
		minqueue.append(i)
		res.append(nums[minqueue[0]])  # guaranteed to be the max

	return res

Conclusion

Hope you find this post helpful. We have discussed 4 methods towards approaching the “Maximum of all Subarrays of size K” problem in this post. We hope that you found it easy to understand and implement.

Stay tuned for more posts and updates. Until then, Happy Coding!

Leave a Comment

Your email address will not be published. Required fields are marked *