CODEWITHSUNDEEP
javaalgorithmdata-structuresqueue
Thaarik
Thaarik

Reputation: 63

Find the max element in all the contiguous subarray of size K using only queue

An array A and an integer K are given. We have to find the max element in all the contiguous subarrays of size K using only the queue in JAVA.

For example:

Input:
7 3
12 1 78 90 57 89 56

Output:
78 90 90 90 89

How can I solve this using only queue in Java?

Upvotes: 1

Views: 1004

Answers (1)

GURU Shreyansh
GURU Shreyansh

Reputation: 909

You can use Sliding Window technique to find the maximum element in all the contiguous subarrays of size K.
We need to use a PriorityQueue for this such that we can retrieve the max element of a particular window in constant time. First, add all the first K elements to queue and return the first max then iterate through the rest of the windows/sub-arrays of size K by just adding the new head and removing the tail of the window.
And at each iteration keep returning the peek (max) of current window.
Here is an implementation:

PriorityQueue<Integer> queue = 
new PriorityQueue<>(Collections.reverseOrder());
 
for (int i=0; i < K; i++)
    queue.add(arr[i]);
 
System.out.println(queue.peek()); // maximum element among first `K` elements
 
// Rest of the windows of size `K`
for (int i=K; i < N; i++)
{
    queue.remove(arr[i - K]); // first element from front
    queue.add(arr[i]);       // adding current element
    System.out.println(queue.peek()); // maximum element in current window
}

Upvotes: 2

Related Questions