Maximum of All Subarrays of Size K

Table of Contents

Introduction

A good programmer is the one who can write the most optimized codes. To develop this ability, the knowledge of data structures and algorithms becomes essential. Due to this reason, the knowledge of Data Structures and Algorithms (DSA) is frequently tested in interviews for SDE(Software Development Engineering) roles. The importance of DSA cannot be emphasized enough, especially if you aim to get placed in product-based companies like Google, Amazon, Microsoft, Adobe, etc.

For questions related to each data structure, refer to the blog Must-Do Coding Interview Questions for Product Based Companies.

This blog will discuss the interview problem: find the maximum of all subarrays of size k previously asked in companies like Amazon, SAP Labs, Flipkart, Directi, etc.

Maximum of all subarrays of size K: Problem Statement

Given an array consisting of “n” non-negative integers and an integer “k” denoting the length of the subarray. Find the maximum element in each subarray of size k.

For example:-

Input:

arr: 11 3 6 9 
k: 3

Output:

11 9

Explanation:

Window 1: [11, 3, 6]

The maximum element is 11.

Window 1: [3, 6, 9]

The maximum element is 9.

Explanation

Now let’s see various approaches to find the maximum of all subarrays of size k.

Maximum of All Subarrays of Size K: Using Nested Loops

In this approach, we will be using nested loops. The maximum element in the window will be obtained by iterating from the i^th array index to the (i+k)^tharray index.

Steps:

Create a max variable.
Iterate from starting index to n – k^th elements in the outer loop.
Iterate through the next k elements from the i^th element in the inner loop.
Update the max value in the inner loop.
Print the maximum element of every window.

Code:

public class Main {
  // function to calculate the maximum number in the subarray
  private static void maxOfSubarray(int[] arr, int k) {
    int max = Integer.MIN_VALUE;
 
   // traverse from an index till the next k numbers
    for(int i = 0 ; i <= arr.length - k ; i++) {
      max = arr[i];
      for(int j = i + 1 ; j <= i + k - 1; j++) {
       // find the maximum number
        max = Math.max(max, arr[j]);
      }
      System.out.print(max+" ");
    }
  }
 
  // driver Code
  public static void main(String[] args) {
    int[] arr = new int[] {11 ,3 ,9 ,6};
    int k = 3;
    maxOfSubarray(arr, k);
  }
}

Output:

11 9

Complexity Analysis:

Time Complexity: O(n * k)

The outer loop runs for (n-k+1) times, and the inner loop runs for k times. So the overall time complexity is O((n-k+1)*k), which can be simplified to O(n * k).

Space Complexity: O(1) as no extra space is required.

Where “n” is the number of elements in the array, and “k” is the size of the window.

Maximum of All Subarrays of Size K: Using Priority Queue

In this approach, we will use a priority queue that stores the elements in descending order of priority, i.e., the maximum element will have the highest priority. After every iteration, the priority queue will be updated with the latest elements.

Steps:

Create a priority queue that stores the elements in descending order of priority.
Add the first k numbers in the priority queue.
Print the maximum element in the first subarray.
Remove the first element from the priority queue.
Similarly, update the priority queue in every iteration and display the maximum element in each window.

Code:

import java.util.Collections;
import java.util.PriorityQueue;
 
public class Main {
  // function to calculate the maximum number in the subarray
  private static void maxOfSubarray(int[] arr, int k) {
    // create a priority queue which stores the maximum element at the front end
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
    
    int i;
    // add first k numbers in the priority queue
    for(i = 0 ; i < k ; i++)
      priorityQueue.add(arr[i]);
    
    // print the maximum number in the first subarray with size k
    System.out.print(priorityQueue.peek()+" ");
    
    // remove the first element from priority queue
    priorityQueue.remove(arr[0]);
    
    // add one element in every iteration and find the maximum element
    for( ; i < arr.length ; i++) {
      priorityQueue.add(arr[i]);
      System.out.print(priorityQueue.peek()+" ");
      priorityQueue.remove(arr[i - k + 1]);
    }
      
  }
 
  // driver Code
  public static void main(String[] args) {
    int[] arr = new int[] {11 ,3 ,9 ,6};
    int k = 3;
    maxOfSubarray(arr, k);
  }
}

Output:

11 9

Complexity Analysis:

Time Complexity: O(n * log k) as the elements are iterated once, and the insertion and deletion operations in the priority queue are O(log k).

