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.
  1. Prepare
  2. Java
  3. Data Structures
  4. Java Dequeue
  5. Discussions

Java Dequeue

Sort by

recency

|

340 Discussions

|

  • salonigoel97
     + 0 comments

    O(n)

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

            for (int i = 0; i < n; i++) {
                int num = in.nextInt();
                deque.addLast(num);
            }
            
            Map<Integer, Integer> hs = new HashMap<>();
            int maxsize = 0;
            int c = 0;
            
            for (int i: deque) {
                
                if (c < m) {
                    int prev = hs.getOrDefault(i, 0);
                    hs.put(i, prev + 1);   
                } else {
                    // remove first
                    int elemfirst = deque.pollFirst();
                    int prevcount = hs.getOrDefault(elemfirst, 0);
                    if (prevcount > 1) {
                        hs.put(elemfirst, prevcount - 1);
                    } else {
                        hs.remove(elemfirst);
                    }
                    
                    // add new
                    int prev = hs.getOrDefault(i, 0);
                    hs.put(i, prev + 1);
                }
                
                maxsize = Math.max(maxsize, hs.size());
                if (maxsize == m) {
                    System.out.println(m);
                    return;
                }
                
                c++;
            }
            
            System.out.println(maxsize);
        }
    }

  • akshatjhansi1
     + 0 comments

    Time Complexity : O(n)

    import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        var max = 0;
        var s = new Scanner(System.in);
        var integerList = new ArrayDeque<>();
        var n = s.nextInt();
        var m = s.nextInt();
        var freqMap = new HashMap<Integer,Integer>();
        
        for(int i = 0; i < n ; i++){
            var num = s.nextInt();
            integerList.addLast(num);
            freqMap.put(num,freqMap.getOrDefault(num, 0) + 1);
            // System.out.println("queue before : " + integerList + " HashMap : " + freqMap);
            //make sure the window size is maintained
            if(integerList.size()> m){
                var removed = (Integer) integerList.removeFirst();
                freqMap.put(removed, freqMap.getOrDefault(removed, 0) - 1);
                if(freqMap.get(removed) == 0){
                    freqMap.remove(removed);
                }
            }
            // System.out.println("queue After : " + integerList + " HashMap : " + freqMap);
            //check for max
            if(integerList.size() == m){
                max = Math.max(freqMap.size(),max);
            }
        }
        s.close();
        
        System.out.println(max);
    }
}

  • BrendaLando45
     + 0 comments

    This is a really clear introduction to deques and their usage. I like how it shows both LinkedList and ArrayDeque implementations — it helps beginners see the options available in Java. funinexchange247

  • sumit_next21
     + 1 comment

    simplest logic

    Scanner in = new Scanner(System.in);
            Deque<Integer> deque = new ArrayDeque<>();
            
            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);
                if(deque.size()==m){
                    int size = new HashSet<Integer>(deque).size();
                    if(max<size) max = size;
                    deque.removeFirst();
                }
            }
            in.close();
            System.out.println(max);

  • tusharvyavahare1
     + 0 comments
    public class Solution {

    public static void main(String[] args) {
      Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      int m=sc.nextInt();
      Deque<Integer> deq=new ArrayDeque<>();
      Map<Integer,Integer> hm=new HashMap<>();
      int res=0;
      for(int i=0;i<n;i++){
        int ele=sc.nextInt();
        deq.offerLast(ele);
        hm.put(ele,hs.getOrDefault(ele, 0)+1);
        if(deq.size()==m){
            res=Math.max(res, hm.size());
            int out=deq.pollFirst();
            int count=hm.get(out);
            if(count==1){
                hm.remove(out);
            }else{
                hm.put(out,hs.get(out)-1);
            }
            
        }
      }
      System.out.println(res);
    }
}