I can confirm that changing the boilerplate code to this made all tests failing due to timeout pass.

Thanks!

Can also confirm that changing my (Java 8) boilerplate code to this made all tests that were failing due to timeout (Test cases 9 - 15) pass.

Thank you so much, and shame on HackerRank for providing bad boilerplate code!

I did this but still tests 10,12,13 fail due to timeout. Please help

my solution :

static List freqQuery(List queries) {

    HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
    List<Integer> retList = new ArrayList<Integer>();

    for(int i=0;i<queries.size();i++)
    {
        int op = queries.get(i)[0];
        int num = queries.get(i)[1];
        if(op==1)
        {
            if(!hash.containsKey(num))
                hash.put(num,1);
            else
                hash.put(num,hash.get(num)+1);
        }
        else
        if(op==2)
        {
            if(hash.containsKey(num))
            {
                if(hash.get(num)<=1)
                    hash.remove(num);
                else
                    hash.put(num,hash.get(num)-1);
            }

        }
        else
        if(op==3)
        {
            if(hash.containsValue(num)){
                retList.add(1);
            }
            else
                retList.add(0);

        }
    }

    return retList;
}

Thanks! Now tests 9-13 pass without "Terminated due to timeout" status with Java 8.

I agree with above comment.

I am getting compilation error in the main after changing my boilerplate code. Solution.java:63: error: ')' expected .map(Object::toString) ^

Solution.java:63: error: ';' expected .map(Object::toString) ^

Solution.java:63: error: not a statement .map(Object::toString) ^

Solution.java:63: error: ';' expected .map(Object::toString) ^

Solution.java:65: error: not a statement + "\n"); ^

Solution.java:65: error: ';' expected + "\n"); ^

That was very helpful. Thank you.

• Ramo

Good catch! I was hoping something like this was the case. I was pretty confident my implementation was O(1) for each of the query operations, but was still getting timeout errors for cases 9-13. After fixing the boilerplate code, all cases are passing. Thanks!

Hackerrank has so many issues... Thanks a ton! This made my test cases pass. My algorithm was linear and always used constant time access, so really this boiler plate code shouldn't matter if the tests are correct. I.E. they should be testing Big O not absolute time.

It's sad! I wasted hours trying to figure out why my tests were timing-out only to find out the bloddy boilerplate code as the culprit!

Very true. Saved further debugging time! I was wondering why its still failing instead my algorithm is quite efficient

I supposed, the result depends on server state. I have to rewrite output code and add inverse map to pass all tests.

Thank you. I didn't know why I had problems of timeout, but your change solved my problem. TY.

Thanks, the Java 8 harness is often joke tier but this one... I came to the discussions after measuring that the whole main method took 1600ms while my own code took 200ms for one of the failing cases.

Thanks, works for me!

Same for me. Solution is in O(n), this new boiler plate made me pass the tests immediately.

I was surprised that when I changed the boilerplate to use an array list presized to q, with elements that were array lists of size 2, I still couldn't beat the timeout. If anybody gets this to work with arraylist or list as the entries, I would be curious to see what they did in the boilerplate. Maybe above would work with compiled pattern but array list of array lists.... Maybe it's the time lost simply to allocate a wrapped integer instead of a primitive.

thank you. I was slowly getting pissed off but now everything passes.

Arrrrgh.... changed the function to take an int[], AND had it return an int[] (by counting the number of queries on input, and then passing that into the function) and am still timing out on 12 and 13. Stripped down my code so it now uses only a single non-primitive structure (one Map to keep track of the frequency of each number), and it's still not passing.

I'll have to come back to this one.

My solution was showing WA for test cases 9-13. Changing boiler plate code fixed it.

Thanks a lot @eduardocorral

Thank you! I was just coming to the discussion to complain how tests are timing out on my O(n) solution and it's not obvious how to optimize it to pass.

Yay, works great! Thanks @eduardocorral. Agreed, HackerRank should test their own code.

Thank you for this. Was there more optimizations that i should have made that could have passed? I went over all queries once and used 2 maps to count frequencies and then the number of occurances for a particular value.

confirm, thank you!

Thanks man:) I spent 2 hours trying to understand what else can be improved. Shame on hackerrank boilerplate.

I also confirm that changing the boilerplate code to this made all tests failing due to timeout pass. Thank you so much !

Thanks. Finally it's work for me.