Space Complexity: O(k) as the priority queue contains the “k” elements of the current window at any point in time.

Where “n” is the number of elements in the array, and “k” is the size of the window.

Maximum of All Subarrays of Size K: Using Deque

In this approach, we will use a deque that stores the array indexes. The queue is updated with the array indexes of “k” elements in every iteration by removing elements that are not there in the current window. The maximum element of every window is printed by accessing the element from the head of the deque.

Steps:

Create a deque to store array indexes.
Traverse the first k elements.
While the deque is not empty, remove the smaller elements from the rear end as we need the maximum element. Else, add the elements into the deque.
Traverse through the rest of the elements in the array.
Print the maximum element of the previous window.
Remove the elements that are not part of the current window.
Then while the deque is not empty, remove the smaller elements from the rear end as we need the maximum element.
Add the current element in the deque.
After completing the iteration, print the maximum element of the last window.

Code:

import java.util.Deque;
import java.util.LinkedList;
 
public class Main {
  // function to calculate the maximum number in the subarray
  private static void maxOfSubarray(int[] arr, int k) {
    // create deque to store indexes of array elements
    Deque<Integer> deque = new LinkedList<Integer>();
 
    int i;
    // traverse first k elements
    for (i = 0; i < k; ++i) {
 
      // remove the smaller elements from the rear end
      while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {
        deque.removeLast();
      }
  
      // add current element at the rear end
      deque.addLast(i);
    }
 
    // traverse through the rest of the elements
    for (; i < arr.length; ++i) {
 
      // print the maximum element of the previous window
      System.out.print(arr[deque.peek()] + " ");
 
      // remove elements that are not part of the current window
      while ((!deque.isEmpty()) && deque.peek() <= i - k)
        deque.removeFirst();
 
      // remove the smaller elements from the rear end
      while ((!deque.isEmpty()) && arr[i] >= arr[deque.peekLast()])
        deque.removeLast();
 
      // add current element at the rear end
      deque.addLast(i);
    }
 
    // print the maximum element of last window
    System.out.print(arr[deque.peek()]);
 
  }
 
  // driver Code
  public static void main(String[] args) {
    int[] arr = new int[] { 11, 3, 9, 6 };
    int k = 3;
    maxOfSubarray(arr, k);
  }
}

Output:

11 9

Complexity Analysis:

Time Complexity: O(n) as the elements are iterated once.
Space Complexity: O(k) as the deque contains the “k” elements of the current window at any point in time.

Where “n” is the number of elements in the array, and “k” is the size of the window.

Maximum of All Subarrays of Size K: Using Stacks

In this approach, we will use two stacks to store the elements. The k elements will be stored in both stack1 and stack2. The maximum element is found out by comparing the variable maximum of the topmost node in both stacks.

Steps:

Create two stacks: stack1 and stack2.
Add elements to stack2 except the last one in the first window.
Traverse the array.
Remove the element of the previous window if the loop counter is more than 1.
Add the new element of the current window.
Print the maximum element of the current window.

Note:

The element is always added into stack2.
The element is always popped out from stack1. If stack1 is empty, push the elements of stack2 into stack1 and update the maximum variable accordingly. Then pop the element from stack1.

Code:

import java.util.Stack;
 
class Node {
  int data;
  int maximum;
}
 
public class Main {
 
  // function to get the maximum element in the current window
  private static int getMax(Stack<Node> stack1, Stack<Node> stack2) {
    int max = Integer.MIN_VALUE;
    // maximum element in stack1
    if (stack1.size() > 0)
      max = Math.max(max, stack1.peek().maximum);
    
    // maximum element in stack2
    if (stack2.size() > 0)
      max = Math.max(max, stack2.peek().maximum);
    
    return max;
  }
 
  // function to remove element present in the previous window
  private static void deleteElement(Stack<Node> stack1, Stack<Node> stack2) {
    // if stack1 is not empty remove the element of the previous window
    if (stack1.size() > 0) {
      stack1.pop();
    } else {
      // push all element from stack2 into stack1
      while (!stack2.empty()) {
        Node value = stack2.peek();
        insertElement(stack1, value.data);
        stack2.pop();
      }
      // remove the element of the previous window
      stack1.pop();
    }
  }
 
