Frequency Queries

  • + 54 comments

    For Java 7/8, change the boilerplate code to this

    public static void main(String[] args) throws IOException {
        try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))) {
          int q = Integer.parseInt(bufferedReader.readLine().trim());
          List<int[]> queries = new ArrayList<>(q);
          Pattern p  = Pattern.compile("^(\\d+)\\s+(\\d+)\\s*$");
          for (int i = 0; i < q; i++) {
            int[] query = new int[2];
            Matcher m = p.matcher(bufferedReader.readLine());
            if (m.matches()) {
              query[0] = Integer.parseInt(m.group(1));
              query[1] = Integer.parseInt(m.group(2));
              queries.add(query);
            }
          }
          List<Integer> ans = freqQuery(queries);
          try (BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")))) {
            bufferedWriter.write(
                    ans.stream()
                            .map(Object::toString)
                            .collect(joining("\n"))
                            + "\n");
          }
        }
      }
    

    and note each query is now an int[2] instead of a List. The method to implement is then

    static List<Integer> freqQuery(List<int[]> queries) {
    

    Reduced the run time in inputs 9 and 13 from ~1.7s (i7-4710MQ CPU @ 2.50GHz) to ~0.8s, and all cases pass now.