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!

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.

brillainat

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

So I rewrote your solution with some comments to try and figure out your logic. Can you check to see if I've understood it?

def freqQuery(queries):
    arr = dict() # val:count of said values    
    freq = dict() #number of counts, ie 1:numbers that appear only
    out = []

for (oper, val) in queries:
    if (oper == 1):
        #insertion
        if not(val in arr):
            arr[val] = 0 #if value isn't in arr dict, then add value to dict and give it a 0 bc we can't assign a 1 just yet
        if not(arr[val] in freq):
            freq[arr[val]] = 1 #if freq dictionary doesn't already have arr[val]'s number, then we automatically assign by 1
        freq[arr[val]] -= 1 #subtracting arr[val]'s number by one because it's always kept at 1
        arr[val] += 1 #adding 1 to arr[val]
        if not(arr[val] in freq):
            freq[arr[val]] = 0  #if arr[val]'s cnt isn't in freq, then we assign it 0
        freq[arr[val]] += 1 #otherwise we increase it by 1

    if (oper == 2) and (val in arr):
        #deletion
        freq[arr[val]] -= 1 #same as above, we subtract 1 from it to keep it at 1
        arr[val] -= 1
        freq[arr[val]] += 1 #same as above, we add 1 from it to keept it at one

        if arr[val] <= 0:
            arr.pop(val)

    if (oper == 3) and (val in freq):
        out.append(int(freq[val]>0))
    elif(oper == 3):
        out.append(0)
return out  

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.

Try to dry run the algortihm with an example. You'll get the idea of how the program runs.

The thing with the 2D array is that you read all the inputs first to build the array and then you process them again one-by-one. This solution will process the current input upon reading it which is relatively faster since you don't have to go through the array again.

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.

I have only put 1 condition in second case for if map[x] > 0 then execute the code.

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) {
        if (map[x] > 0) { 
            map[x] = f - 1;
            freq[f - 1] += 1;
            freq[f] -= 1;
        }
    }
    if (op === 3) {
        result.push(freq[x] > 0 ? 1 : 0);
    }
}
return result;

My solution is slightly more verbose but does more or less the same thing but also doesn't pass 7 - 13.

// Complete the freqQuery function below.
function freqQuery(queries) {
    let hashMap = {};
    let freqMap = [];
    let results = [];

    for(let q in queries) {
        let action = queries[q][0];
        let actionValue = queries[q][1];
        let oldValue = hashMap[actionValue] || 0

        if(action === 1) {
            hashMap[actionValue] = oldValue + 1;
            setFreqMapValue(oldValue, hashMap[actionValue], freqMap);
        } else if(action === 2) {
            hashMap[actionValue] = oldValue - 1
            setFreqMapValue(oldValue, hashMap[actionValue], freqMap);
        } else if (action === 3) {
            results.push(freqMap[actionValue] > 0 ? 1 : 0);
        }
    }

    return results;

}

function setFreqMapValue(oldValue, newValue, freqMap) {
    let oldFreq = freqMap[oldValue] || 0;
    let newFreq = freqMap[newValue] || 0;
    if(oldFreq > 0) {
        freqMap[oldValue] -= 1;
    }
    freqMap[newValue] = newFreq +1;
}

Fixed.

how to sent suggestion?

Same here.