- Practice
- Java
- Data Structures
- Java Dequeue
- Discussions
Java Dequeue
Java Dequeue
readyready15728 + 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 + 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 + 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 + 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 + 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)
Sort 185 Discussions, By:
Please Login in order to post a comment