Skip to main content

Java Dequeue

Problem
In computer science, a double-ended queue (dequeue, often abbreviated to deque, pronounced deck) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Deque interfaces can be implemented using various types of collections such as LinkedList or ArrayDeque classes. For example, deque can be declared as:

Deque deque = new LinkedList<>();
or
Deque deque = new ArrayDeque<>();

In this problem, you are given NN integers. You need to find the maximum number of unique integers among all the possible contiguous subarrays of size MM.

Note: Time limit is 33 second for this problem.

Input Format

The first line of input contains two integers NN and MM: representing the total number of integers and the size of the subarray, respectively. The next line contains NN space separated integers.

Constraints

1≤N≤1000001≤N≤100000
1≤M≤1000001≤M≤100000
M≤NM≤N
The numbers in the array will range between [0,10000000][0,10000000].

Output Format

Print the maximum number of unique integers among all possible contiguous subarrays of size MM.

Sample Input

6 3
5 3 5 2 3 2

Sample Output

3

Explanation

In the sample testcase, there are 4 subarrays of contiguous numbers.

s1=⟨5,3,5⟩s1=⟨5,3,5⟩ - Has 22 unique numbers.

s2=⟨3,5,2⟩s2=⟨3,5,2⟩ - Has 33 unique numbers.

s3=⟨5,2,3⟩s3=⟨5,2,3⟩ - Has 33 unique numbers.

s4=⟨2,3,2⟩s4=⟨2,3,2⟩ - Has 22 unique numbers.

In these subarrays, there are 2,3,3,22,3,3,2 unique numbers, respectively. The maximum amount of unique numbers among all possible contiguous subarrays is 33.

Solution
    import java.util.*;
    public class test {
       public static void main(String[] args){
           
    Scanner in = new Scanner(System.in);
    Deque q    = new ArrayDeque<Integer>();
    int []a = new int[10000001];
    int i = 0, n = in.nextInt(), m = in.nextInt();
    int r = 0, c = 0;
           
    for(;i<m;i++){
    int x = in.nextInt();
    if(a[x]==0){c++;if(r<c)r=c;}
    a[x]++;
    q.addLast(x);
    }
           
    for(;i<n;i++){
    if(a[(int)q.getFirst()]==1)c--;
    a[(int)q.getFirst()]--;
    q.removeFirst();
    int x=in.nextInt();
    if(a[x]==0){c++;if(r<c)r=c;}
    a[x]++;
    q.addLast(x);
    }
           
    System.out.println(r);
    }
    }

Comments

Popular posts from this blog

ജാവാ വളരെ സിമ്പിൾ ആണ് , പവർഫുൾ ഭയങ്കര പവർഫുൾ ആണ്.

ജാവ യെ  കുറിച്ച്  മലയാളത്തിൽ  ഡോകുമെന്റുകളോ  ബ്ലോഗ്‌കളോ  കൂടുതൽ ഇല്ലാത്തതുകൊണ്ട് എനികറിയവുന്നത് ഷെയർ ചെയ്യാം എന്ന് വിചാരിച്ചു .  ജവയെ കുറിച്ച് പറയുകയാണെങ്കിൽ  ജാവാ വളരെ സിമ്പിൾ ആണ് , പവർഫുൾ  ഭയങ്കര പവർഫുൾ ആണ്. :) 1. നമ്മടെ Sun MicroSystems 1995 ൽ തുടങ്ങി വച്ചാ സംഭവമാണിത് . 2. ഇപ്പൊ ജാവയുടെ എട്ടാമത്തെ വെർഷൻ  വരെ ഇറങ്ങികഴിഞ്ഞു . ജാവയുടെ തിയറിയെ കുറിച്ച് എനിക്ക് പറയാൻ താല്പര്യം  ഇല്ലാ, അത് അറിവിള്ളവർ നല്ലപോലെ പറഞ്ഞിടുണ്ട്. നമുക്ക് ഡയറക്റ്റ്  ആയി കോഡിംഗ് പാർട്ടിലേക്ക്  പോകാം. എങ്ങനെയാ ജാവ ഇൻസ്റ്റോൾ ചെയണ്ടേ എന്നൊക്കെ ഒന്ന് ഗൂഗിൾനോട് ചോദിച്ചാ മതി പുള്ളി പറഞ്ഞുതരും. പിന്നെ എല്ലാവരും പറയുന്നു ജാവാ Object  Oriented ആണെന്ന് . അതെ ജാവാ Object Oriented ആണ് . എന്താണ് Object ?, Object  നു വച്ചാ ഒരു സാധനം അത്രതന്നെ. ഇപ്പൊ example പറയുകയാണെങ്കിൽ Book ഒരു സാധനമാണ് . Book റ്റെ പ്രതേകത എന്തൊക്കെ അന്നെന്നുവച്ചാ ആതിനൊരു Auther ഉണ്ടാകും, അതൊരു Category ൽ പെട്ട book ആയിരിക്കും (Novel / Academic ) പിന്നെ ഓരോ bookനും അ...

Angular (web framework)

 Angular is a TypeScript-based free and open-source web application framework lead by the Angular Team at Google and by a community of individuals and corporations. Angular is a complete rewrite from the same team that built AngularJS. Google designed Angular as a ground-up rewrite of AngularJS. Angular 14 was released on June 02, 2022. Some new features include typed forms, standalone components, and new primitives in the Angular CDK (component dev kit). All the major releases are supported for 18 months.  This consists of 6 months of active support, during which regularly-scheduled updates and patches are released. It is then followed by 12 months of long-term support (LTS), during which only critical fixes and security patches are released. Official website :- https://angular.io/

Java String Token

Problem    Given a string, find number of words in that string.     For this problem a word is defined by a string of one or more english alphabets. Input Format   A string not more than 400000 characters long.    The string can be defined by following regular expression:       [A-Za-z !,?.\_'@]+   That means the string will only contain english alphabets,    blank spaces and this characters: "!,?._'@". Output Format   In the first line, print number of words nn in the string.    The words don't need to be unique. In the next nn lines,    print all the words you found in the order they appeared in the input. Sample Input   He is a very very good boy, isn't he? Sample Output 10 He is a very very good boy isn t he Solution import java.io.* ; import java.util.* ; public class Solution { ...