Why changing to int[] make it faster? I changed the code and all the tests passed. I wonder why. Is it because intializing a list is slower than intializing an array? Or list.get() is slower than array[index]?

Test cases 10-13 were failing but after changing the boilerplate code to the above code, they passed. Thanks brother.!

Bless you. You code executes 2-3 times faster on my machine and I finally passed the tests

There are two more things have to be done before passing all test cases.

1. Use String.split() instead of pattern match.
2. Use 2D array instead of List<int[]> to store all queries.

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[] qs = bufferedReader.readLine().split(" ");
            queries[i][0] = Integer.parseInt(qs[0]);
            queries[i][1] = Integer.parseInt(qs[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");
        }
    }
}

Can you give me your code

For all those who were like me , trying to find solution for java.... just use the above one or fast IO (make sure u do the same justice with output also) with your own implementation........

OR

import java.io.; import java.util.; import static java.util.stream.Collectors.joining;

public class Solution { public static void main(String[] args) throws IOException {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter out = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    List<Integer> result = new ArrayList<>();
    int n = Integer.parseInt(in.readLine());
    HashMap<Long, Long> map = new HashMap<Long, Long>();
    HashMap<Long, Long> freq = new HashMap<Long, Long>();

    for (int i = 0; i < n; i++) {
        StringTokenizer s= new StringTokenizer(in.readLine());
        int a = Integer.parseInt(s.nextToken());
        final long b = Long.parseLong(s.nextToken());
        switch (a) {
            case 1:
                freq.computeIfPresent(map.get(b), (k, v) -> v == 1 ? freq.remove(map.get(b)) : v - 1);
                map.compute(b, (k, v) -> v == null ? 1 : v + 1);
                freq.compute(map.get(b), (k, v) -> v == null ? 1 : v + 1);
                break;
            case 2:
                freq.computeIfPresent(map.get(b), (k, v) -> v == 1 ? freq.remove(map.get(b)) : v - 1);
                map.computeIfPresent(b, (k, v) -> v == 1 ? map.remove(b) : v - 1);
                freq.compute(map.get(b), (k, v) -> v == null ? 1 : v + 1);
                break;
            case 3:
                result.add(freq.containsKey(b) ? 1 : 0);
                break;
        }
    }
    out.write(result.stream().map(Object::toString).collect(joining("\n")) + "\n");

    in.close();
    out.close();
}

}

Using Java 8 even with the change in the boiler plate my code timed out some test cases.

I switched to using Java 7 and all tests pass.

Thank you so much for this! I was beginning to pull my hair wondering why I was still getting timeouts after implementing a reverse HashMap to keep track of frequencies instead of calling values().contains()

Check my accepted c++ code here: https://www.hackerrank.com/challenges/frequency-queries/forum/comments/648137?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Thank you for pointing this out. Here is a c# version of boiler plate:

        static void Main(string[] args)
        {
                int q = Convert.ToInt32(Console.ReadLine().Trim());

                var queries = new int[q,2];

                for (int i = 0; i < q; i++)
                {
                    var nq = new int[2];
                    nq = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(queriesTemp => Convert.ToInt32(queriesTemp)).ToArray();
                    queries[i, 0] = nq[0];
                    queries[i, 1] = nq[1];
                }

                List<int> ans = freqQuery(queries);
                Console.WriteLine(String.Join("\n", ans));
        }

Why doesn't this code which runs in O(n) pass the test cases 10, 11, 12 and 13? It times out.

static List<Integer> freqQuery(List<int[]> queries) {
    List<Integer> result = new ArrayList<Integer>();
    HashMap<Integer, Integer> map = new HashMap<>();
    HashMap<Integer, Integer> freq = new HashMap<>();
    for (int[] q: queries) {
        System.out.println("\nIndex: " + _count ++);
        int x = q[0];
        int y = q[1];
        Integer count = map.getOrDefault(y, 0);
        Integer _freq = freq.getOrDefault(count, 0);            
        if (x == 1) {
            freq.put(count, _freq > 0 ? (_freq - 1): 0);
            freq.put(count + 1, freq.getOrDefault(count + 1, 0) + 1);
            map.put(y, count + 1);
        } else if (x == 2) {
            if (count != 0) {
                freq.put(count, _freq > 0 ? (_freq - 1): 0);
                freq.put(count - 1, freq.getOrDefault(count - 1, 0) + 1);
                map.put(y, count - 1);
            }
        } else if (x == 3) {
            result.add(freq.getOrDefault(y, 0) > 0 ? 1: 0);
        }
    }
    return result;
}

