Thanks!

Boilerplate is great :), makes you make sure code works. Hints: Input does not fit memory, there are requests for too hight frequencies.

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.

Hashmap.containsValue is O(n) time complexity - more expensive than needed. In my solution, I use both a counter Hashmap to know how many times a specific number appears and a frequency Hashmap to count how many numbers appeared for a specific amount of times. Then, for op==3 I just check if frequency is greater than zero.

All tests passed after changing the boilerplate.

This solution works

static List<Integer> freqQuery(List<int[]> queries) {
    final Map<Integer, Integer> valueToFreq = new HashMap<>();
    final Map<Integer, Integer> freqToOccurrence = new HashMap<>();
    final List<Integer> frequencies = new ArrayList<>();

    int key;
    int value;
    Integer oldFreq;
    Integer newFreq;
    Integer oldOccurrence;
    Integer newOccurrence;
    for (int[] query : queries) {
        key = query[0];
        value = query[1];
        if (key == 3) {
            if (value == 0) {
                frequencies.add(1);
            }
            frequencies.add(freqToOccurrence.get(value) == null ? 0 : 1);
        } else {
            oldFreq = valueToFreq.get(value);
            oldFreq = oldFreq == null ? 0 : oldFreq;
            oldOccurrence = freqToOccurrence.get(oldFreq);
            oldOccurrence = oldOccurrence == null ? 0 : oldOccurrence;

            if (key == 1) {
                newFreq = oldFreq + 1;
            } else {
                newFreq = oldFreq - 1;
            }
            newOccurrence = freqToOccurrence.get(newFreq);
            newOccurrence = newOccurrence == null ? 0 : newOccurrence;

            if (newFreq < 1) {
                valueToFreq.remove(value);
            } else {
                valueToFreq.put(value, newFreq);
            }

            if ((oldOccurrence - 1) < 1) {
                freqToOccurrence.remove(oldFreq);
            } else {
                freqToOccurrence.put(oldFreq, oldOccurrence - 1);
            }
            freqToOccurrence.put(newFreq, newOccurrence + 1);
        }
    }
    return frequencies;
}

This isn't an issue with boiler plate. Your code is failing for cases where there is large amount of queries for op 3 that don't find a matching value.

containsValue is probably O(n) since the value list is not sorted.

Imagine your hash had >100k unique entries all with a frequency of one. Each query with op 3 would have to do 100k tests if the the value was two. This would be true even if every call to op 3 was testing for the same exact value each time!

That is going to be really really slow. Especially if you do all op 3 queries after all op 1 and op 2 queries. The hash table is not changing and we're passing the same values over and over and yet this code does O(n) look up every time.

If you want it to be fast you need a reverse look up of frequency value to list of operand.

else if(op==3) { need to compare the count of a number.. Z not the actual number

        if(hash.containsValue(num)){

You are iterating the map for finding whether the required frequency is present or not. Try maintaining the frequency to values map. So you won't have to iterate the map. see below code :-

static List freqQuery(List queries) { List result = new ArrayList<>(); Map operationsMap = new HashMap();

    Map<Integer, Set<Integer>> frequencyMap = new HashMap<>();
    for (int[] query : queries) {
        switch (query[0]) {
        case 1:
            Integer m = operationsMap.get(query[1]);
            if (m == null) {
                operationsMap.put(query[1], 1);
                Set<Integer> sampleMap = frequencyMap.get(1);
                if (sampleMap != null)
                    sampleMap.add(query[1]);
                else
                    frequencyMap.put(1, new HashSet() {
                        {
                            add(query[1]);
                        }
                    });
            } else {
                operationsMap.put(query[1], ++m);
                frequencyMap.get(m - 1).remove(query[1]);
                Set<Integer> sampleMap = frequencyMap.get(m);
                if (sampleMap != null)
                    sampleMap.add(query[1]);
                else
                    frequencyMap.put(m, new HashSet() {
                        {
                            add(query[1]);
                        }
                    });
            }

            break;
        case 2:
            Integer n = operationsMap.get(query[1]);
            if (n == null)
                break;
            else if (n == 1) {
                operationsMap.remove(query[1]);
                frequencyMap.get(1).remove(query[1]);
            } else {
                operationsMap.put(query[1], --n);
                frequencyMap.get(n + 1).remove(query[1]);
                Set<Integer> sampleMap = frequencyMap.get(n);
                if (sampleMap != null)
                    sampleMap.add(query[1]);
                else
                    frequencyMap.put(n, new HashSet() {
                        {
                            add(query[1]);
                        }
                    });

            }
            break;
        case 3:
            result.add((frequencyMap.get(query[1]) == null || frequencyMap.get(query[1]).isEmpty()) ? 0 : 1);
            break;
        }
    }

return result; }

include

using namespace std;

string ltrim(const string &); string rtrim(const string &); vector split(const string &);

// Complete the freqQuery function below. vector freqQuery(vector> queries) {

map m; map m1; vector v; for(int i=0;i

        if(queries[i][0]==1)
        {
            m[queries[i][1]]++;
            m1[m[queries[i][1]]]++;
        }
        else if(queries[i][0]==2)
        {
            auto f=m.find(queries[i][1]);
            if(f!=m.end())
            {
                m[queries[i][1]]--;
                m1[m[queries[i][1]]]--;
            }

        }
        else if(queries[i][0]==3)
        {
            int flag=0;
            auto f=m1.find(queries[i][1]);
            if(f!=m1.end())
            {
                if(f->second>0)
                flag=1;
            }

            if(flag==0)

              v.push_back(0);
              else
              v.push_back(1);

        }
}
            return v; 

}

int main() { ofstream fout(getenv("OUTPUT_PATH"));

string q_temp;
getline(cin, q_temp);

int q = stoi(ltrim(rtrim(q_temp)));

vector<vector<int>> queries(q);

for (int i = 0; i < q; i++) {
    queries[i].resize(2);

    string queries_row_temp_temp;
    getline(cin, queries_row_temp_temp);

    vector<string> queries_row_temp = split(rtrim(queries_row_temp_temp));

    for (int j = 0; j < 2; j++) {
        int queries_row_item = stoi(queries_row_temp[j]);

        queries[i][j] = queries_row_item;
    }
}

vector<int> ans = freqQuery(queries);

for (int i = 0; i < ans.size(); i++) {
    fout << ans[i];

    if (i != ans.size() - 1) {
        fout << "\n";
    }
}

fout << "\n";

fout.close();

return 0;

}

string ltrim(const string &str) { string s(str);

s.erase(
    s.begin(),
    find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);

return s;

}

string rtrim(const string &str) { string s(str);

s.erase(
    find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
    s.end()
);

return s;

}

vector split(const string &str) { vector tokens;

string::size_type start = 0;
string::size_type end = 0;

while ((end = str.find(" ", start)) != string::npos) {
    tokens.push_back(str.substr(start, end - start));

    start = end + 1;
}

tokens.push_back(str.substr(start));

return tokens;

}

Still test cases 10,11,12 could not pass.

I am still timingout on 9,10,11 with this boiler plate code.

Bro, thank you very much for the solution, since two days I'm trying for this, tried in hundreds of ways, but only yours suceeded. thanks a lot

Thanks, your input/output code was the key for me. I found that the official boilerplate and other ones provided both weren't passing for me, but this did the trick!