Java Dequeue HackerRank Solution

byAfzal Imam •
0

Java Dequeue HackerRank Solution

Hello Friends, How are you? Today I am going to solve the HackerRank Java Dequeue Problem with a very easy explanation. In this article, you will get more than one approach to solve this problem. So let's start-

{tocify} $title={Table of Contents}

Java Dequeue HackerRank Solution

HackerRank Java Dequeue Solution - Problem Statement

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 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 seconds 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 <=10000
  • 1<= M <=10000
  • M<=N
  • The numbers in the array will range between [1, 100000].

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 {codeBox}

Sample Output

3 {codeBox}

Explanation

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

s1 = (5, 3, 5) - Has 2 unique numbers.
s2 = (3, 5, 2) - Has 3 unique numbers.
s3 = (5, 2, 3) - Has 3 unique numbers.
s4 = (2, 3, 2) - Has 2 unique numbers.

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

Java Dequeue HackerRank Solution

Java Dequeue - Hacker Rank Solution

Approach I: Java Dequeue Solution HackerRank

// ========================
//       Information
// ========================

// Name: Java Dequeue HackerRank Problem
// Direct Link: https://www.hackerrank.com/challenges/java-dequeue/problem
// Difficulty: Medium
// Max Score: 20
// Language: Java 8

// ========================
//         Solution Start
// ========================

// Java Dequeue - Hacker Rank Solution Start

import java.util.*;

public class test {
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque deque = new ArrayDeque<>();
        HashSet<Integer> set = new HashSet<>();

        int n = in.nextInt();
        int m = in.nextInt();
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int input = in.nextInt();

            deque.add(input);
            set.add(input);

            if (deque.size() == m) {
                if (set.size() > max)
                    max = set.size();

                int first = (int) deque.remove();
                if (!deque.contains(first))
                    set.remove(first);
            }
        }
        System.out.println(max);
    }
}

// Java Dequeue Hacker Rank Solution END
// MyEduWaves

Approach II: Java Dequeue Solution HackerRank

// ========================
//       Information
// ========================

// Name: Java Dequeue HackerRank Problem
// Direct Link: https://www.hackerrank.com/challenges/java-dequeue/problem
// Difficulty: Medium
// Max Score: 20
// Language: Java 8

// ========================
//         Solution Start
// ========================

// Java Dequeue - Hacker Rank Solution Start

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.HashMap;
    
//  Time Complexity: O(n)
// Space Complexity: O(n)

public class test {
    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap();
        ArrayDeque<Integer> 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);
    }
}

// Java Dequeue Hacker Rank Solution END
// MyEduWaves

Disclaimer: The above Problem ( Java Dequeue ) is generated by Hackerrank but the Solution is Provided by MyEduWaves. This tutorial is only for Educational and Learning purposes. Authority if any of the queries regarding this post or website fill the contact form.

I hope you have understood the solution to this HackerRank Problem. All these three solutions will pass all the test cases. Now visit Java Dequeue Hackerrank Problem and try to solve it again.

All the Best!
Tags:

Post a Comment

Previous Post Next Post