K Sized Subarray Maximum

Given an array arr[] and an integer k. Find the maximum for each and every contiguous subarray of size k.

Examples:

Input: k = 3, arr[] = [1, 2, 3, 1, 4, 5, 2, 3, 6]
Output: [3, 3, 4, 5, 5, 5, 6] 
Explanation: 
1st contiguous subarray = [1 2 3] max = 3
2nd contiguous subarray = [2 3 1] max = 3
3rd contiguous subarray = [3 1 4] max = 4
4th contiguous subarray = [1 4 5] max = 5
5th contiguous subarray = [4 5 2] max = 5
6th contiguous subarray = [5 2 3] max = 5
7th contiguous subarray = [2 3 6] max = 6

Input: k = 4, arr[] = [8, 5, 10, 7, 9, 4, 15, 12, 90, 13]
Output: [10, 10, 10, 15, 15, 90, 90]
Explanation: 
1st contiguous subarray = [8 5 10 7], max = 10
2nd contiguous subarray = [5 10 7 9], max = 10
3rd contiguous subarray = [10 7 9 4], max = 10
4th contiguous subarray = [7 9 4 15], max = 15
5th contiguous subarray = [9 4 15 12], max = 15
6th contiguous subarray = [4 15 12 90], max = 90
7th contiguous subarray = {15 12 90 13}, max = 90

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(k)

Constraints:
1 ≤ sizeof(arr) ≤ 10⁶
1 ≤ k ≤ sizeof(arr)
0 ≤ arr[i] ≤ 10⁹

Approach 01:

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    vector<int> max_of_subarrays(int k , vector<int>& arr) {
        priority_queue<pair<int, int>> maxHeap;  // Max-heap to store elements and their indices
        vector<int> result;  // To store the maximums of each subarray

        // Push the first k-1 elements into the heap
        for (int index = 0; index < k - 1; ++index) {
            maxHeap.push({arr[index], index});
        }

        // Process the remaining elements
        for (int index = k - 1; index < arr.size(); ++index) {
            maxHeap.push({arr[index], index});  // Add the current element to the heap

            // Remove elements that are outside the current window (of size k)
            while (maxHeap.top().second <= index - k) {
                maxHeap.pop();
            }

            // The root of the heap contains the maximum element of the current window
            result.push_back(maxHeap.top().first);
        }

        return result;
    }
};

from heapq import heappop, heappush

class Solution:
    
    #Function to find maximum of each subarray of size k.
    def max_of_subarrays(self,k,arr):
        
        maxHeap = []  # Heap to store the negative of the elements (for max-heap behavior)
        
        # Push first k-1 elements into the heap
        for index in range(k - 1):
            heappush(maxHeap, (-arr[index], index))
        
        result = []  # To store the maximums of each subarray
        
        # Process the remaining elements
        for index in range(k - 1, len(arr)):
            heappush(maxHeap, (-arr[index], index))  # Add the current element to the heap
            
            # Remove elements that are outside the current window (of size k)
            while maxHeap[0][1] <= index - k:
                heappop(maxHeap)
            
            # The root of the heap contains the maximum element of the current window
            result.append(-maxHeap[0][0])
        
        return result

Time Complexity

• Heap Operations:

  Inserting an element into the heap takes \(O(\log k)\), where \(k\) is the window size. After adding each element, we remove outdated elements from the heap, which also takes \(O(\log k)\). Since these heap operations are performed for each element in the array, the time complexity for processing each element is \(O(\log k)\).

• Loop Iteration:

  The algorithm iterates through the entire array of size \(n\) exactly once, resulting in a time complexity of \(O(n)\).

• Overall Time Complexity:

  Since the heap operations are performed for each element, the overall time complexity is \(O(n \log k)\), where \(n\) is the number of elements in the array and \(k\) is the window size.

Space Complexity

• Auxiliary Space:

  The max-heap stores at most \(k\) elements at any given time (one element for each position in the sliding window). Therefore, the space complexity for the heap is \(O(k)\).

• Result Vector:

  The result vector stores \(n – k + 1\) elements, which corresponds to the number of subarrays, and thus takes \(O(n)\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(n + k)\), where \(n\) is the size of the input array and \(k\) is the size of the sliding window.