<\/span><\/h2>\n\n\n\nIn computer science, a double-ended queue (dequeue, often abbreviated to deque, pronounced deck) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).<\/p>\n\n\n\n
Deque interfaces can be implemented using various types of collections such as LinkedList or ArrayDeque classes. For example, deque can be declared as:<\/p>\n\n\n\n
Deque deque = new LinkedList<>();\n or\n Deque deque = new ArrayDeque<>();<\/code><\/pre>\n\n\n\nIn this problem, you are given N <\/em><\/strong>integers. You need to find the maximum number of unique integers among all the possible contiguous subarrays of size M<\/em><\/strong>.
Note: Time limit is 3 <\/em><\/strong>second for this problem.<\/p>\n\n\n\n<\/span>Input Format<\/strong><\/span><\/h2>\n\n\n\nThe first line of input contains two integers N <\/strong>and M<\/strong>: representing the total number of integers and the size of the subarray, respectively. The next line contains N <\/strong>space separated integers.<\/p>\n\n\n\n<\/span>Constraints<\/strong><\/span><\/h4>\n\n\n\n- 1 <= N <= <\/em><\/strong>100000<\/strong><\/em><\/li>
- 1 <= M <= <\/em><\/strong>100000<\/strong><\/em><\/li>
- M <= N<\/em><\/strong><\/li>
- The numbers in the array will range between [10000000]<\/strong>.<\/li><\/ul>\n\n\n\n
<\/span>Output Format<\/strong><\/span><\/h2>\n\n\n\nPrint the maximum number of unique integers among all possible contiguous subarrays of size M<\/strong>.<\/p>\n\n\n\n<\/span>Sample Input<\/strong><\/span><\/h4>\n\n\n\n 6 3\n 5 3 5 2 3 2<\/code><\/pre>\n\n\n\n<\/span>Sample Output<\/strong><\/span><\/h4>\n\n\n\n 3<\/code><\/pre>\n\n\n\n<\/span>Explanation<\/strong><\/span><\/h4>\n\n\n\nIn the sample testcase, there are 4 subarrays of contiguous numbers.<\/p>\n\n\n\n
- s1 = <5,3,5> – <\/em><\/strong>Has 2 <\/strong>unique numbers.<\/li>
- s2 = <3,5,2> – <\/em><\/strong>Has 3 <\/strong>unique numbers.<\/li>
- s3 = <5,2,3> – <\/em><\/strong>Has 3 <\/strong>unique numbers.<\/li>
- s4 = <2,3,2> – <\/em><\/strong>Has 2 <\/strong>unique numbers.<\/li><\/ul>\n\n\n\n
In these subarrays, there are 2,3,3,2 <\/em><\/strong>unique numbers, respectively. The maximum amount of unique numbers among all possible contiguous subarrays is 3<\/em><\/strong>.<\/p>\n\n\n\n<\/span>Solution –<\/strong> Java Dequeue<\/strong><\/span><\/h2>\n\n\n\nimport java.util.*;\n\npublic class test {\n public static void main(String[] args) {\n Scanner in = new Scanner(System.in);\n Deque<Integer> deque = new ArrayDeque<>();\n HashSet<Integer> set = new HashSet<>();\n \n int n = in.nextInt();\n int m = in.nextInt();\n int max = Integer.MIN_VALUE;\n\n for (int i = 0; i < n; i++) {\n int input = in.nextInt();\n \n deque.add(input);\n set.add(input);\n \n if (deque.size() == m) {\n if (set.size() > max) max = set.size();\n int first = deque.remove();\n if (!deque.contains(first)) set.remove(first);\n }\n }\n \n System.out.println(max);\n }\n}\n<\/pre>\n\n\n\n