Thank you for calarifying this. I have spent a significant amount of time trying to come up with something better than O(n) . I have just changed the boilerplate code and have all test cases passing. My solution is O(n)

I can confirm that boilerplate in Java 8 is doing tests failling due to timeout. You can easily test it by submitting the code (without implementing the freqQuery method). Test 9 to 14 will fail due to timeout instead of wrong answer, like the others.

Thanks for the new boilerplate code!

Also, if someone still struggles with tests 12 and 13 due to timeout, use: List<Integer> result = new ArrayList<>(queries.size()); instead of List<Integer> result = new LinkedList<>();.

Of course we potentially allocate unnecessary memory in ArrayList (if queries contains other operations than operation 3), but this tric is to pass those tests. I.e. LinkedList will be better only with small amount of operations 3.

Thanks a bunch! I was lossing my mind trying to think of a sub linear solution. After first reading your comment I ran a submission with all my code commented out, still went over time.

Nice way to use Counter, I didn't know you can use it like that. But I tested it with 1000000 queries against defaultdict and defaultdict is around 15-20% faster. I guess both of them using a lot of memory but as a dictionaries and hashmaps problem it's not so important here.

Very clever! I had trouble looking up if a particular frequency existed without timing out; this is (in my opinion) a very elegant solution!

Great job! I'm gonna remember the double hash trick for the future!

Nice work. In my code taste I would just suggest extracting command and value for less square brackets => better readability and simplify result else f.e. like:

#!/bin/python
import os
from collections import Counter

def freqQuery(queries):
    freq = Counter()
    cnt = Counter()
    result = []
    for action, value in queries:
        if action == 1:
            cnt[ freq[value] ] -= 1
            freq[value] += 1
            cnt[ freq[value] ] += 1
        elif action == 2:
            if freq[value] > 0:
                cnt[ freq[value] ] -= 1
                freq[value] -= 1
                cnt[ freq[value] ] += 1
        else:
            result.append(1 if cnt[value] > 0 else 0)
    return result

if __name__ == '__main__':
    queries = []
    for _ in xrange(int(raw_input().strip())):
        queries.append(map(int, raw_input().rstrip().split()))
    ans = freqQuery(queries)
    with open(os.environ['OUTPUT_PATH'], 'w') as fptr:
        fptr.write('\n'.join(map(str, ans)))
        fptr.write('\n')

This is the shortest way (as per my knowledge). However, there is an error. when [q[0] == 2], before doing cnt[freq[q[1]]]-=1, you should check if cnt[freq[q[1]]] > 0. Otherwise, you might make it negative.

Actually my logic is same, test cases 7,8 and 11 are failing

Very clever solution. One minor change (which is optional, actually). The first instance of "cnt[freq[q[1]]]-=1" (within "if q[0]==1:") should only be done if cnt[freq[q[1]]] >0.

Hi Naomi, great solution! i understand the method is called double hashing. I tried solving the problem with single hash but faced timeout issues in several cases. could you explain why double hashing resolves the issue?

gettings tle in 10,12,13. any suggestions?

def freqQuery(queries):
    dic = dict()
    res =[]
    for q, n in queries:
        if q == 1:
            try:
                dic[n] += 1 
            except Exception:
                dic[n] = 1
        elif q == 2:
            try:
                dic[n] -= 1
                if (dic[n] == 0):
                    dic.pop(n)
            except Exception:
                continue;
        else:
            if n in dic.values():
                res.append(1)
            else:
                res.append(0)
    return res

can you explain the question why you need to use two dictionaries

My question is why is this better than using a defaultdict and a Counter? my solution is as follows:

def freqQuery(queries):
    occ_dict = defaultdict(int)
    result_array = []
    for op in queries:
        if op[0] == 1:
            occ_dict[op[1]] += 1
        elif op[0] == 2:
            if occ_dict[op[1]] > 0:
                occ_dict[op[1]] -= 1
        elif op[0] == 3:
            occ_counter = Counter(occ_dict)
            if occ_counter[op[1]]:
                result_array.append(1)
            else:
                result_array.append(0)
    return(result_array)

Any help would be appreciated, thanks!

Best solution ever, concise and great use of Counters

