medium Max of All Subarrays of Size 'k'

Problem Statement

Given an integer array arr and an integer k, return the result list containing the maximum for each and every contiguous subarray of size k.

In other words, result[i] = max(arr[0],..., arr[k]), result[1] = max(arr[1],...arr[k+1]), etc.

Examples

Example 1

• Input: arr = [1, 2, 3, 1, 4, 5, 2, 3, 6], k = 3
• Output: [3, 3, 4, 5, 5, 5, 6]
• Description: Here, subarray [1,2,3] has maximum 3, [2,3,1] has maximum 3, [3,1,4] has maximum 4, [1,4,5] has maximum 5, [4,5,2] has maximum 5, [5,2,3] has maximum 5, and [2,3,6] has maximum 6.

Example 2

• Input: arr = [8, 5, 10, 7, 9, 4, 15, 12, 90, 13], k = 4
• Output: [10, 10, 10, 15, 15, 90, 90]
• Description: Here, the maximum of each subarray of size 4 are 10, 10, 10, 15, 15, 90, 90 respectively.

Example 3

• Input: arr = [12, 1, 78, 90, 57], k = 3
• Output: [78, 90, 90]
• Description: Here, the maximum of each subarray of size 3 are 78, 90, and 90 respectively.

Constraints:

• 1 <= arr.length <= 10⁵
• -10⁴ <= arr[i] <= 10⁴
• 1 <= k <= arr.length

Solution

The approach to solve this problem involves utilizing a deque (double-ended queue) to efficiently track the maximum elements in each window of size 'k' as we traverse the array. Initially, we populate the deque with indices of elements, ensuring that it always contains elements in decreasing order. This way, the front of the deque always holds the index of the current maximum element. As we move the window, we add new elements to the rear of the deque, removing those from the front that fall outside the current window. We also remove elements from the rear if they are smaller than the new element being added, as they are no longer potential maximums. This strategy ensures that for each window, we can quickly identify the maximum element, which is always at the front of the deque.

Step-by-Step Algorithm

1. Initialize Data Structures:

   • Create a Deque<Integer> named dq to store indices of array elements.
   • Create a List<Integer> named result to store the maximum values of each sliding window.
   • Store the length of the input array arr in a variable n.

2. Iterate Through the Array:

   • Loop through the array arr using an index i that ranges from 0 to n-1.

3. Remove Out-of-Window Elements:

   • Inside the loop, first check if there are elements in the dq that are out of the current window. The current window is defined as the subarray from i-k+1 to i.
   • If the element at the front of the deque is out of this window (i.e., dq.peek() < i - k + 1), remove it from the front of the dq using poll().

4. Remove Useless Elements:

   • Next, check if there are any elements in the dq that are smaller than the current array element arr[i]. This helps to maintain the queue elements in decreasing order, keeping the largest element in the current window at the front.
   • Remove these smaller elements from the rear of the dq using pollLast(), as they are not useful for finding the maximum in the current window.

5. Add Current Element's Index:

   • After cleaning up the dq, add the current element's index i to the rear of the dq using offer(i).

6. Add Maximum to Result List:

   • If the index i is greater than or equal to k-1, it means the current window is fully formed.
   • The element at the front of the dq is the maximum of the current window, so add arr[dq.peek()] to the result list.

7. Repeat for All Elements:

   • Continue this process for all elements in the array.

8. Return the Result:

   • After processing all elements, return the result list containing the maximum values for each sliding window of size k.

Algorithm Walkthrough

Code

Here is how we can implement this algorithm:

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

public class Solution {

  public List<Integer> printMax(int[] arr, int k) {
    Deque<Integer> dq = new LinkedList<Integer>();
    List<Integer> result = new ArrayList<Integer>();
    int n = arr.length;
    for (int i = 0; i < n; i++) {
      // Remove the elements which are out of this window
      while (!dq.isEmpty() && dq.peek() < i - k + 1) dq.poll();

      // Remove all elements smaller than the currently being added element
      // (remove useless elements)
      while (!dq.isEmpty() && arr[i] >= arr[dq.peekLast()]) dq.pollLast();

      // Add current element at the rear of dq
      dq.offer(i);

      if (i >= k - 1) result.add(arr[dq.peek()]);
    }

    return result;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    int arr[] = { 12, 1, 78, 90, 57 };
    int k = 3;
    List<Integer> result = s.printMax(arr, k);

    // Print the result array
    System.out.println(result);
  }
}

Complexity Analysis

Time Complexity

• Single pass through the array: The algorithm processes each element of the array exactly once by iterating over the array in a single pass. This gives us an initial time complexity of , where N is the length of the array.

• Deque operations:

  • Each element is added to the deque once and removed from the deque at most once. Therefore, all enqueue (offer) and dequeue (poll) operations are done in constant time, , per element.
  • The while loops inside the iteration only remove elements from the deque in constant time per iteration. Since each element is processed once and added/removed only once from the deque, the total number of deque operations is .

• Therefore, the overall time complexity of the algorithm is .

Overall time complexity: .

Space Complexity

• Deque space: The deque stores indices of array elements. At most, it will store k elements (since it only keeps track of elements in the current window of size k), so the space complexity for the deque is .

• Result list: The result list stores the maximum of each sliding window, which requires space (where N - k + 1 is the number of windows). This is equivalent to in the worst case.

Overall space complexity: .