Java Dequeue program using Java HackerRank solutions
Problem
You are given N integers. You need to find the maximum number of unique integers among all the possible contiguous subarrays of size M.
Note: Time limit is 3 second for this problem.
Input Format
The first line of input contains two integers N and M: representing the total number of integers and the size of the subarray, respectively. The next line contains N space separated integers.
Output Format
Print the maximum number of unique integers among all possible contiguous subarrays of size .
Sample Input
6 3
5 3 5 2 3 2
Sample Output
3
Solution
import java.util.*;
public class test {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque<Integer> deque = new ArrayDeque<>();
Set<Integer> uniqueElements = new HashSet<>();
int n = in.nextInt();
int m = in.nextInt();
int maxUnique = 0;
for (int i = 0; i < n; i++) {
int num = in.nextInt();
deque.addLast(num);
uniqueElements.add(num);
if (deque.size() == m) {
maxUnique = Math.max(maxUnique, uniqueElements.size());
int removedElement = deque.removeFirst();
if (!deque.contains(removedElement)) {
uniqueElements.remove(removedElement);
}
}
}
System.out.println(maxUnique);
}
}
Steps involved in this solution:
1. Begin by importing the required Java utilities, including tools for handling input and collections.
2. Create a Scanner for user input, a deque (double-ended queue) for the sliding window, and a set for tracking unique elements.
3. Prompt the user for input, specifically the total number of elements (n) and the subarray length (m).
4. Start a loop to iterate through each input element.
5. For each element, add it to the deque (sliding window) and the set (for tracking unique elements).
6. Check if the size of the sliding window (dequeue) reaches the specified subarray length (m). If so, update the maximum count of unique integers.
7. Remove the element at the start of the sliding window.
8. If the removed element was unique in the window, remove it from the set.
9. After processing all elements, print the maximum count of unique integers within any subarray of length m.
10. Close the Scanner to release resources.
