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.
Loading...
  1. Frequency Queries
  2. Discussions

Frequency Queries

  • toria_gibbs + 3 comments

    Same! The new boilerplate fixed 9, 11 but 10, 12, 13 still failing. I even tried taking OP's suggestion a step further and changed the boilerplate to int[q][2] (instead of just List<int[2]>) and still times out. Bummer.

    • oscards + 0 comments

      Changing to 2-D array worked for me

    • ferlenbusch + 2 comments

      I kept adjusting my code, and got my solution to O(n), where n = number of queries, and it still didn't pass test case 10 due to time out. Cut out a bunch of fat from the Boilerplate, and finally got it everything to pass with my solution. Here's what I ended up with for my boilerplate: 


      public static void main(String[] args) throws IOException {
        try (BufferedReader bufferedReader = new BufferedReader(
                    new InputStreamReader(System.in))) {
            
            int q = Integer.parseInt(bufferedReader.readLine().trim());
            int[][] queries = new int[q][2];
           
            for (int i = 0; i < q; i++) {
                String[] query = bufferedReader.readLine().split(" ");
                queries[i][0] = Integer.parseInt(query[0]);
                queries[i][1] = Integer.parseInt(query[1]);
            }
          
            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");
            }
        }
    }


      Solution method does need to take in int[][] instead of List<List<Integer>>

      • avinash_mv + 1 comment

        Thanks, Finally this worked for me. I used two maps one to track values and another to track frequencies. I don't know why hackerrack adds boiler plate code if it's so bad.

      • masterpradip + 0 comments

        Didn't work for me!

    • bob_perry + 0 comments

      For me, setting the intitital capacity of the maps made the difference between the 1000000 query tests timing out vs. passing...

      static List freqQuery(int[][] queries) {

          int qs = queries.length;

    // maps values and their frequencies
    // setting the initial capacity to qs was key to not timing out
    Map<Integer, Integer> map = new HashMap<>(qs);

    // maps frequencies and number of values which have that frequency
    // setting the initial capacity to qs was key to not timing out
    Map<Integer, Integer> freqMap = new HashMap<>(qs);