Algorithm


Problem Name: Java Dequeue

Problem Link: https://www.hackerrank.com/challenges/java-dequeue/problem?isFullScreen=true

In this HackerRank Functions in Java programming problem solution,

In 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).

 

Deque interfaces can be implemented using various types of collections such as LinkedList or ArrayDeque classes. For example, deque can be declared as:

 

Deque deque = new LinkedList<>();
or
Deque deque = new ArrayDeque<>();

 

You can find more details about Deque here.

In this problem, you are given N ntegers. You need to find the maximum number of unique integers among all the possible contiguous subarrays of size M .

Note: Time limit is 3 econd 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.

Constraints

  • 1 <= N <= 100000
  • 1 <= M <= 100000
  • M <= N

The numbers in the array will range between

[0, 10000000].

Output Format

Print the maximum number of unique integers among all possible contiguous subarrays of size M.

Sample Input

6 3
5 3 5 2 3 2

Sample Output

3

 

 

 

 

 

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.HashMap;

// Why not use just a HashMap instead of both a HashMap and an ArrayDeque? 
// Well, an ArrayDeque helps keep the ordering of elements. Although the 
// elements are also in our HashMap, they is no ordering to the elements 
// in the HashMap since it's just a set.
    
//  Time Complexity: O(n)
// Space Complexity: O(n)

public class test {
    public static void main(String[] args) {
        HashMap < Integer, Integer> map = new HashMap();
        ArrayDeque deque     = new ArrayDeque();
        
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int max = 0;
        
        for (int i = 0; i  <  n; i++) {
            /* Remove old value (if necessary) */
            if (i >= m) {
                int old = deque.removeFirst();
                if (map.get(old) == 1) {
                    map.remove(old);
                } else {
                    map.merge(old, -1, Integer::sum);
                }
            }
            
            /* Add new value */
            int num = scan.nextInt();
            deque.addLast(num);
            map.merge(num, 1, Integer::sum);
            
            max = Math.max(max, map.size());
            
            /* If all integers are unique, we have found our largest
               possible answer, so we can break out of loop */
            if (max == m) {
                break;
            }
        }
        
        scan.close();
        System.out.println(max);
    }
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Java Comparator in Java solution in Hackerrank - Hacerrank solution Java
Next
[Solved] Java Priority Queue in Java solution in Hackerrank - Hacerrank solution Java