Sort by

recency

|

340 Discussions

|

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

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