Not shorter but this is a passable solution without the use of Counter from Collections:

def freqQuery(queries):

    a1 = dict()  #Keep track of the number of times each queried number occurs in the array
    a2 = dict() #[0]*len(queries)  #Keep track of how many numbers occur once, twice, etc.
    
    out = []

    for (op,num) in queries:

        if  (op == 1):
            if not(num in a1):
                a1[num] = 0

            if not(a1[num] in a2):
                a2[a1[num]] = 1

            a2[a1[num]] -= 1
            
            a1[num] += 1

            if not(a1[num] in a2):
                a2[a1[num]] = 0

            a2[a1[num]] += 1
        
        if (op == 2) & (num in a1):

            a2[a1[num]] -= 1
            a1[num] -= 1
            a2[a1[num]] += 1

            if a1[num] <= 0:
                a1.pop(num)
            

        if (op == 3) & (num in a2):
            out.append(int(a2[num]>0))
            #out.append(a2[num])

        elif (op==3):
            out.append(0)

    return out
		

I have almost the same code as you, but I have a few tests failing, all in the test cases with 100000 operations :( If I pastge your code directly, it works. I've optimised my code to be as close as yours, just to try and see what happens, and it doesn't work. Can you see any difference?

function freqQuery(queries) {
    let result = [];
    let freq = [];
    let map = {};

    for (let i = 0; i < queries.length; i++) {
        const [op, x] = queries[i];
        const f = map[x] || 0;

        if (op === 1) {
            map[x] = f + 1;
            freq[f] = (freq[f] || 0) - 1;
            freq[f+1] = (freq[f+1] || 0) + 1;
        }
        if (op === 2) {
            map[x] = f - 1;
            freq[f-1] += 1;
            freq[f] -= 1;
        }
        if (op === 3) {
            result.push(freq[x] > 0 ? 1 : 0);
        }
    }

    return result;
}

you're appreciated

It doesn't pass all test cases. Just ran it and got the same errors as with my code. It doesn't pass 7 through 13.

I'm getting a timeout for those no matter what in Java. I'm not sure I can optimize this solution much more and I'm starting to think it's not my fault that I'm timing out.

Same for Swift. And same for PHP solutions.

I'm using two NSCountedSets and have tried minimizing the boilerplate code as much as possible to no success.

Same here. 2 Hashmaps so no .contains() or anything. In fact not function calls aside from append() is used. Still no go. No one on leaderboard got full point in Swift

yeah i am also getting timeout for 9-13 testcases.

I tried running the barebones boilerplate code and I am still getting timeouts

I was experiencing the same issue. It turns out that the boilerplate code is the problem, because if you set freqQuery(queries: [[Int]])->[Int] to simply return [], it still fails some of the tests with timeout.

So, in the boilerplate, I replaced:

let queries: [[Int]] = AnyIterator{ readLine()?.replacingOccurrences(of: "\\s+$", with: "", options: .regularExpression) }.prefix(q).map {
    let queriesRow: [Int] = $0.split(separator: " ").map {
        if let queriesItem = Int($0) {
            return queriesItem
        } else { fatalError("Bad input") }
    }

    guard queriesRow.count == 2 else { fatalError("Bad input") }

    return queriesRow
}

with:

var queries = [[Int]]()
while let raw = readLine() {
    guard raw.count >= 3, raw[raw.index(raw.startIndex, offsetBy: 1)] == " " else { fatalError("Bad input") }
    guard let op = Int("\(raw[raw.startIndex])"),
        let val = Int("\(raw[raw.index(raw.startIndex, offsetBy: 2)..<raw.endIndex])")
    else {
        fatalError("Bad input")
    }
    queries.append([op, val])
}

And then all my tests passed. I'll submit this as a suggestion for them to fix as well. Cheers!

Yep that did it. Dang that was annoying. Thanks for the help ;)

This fixed timeout on 9-12 for me, on Java 8. The other suggestions to change the boilerplate by passing in[][] did not, but this worked.

Can someone explain why though? Is there a memory constraint problem with passing in the 2D array instead of the bufferedReader, consequentially slowing the program down? Not too sure what's the difference.

I ended up using StringBuilder to construct the answer, always appending "0\n" or "1\n".

Faster than first collecting all answers into a List, then iterating through the list to create the stream, then converting the integers to Strings, then joining the Strings with "\n".