Discussion on Java Dequeue Challenge

Sort 185 Discussions, By:

readyready15728 4 years ago+ 0 comments

This is fast enough though I thought it wouldn't be:

import java.util.*;

public class test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Integer> 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 = deque.remove();
                if (!deque.contains(first)) set.remove(first);
            }
        }
        
        System.out.println(max);
    }
}

amberberiwal 5 years ago+ 0 comments

I thought of both editorial solution and hashmap solution but as the question belongs to dequeue category, I tried to get an answer using dequeue and couldn't make any logic. Then, I checked the editorial and I am really disappointed that it is not up to the mark.

This question does not belong to dequeue. Even, editorial have just used dequeue for no purpose. An array or hashmap would be sufficient. I must say that if you are putting a question under some category then atleast make that category applicable.

RodneyShag 4 years ago+ 0 comments

Java solution - passes 100% of test cases

From my HackerRank solutions.

Runtime: O(n) using HashMap and Deque.
Space Complexity: O(n)

public class test {
    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();
        Deque<Integer> deque          = new ArrayDeque<>();
        
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();        
        int max = map.size();
        
        for (int i = 0; i < n; i++) {
            /* Remove old value (if necessary) */
            if (i >= m) {
                int old = deque.remove();
                if (map.get(old) == 1) {
                    map.remove(old);
                } else {
                    map.put(old, map.get(old) - 1);
                }
            }
            /* Add new value */
            int num = scan.nextInt();
            deque.add(num);
            map.merge(num, 1, Integer::sum);
            
            max = Math.max(max, map.size());
						
            /* If all integers are unique, break out of loop */
            if (max == m) {
                break;
            }
        }
        
        scan.close();
        System.out.println(max);
    }
}

KayKaySea 4 years ago+ 0 comments

My solution:

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();
		int max = 0;
		HashSet hs = new HashSet();

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

			deque.add(num);
			hs.add(num);

			if (deque.size() == m + 1) {

				int q_out = (int) deque.remove();

				if (!deque.contains(q_out)) {
					hs.remove(q_out);

				}

			}

			max = Math.max(hs.size(), max);

		}
		System.out.println(max);
	}
}

tliz007 4 years ago+ 0 comments

We can do a little better if we stop the loop at any point if the number of uniques == m. (Since we can't do better)

Load more conversations