Thanks!

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.

Interesting. Do you know why defaultdict is faster. From what I understand, defaultdict is very similar to Counter except that if we call a missing key, the defaultdict will include that key in its key set while Counter does not, which means defaultdict cost more operations and thus cost more time? (I'm a total newbie to computer science so excuse me for my naive question

Thank you My first time sharing a solution (as well as earning compliments from it)

Looks exactly like my solution.

Why do you do

cnt[freq[value]] -= 1

and

cnt[freq[value]] +=1

before and after actions 1 and 2? Why do they not cancel out?

This approach does not work in python 3 because action is interpreted as the index of the query, and not the first number in the array.

my wrong answer also failing in 7, 8 and 11 i got correct answer after i found that i forgot to skip delete query if the number total is zero

"if n in dic.values()" can start to take too much time if you are doing it too often. Try to store frequencies somewhere instead of searching through your array of values everytime you get a q==3.

Hi, one dict is to keep track of the frequency of each elements (key: element, value: frequency). The other keeps track of frequency of the frequency (key: frequency, value: number of elements that has that frequency). Hope it helps!

Hi, do you notice that each time, the query starts with 3, it has to count occ_dict all over again? In my code, when the query starts with 3, it just has to search for it, none additional counting is required

we just needed to store frequencies of elements in such a way that we can perform search efficiently. So, to store them in keys, just storing their frequency count (frequency of frequencies) in values. so, frequency count is just used to store the actual element frequencies in keys.

I ended up creating a frequancy dictionary to store the frequancy as a key, and a Hash Set of values. I did this because the key needs to be unique, and in most cases, using a frequancy dictionary of integers alone would fail.

If you follow this path, always remember to remove the value from the current frequancy hash set before you move it onto the next, whenever you add or subtract. Don't worry about removing the entry, if there are no more values in a certain frequencies Hash Set. Just check that the Hash Set has a Count greater than 0, when asserting that the frequancy can be found.

I solved it, with extensive changes to the boilerplate code. Wrote a blog post about it here. But for some reason the leaderboard won't update my score; I completed the problem in Python 3 first because I got frustrated.

I also independently came up with the dual Dictionary hashmap approach and am timeout failing on cases 9 - 11.

I even added optimizations such as pre-allocating dictionary size to maximum potential sizes, and automatically rejecting out of bounds frequency checks.

Fixed.

how to sent suggestion?