  // function to insertElement the new element present in the current window
  private static void insertElement(Stack<Node> stack2, int value) {
    // inserting the new element of the current window into stack2
    Node newNode = new Node();
    newNode.data = value;
 
    if (stack2.empty()) {
      newNode.maximum = value;
    } else {
      Node front = stack2.peek();
      // initialize maximum of the node with the value of maximum element in current window
      newNode.maximum = Math.max(value, front.maximum);
    }
 
    // push the new node to the stack
    stack2.push(newNode);
  }
 
  // function to calculate the maximum number in the subarray
  private static void maxOfSubarray(int[] arr, int k) {
    Stack<Node> stack1 = new Stack<>();
    Stack<Node> stack2 = new Stack<>();
 
    // adding elements to stack2 except the last one in the first window
    for (int i = 0; i < k - 1; i++) {
      insertElement(stack2, arr[i]);
    }
 
    for (int i = 0; i <= arr.length - k; i++) {
      // remove the element of the previous window
      if (i - 1 >= 0) {
        deleteElement(stack1, stack2);
      }
 
      // add new element of the current window
      insertElement(stack2, arr[i + k - 1]);
 
      // print maximum element of the current window
      System.out.print(getMax(stack1, stack2) + " ");
 
    }
  }
 
  // driver Code
  public static void main(String[] args) {
    int[] arr = new int[] {11, 3, 9, 6};
    int k = 3;
    maxOfSubarray(arr, k);
  }
}

Output:

11 9

Complexity Analysis:

Time Complexity: O(n) as the elements are iterated once, and the insertion and deletion operations of the stack are O(1).

Space Complexity: O(k) as at any point of time the sum of elements in both the stacks is “k.”

Where “n” is the number of elements in the array, and “k” is the size of the window.

Maximum of All Subarrays of Size K: Using Self Balancing BST

In this approach, a self-balancing Binary Search Tree (BST) is used. “k” elements are stored in the BST, and the maximum element is printed in every iteration.

Steps:

Create a self-balancing BST to store the “k” elements
Traverse the array.
Insert the element in the self-balancing BST.
When the window of size “k” is formed, the maximum element is printed, and the element from the previous window is deleted.

Code:

import java.util.TreeMap;
 
public class Main {
 
  // function to remove the element of the previous window
  private static void removeElement(TreeMap<Integer, Integer> treeMap, int value) {
    treeMap.put(value, treeMap.getOrDefault(value, 0) - 1);
    // remove if no more element with the value is present
    if (treeMap.get(value) == 0)
      treeMap.remove(value);
  }
 
  // function to calculate the maximum number in the subarray
  private static void maxOfSubarray(int[] arr, int k) {
    // treemap stores the value of the element and the index
    TreeMap<Integer, Integer> treeMap = new TreeMap<>();
    for (int i = 0; i < arr.length; i++) {
      // insert the new element of the current window
      treeMap.put(arr[i], treeMap.getOrDefault(arr[i], 0) + 1);
      // when the window size reaches the value of k
      if (i + 1 >= k) {
        // return max element in the current window
        System.out.print(treeMap.lastKey() + " ");
        // remove the element of the previous window
        removeElement(treeMap, arr[i + 1 - k]);
      }
    }
  }
 
  // driver Code
  public static void main(String[] args) {
    int[] arr = new int[] { 11, 3, 9, 6 };
    int k = 3;
    maxOfSubarray(arr, k);
  }
}

Output:

11 9

Complexity Analysis:

Time Complexity: O(n * log k) as the elements are iterated once, and the operations of the BST of size “k” is O(log k).

Space Complexity: O(k) as at any point of time the treemap contains the “k” elements of the current window.

Where “n” is the number of elements in the array, and “k” is the size of the window.

Frequently Asked Questions

What is the sliding window algorithm?

A window is a contiguous sequence part of a linear data structure like an array. The sliding window algorithm is an algorithm that grazes the window linearly over the array.

What is the advantage of using a BST?

BST has O(log n) time complexity for operations like lookup, insertion, and deletion, where n is the number of nodes in the tree.

What is a deque?

A deque is a double-ended queue where insert and delete operations are defined for the queue’s front, and rear ends.

What is the time complexity to add and delete elements in a deque?

The time complexity to add and delete elements in a deque id O(1).

Key Takeaways

This blog covered the various methods to find the maximum of all subarrays of size k and their complexity analysis. The methods discussed are using a nested loop, priority queue, deque, stacks, and self-balancing BST.

Don’t stop here. Check out our Data Structures and Algorithms-guided path to learn Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.

By: Hari Sapna Nair