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.
I was timing out on a few of the test cases, even using two hashmaps. I tried the optimization of boilerplate code proposed here, and was still timing out on 10 which, to be fair, has a million operations. So to really turbocharge it, you can pass a BufferedReader to your freqQuery function, and rather than pass in an int array[q][2], undertake your operations as you read them line by line, so you only do a single pass.
My code - if there's another optimization I missed, please feel free to point it out to me.
importjava.io.*;importjava.math.*;importjava.security.*;importjava.text.*;importjava.util.*;importjava.util.concurrent.*;importjava.util.function.*;importjava.util.regex.*;importjava.util.stream.*;importstaticjava.util.stream.Collectors.joining;importstaticjava.util.stream.Collectors.toList;publicclassSolution{// Complete the freqQuery function below.staticList<Integer>freqQuery(BufferedReaderbufferedReader,intq)throwsIOException{HashMap<Integer,Integer>valuesToCounts=newHashMap<>();HashMap<Integer,Set<Integer>>countsToValues=newHashMap<>();ArrayList<Integer>results=newArrayList<>();intsize=q;for(inti=0;i<q;i++){String[]query=bufferedReader.readLine().split(" ");intoperation=Integer.parseInt(query[0]);intnumber=Integer.parseInt(query[1]);intoldCount=valuesToCounts.getOrDefault(number,0);intnewCount;if(operation==1){newCount=oldCount+1;valuesToCounts.put(number,newCount);if(countsToValues.containsKey(oldCount)){countsToValues.get(oldCount).remove(number);}countsToValues.putIfAbsent(newCount,newHashSet<>());countsToValues.get(newCount).add(number);}if(operation==2){newCount=(oldCount>1)?oldCount-1:0;valuesToCounts.put(number,newCount);if(countsToValues.containsKey(oldCount)){countsToValues.get(oldCount).remove(number);}countsToValues.putIfAbsent(newCount,newHashSet<>());countsToValues.get(newCount).add(number);}if(operation==3){if(number>size)results.add(0);else{results.add((number==0||countsToValues.getOrDefault(number,Collections.emptySet()).size()>0)?1:0);}}}returnresults;}publicstaticvoidmain(String[]args)throwsIOException{try(BufferedReaderbufferedReader=newBufferedReader(newInputStreamReader(System.in))){intq=Integer.parseInt(bufferedReader.readLine().trim());List<Integer>ans=freqQuery(bufferedReader,q);try(BufferedWriterbufferedWriter=newBufferedWriter(newFileWriter(System.getenv("OUTPUT_PATH")))){bufferedWriter.write(ans.stream().map(Object::toString).collect(joining("\n"))+"\n");}}}}
Frequency Queries
You are viewing a single comment's thread. Return to all comments →
I was timing out on a few of the test cases, even using two hashmaps. I tried the optimization of boilerplate code proposed here, and was still timing out on 10 which, to be fair, has a million operations. So to really turbocharge it, you can pass a BufferedReader to your freqQuery function, and rather than pass in an int array[q][2], undertake your operations as you read them line by line, so you only do a single pass.
My code - if there's another optimization I missed, please feel free to point it out to me.