We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Java
  3. Data Structures
  4. Java Dequeue
  5. Discussions

Java Dequeue

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 185 Discussions, By:

votes

Please Login in order to post a comment

  • 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);
        }
    }
    
    101|
    Permalink
  • 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.

    50|
    Permalink
  • 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);
        }
    }
    
    16|
    Permalink
  • 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);
    	}
    }
    
    8|
    Permalink
  • 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)

    5|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature