Maximum of all subarrays of size k

problem statement : https://practice.geeksforgeeks.org/problems/maximum-of-all-subarrays-of-size-k3101/1

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

Example 1:

Input:
N = 9, 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

Example 2:

Input:
N = 10, 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

Your Task:

You don't need to read input or print anything. Complete the function max_of_subarrays() which takes the array, N and K as input parameters and returns a list of integers denoting the maximum of every contiguous subarray of size K.

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(K)

Constraints:
1 ≤ N ≤ 105
1 ≤ K ≤ N
0 ≤ arr[i] ≤ 107

Solution

class Solution
{
    //Function to find maximum of each subarray of size k.
    static ArrayList <Integer> max_of_subarrays(int a[], int n, int k)
    {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        ArrayList<Integer> res = new ArrayList<>();

        for(int i = 0; i < k-1; i++) {
            queue.offer(a[i]);
        }

        for(int i = k-1; i < n; i++) {
            queue.offer(a[i]); // considering new element
            res.add(queue.peek());
            queue.remove(a[i-k+1]); // removing the last left out element
        }

        return res;
    }
}

Comments

[Kostas Kalafatis]

Thank you for sharing your solution to the problem of finding the maximum for each and every contiguous subarray of size K. Overall, your code seems to be correct and efficient, but there are a few things that could be improved.

Firstly, it would be helpful to use more descriptive variable names. Instead of a, n, and k, it would be better to use more meaningful names like array, size, and subarraySize. This will make the code easier to read and understand for other developers.

Secondly, it is important to indicate that the method can throw an exception, especially because it is dealing with a collection. Therefore, it is better to add the throws keyword followed by an exception type like NullPointerException to the method signature.

Additionally, it would be helpful to explain how the algorithm works in the code comments, or even better, write a blog post around the solution and not just dump the code. Although the code is relatively simple and easy to understand, some explanation can make it easier to follow and can help other developers learn from it.

Finally, it is worth noting that the space complexity of the algorithm is O(k) because we are using a priority queue to store the maximum element of each subarray. This is within the expected auxiliary space constraints, but it is still important to consider. Also, the time complexity of the algorithm is O(n log k) because inserting and removing elements from a priority queue takes O(log k) time. However, we are iterating over the array only once, which is efficient and meets the expected time complexity constraints.

Thank you again for sharing your solution. With these improvements, the code will be more readable, understandable, and helpful for other developers.