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

We can optimize the space a little bit by avoiding the hashmap all together, but it seems like Hackerrank does not care about that. Any how I am putting my solution here which can solve this problem by using using a map.

private int countUniqueNumsInSubarrays(int[] nums, int m) {
        Deque<Integer> deque = new LinkedList<>();

        int maxUniqueCount = 0;

        for (int i = 0; i < nums.length; i++) {
            // if deque's left entry is outside the window then pop it out
            while (!deque.isEmpty() && i - deque.peekFirst() >= m) {
                deque.removeFirst();
            }

            // this will make sure that the deque only contains unique numbers,
            // this is essentially helps us avoid that extra hash map  
            while (!deque.isEmpty() && nums[deque.peekLast()] == nums[i]) {
                deque.removeLast();
            }

            deque.addLast(i);

            if (i >= m - 1) {
                maxUniqueCount = Math.max(maxUniqueCount, deque.size());
            }
        }

        return maxUniqueCount;
    }

Answer 3

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);
}

Answer 4

import java.util.*;
public class test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Integer> deque = new ArrayDeque<>();
        int n = in.nextInt();
        int m = in.nextInt();
        int maxUnique = 0;
        Map<Integer, Boolean> uniqSet = new HashMap<>();
        for (int i = 0; i < n; i++) {
          int num = in.nextInt();
           deque.addLast(num);
           uniqSet.put(num, true);
           if(deque.size() == m){
            //  int uniqueSize = new HashSet<>(deque).size();
            int uniqueSize = uniqSet.size();
             maxUnique = Math.max(maxUnique, uniqueSize);
  
             int x = deque.removeFirst();
             if(!deque.contains(x)){
               uniqSet.remove(x);
             }
           }
        }
        in.close();
        System.out.println(maxUnique);
    }
}

Answer 5

Instead of trying to remove elements from hashSet, we only remove elements from deque that are no longer in the window. If an element is not present in the deque, it means it is no longer within the window, so we remove it from hashSet.

We check if hashSet.size() is greater than max to update the maximum count of unique elements.

public class test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque deque = new ArrayDeque<Integer>();
        HashSet hashSet = new HashSet<Integer>();
        int n = in.nextInt();
        int m = in.nextInt();
        int max = 1; 
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            deque.add(num);
            hashSet.add(num);
            if (i >= m-1) {
                if (hashSet.size() > max) max = hashSet.size();
                int removeElement = (Integer)deque.remove();
                if (!deque.contains(removeElement)) {
                    hashSet.remove(removeElement);
                }
            }
        }
        System.out.println(max);
    }
}

Answer 6

import java.io.*;

import java.util.*; import java.util.stream.Stream;

public class Solution {

public static void main(String[] args) {
    var sc = new Scanner(System.in);
    
    var split = sc.nextLine().split(" ");
    int n = Integer.parseInt(split[0]);
    int m = Integer.parseInt(split[1]);
    
    if (!(1 <= n && n <= 100_000)) {
        System.exit(0);
    }
    if (!(1 <= m && m <= 100_000)) {
        System.exit(0);
    }
    if (!(m <= n)) {
        System.exit(0);
    }
    
    split = sc.nextLine().split(" ");
    
    sc.close();
    int maxNumUniqueInt = 0;
    HashSet<Integer> dist = new HashSet<>();
    Deque<Integer> deque = new ArrayDeque<>();
    int[] arr = Stream.of(split).mapToInt(Integer::parseInt).toArray();
    
    for (int i = 0; i < m; i++) {
        deque.addLast(arr[i]);
        dist.add(arr[i]);
    }
    int num = dist.size();
    if (maxNumUniqueInt < num) {
        maxNumUniqueInt = num;
    }
    for (int i = m; i < n; i++) {
        deque.addLast(arr[i]);
        dist.add(arr[i]);
        int remove = deque.removeFirst();
        if (!deque.contains(remove)) {
            dist.remove(remove);
        }
        num = dist.size();
        if (maxNumUniqueInt < num) {
            maxNumUniqueInt = num;
        }
       // System.out.println(i + "  |  " + deque + "  |  " + dist + "  |  " + maxNumUniqueInt);
    }
    
    System.out.println(maxNumUniqueInt);
}

}