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);