Java Deque (Finding the max number of unique integers from subarrays.)

Question

I was trying to solve a HackerRank problem on Java Deque. My code passed all the cases apart from the ones which have 100,000 inputs.

Problem: 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. --->So we wre given N integers, and need to find the number of "unique integers" in each contagious subarray(of size M). And then print the maximum number of those "unique Integers".

link: https://www.hackerrank.com/challenges/java-dequeue/problem

My Code:

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=0;
            for (int i = 0; i < n; i++) {
                int num = in.nextInt();
                deque.add(num);
                set.add(num);
                if(i>=m-1){
                    if(set.size()>max)max=set.size();
                    Integer removed=(Integer)deque.removeFirst();
                    set.remove(removed);
                   set.add((Integer)deque.peek());
                }
                
            }
            System.out.println(max);
        }

Please tell me where my code went wrong.

Answer 1

What is the point of this line?

                   set.add((Integer)deque.peek());

I don't see anything in your code that is slow. I just wonder how you can keep track of unique numbers by using a set, given that a set only tells you if there is such a number (but not how many occurrences of the same number there are). And you don't want to keep scanning the deque to see if the number being removed is the last one.

I don't think this is great/fast code, but it seems to pass the test-cases. I keep a count of how many of each integer there is in the window by using a map (and use some of your code).

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Integer> deque = new ArrayDeque<>();
        HashMap<Integer, Integer> counts = new HashMap<>();
        int n = in.nextInt();
        int m = in.nextInt();
        int max = 0;
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            deque.add(num);
            int count = counts.getOrDefault(num, 0);
            counts.put(num, ++count);
            if (i >= m - 1) {
                if (counts.size() > max) max = counts.size();
                Integer removed = deque.removeFirst();
                int removing = counts.get(removed);
                removing--;
                if (removing == 0) {
                    counts.remove(removed);
                } else {
                    counts.put(removed, removing);
                }
            }
        }
        System.out.println(max);
    }

}

Answer 2

Just wanted to share how I solved it in case it helps.

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    Deque deque = new ArrayDeque();
    Set<Integer> integers = new HashSet<>();
    int n = in.nextInt();
    int m = in.nextInt();
    long result = 0;
    for (int i = 0; i < n; i++) {
        int num = in.nextInt();
        deque.add(num);
        integers.add(num);
        if (deque.size() == m) {
            long currentSize = integers.size();
            if (currentSize > result) {
                result = currentSize;
            }
            Integer removed = (Integer) deque.pollFirst();
            if (!deque.contains(removed)) {
                integers.remove(removed);
            }
        }
    }
    System.out.println(result);
}