DEV Community

Aniket Vaishnav
Aniket Vaishnav

Posted on

2

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Image of Docusign

Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (1)

Collapse
 
kalkwst profile image
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.

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay