Java Dequeue HackerRank Solution with Example

HackerRank Solution for Java Dequeue Problem

Problem Description :

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

Sample 1 :

Input :

6 3
5 3 5 2 3 2

Output :

3

Explanation :

In the sample testcase, there are 4 subarrays of contiguous numbers.

a1 = [5 3 5] - Has unique 2 numbers.
a2 = [3 5 2] - Has unique 3 numbers.
a3 = [5 2 3] - Has unique 3 numbers.
a4 = [2 3 2] - Has unique 2 numbers.

in these subarrays, there are 2, 3, 3, 2 unique numbers, respectively. The maximum amount of unique numbers among all possible contiguous subarrays is 3.

Sample 2 :

Input :

6 3
5 9 8 6 8 7 4 2 3 3

Output :

5

Explanation :

a1 = [5 9 8 6 8] - Has unique 4 numbers.
a2 = [9 8 6 8 7] - Has unique 4 numbers.
a3 = [8 6 8 7 4] - Has unique 4 numbers.
a4 = [6 8 7 4 2] - Has unique 5 numbers.
a5 = [8 7 4 2 3] - Has unique 5 numbers.
a6 = [7 4 2 3 3] - Has unique 4 numbers. 

in these subarrays, there are 4, 4, 4, 5, 5, 4 unique numbers, respectively. The maximum amount of unique numbers among all possible contiguous subarrays is 5.

Before you jump on code, first learn about Queue interface in Java :

• Queue interface in Java with examples | Collection Interface
  

import java.util.*;

public class test {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque deque = new ArrayDeque<>();
        int n = in.nextInt();
        int m = in.nextInt();
        long maxCount = 0;
        Set<Integer> set = new LinkedHashSet<>();
     
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            deque.add(num);
            set.add(num);

            if (deque.size() == m) {
                if (set.size() > maxCount) {
                    maxCount = set.size();
                }
               
                int removed = (int) deque.remove();
               
                if (!deque.contains(removed)) {
                    set.remove(removed);
                }
            }
        }
        System.out.println(maxCount);
    }
}

Code Explanation :

• Here we have already defined Queue . Now define Set and initialize with LinkedHashSet (we can initialize with HashSet also).
• We take N as Queue size and M as sub array size.
• Loop through 0 to N (queue size).
  
• Now add user input into both Queue and Set.
• We perform operation if queue size becomes same as M (Sub array size).
• In set, only unique elements are stored. so we check size of set and if its size greater than maxCount variable then store set size into maxCount. (As we have to print answer of maximum number of unique integers among all possible contiguous subarrays).
• Now, remove head element of Queue. (remove() method return head as queue follows FIFO order).
• Now, remove element from Set that are not duplicate in Queue. Lets take example,
• Queue = [5, 3, 5], Set = [5, 3]. Now 5 is present 2 times in Queue and 1 time in Set. Now if remove 5 from Queue and Set also then we will get wrong output. Because 5 present 1 times in Set.
• Print maxCount.

Output Explanation :

Queue = [5, 3, 5, 2, 3, 2], n = 6, m = 3

• For loop, i = 0
• deque = [5], set = [5]
• i = 1
  
• deque = [5, 3], set = [5, 3]
• i = 2
• deque = [5, 3, 5], set = [5, 3]
• deque.size() == m | 3 = 3 becomes true
• set.size() > maxCount | 2 > 0 becomes true
• maxCount = 2
•  removed = deque.remove() | removed = 5 
• !deque.contains(removed) | queue contains 5 | becomes false
  
• i = 3, maxCount = 2
• deque = [3, 5, 2], set = [5, 3, 2]
• deque.size() == m | 3 = 3 becomes true
• set.size() > maxCount | 3 > 0 becomes true
• maxCount = 3
•  removed = deque.remove() | removed = 3
  
• !deque.contains(removed) | queue does contains 3 | becomes true
• set.remove(3) | set = [5, 2]
  
• i = 4, maxCount = 3
• deque = [5, 2, 3], set = [5, 2, 3]
• deque.size() == m | 3 = 3 becomes true
• set.size() > maxCount | 3 > 3 becomes false
• removed = deque.remove() | removed = 5
  
• !deque.contains(removed) | queue does contains 5 | becomes true
• set.remove(5) | set = [2, 3]
  
• i = 5, maxCount = 3
• deque = [2, 3, 2], set = [2, 3]
• deque.size() == m | 3 = 3 becomes true
• set.size() > maxCount | 3 > 2 becomes false
• removed = deque.remove() | removed = 2
  
• !deque.contains(removed) | queue contains 2 | becomes false
• i = 6 | 6 < 6 becomes false
• maxCount = 3 

We can also solve this problem without Set, but its give Timeout error in some HackeRank test cases. But as learning purpose we can refer that.

    for (int i = 0; i < n; i++) {
       
        int num = in.nextInt();
        deque.add(num);
       
        if (deque.size() == m) {
           
            long count = deque.stream().distinct().count();
            maxCount = count > maxCount ? count : maxCount;
         
            if (count > maxCount) {
                maxCount = count;
            }
          deque.pollLast();
        }
    }
    System.out.println(maxCount);

Related articles :

• Count Triplets HackerRank solution in Java with Explanation (Dictionaries and Hashmaps Problem)
• How to print Pascal's Triangle by given index | Pascal's Triangle II LeetCode Solution