We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Two dictionary appraoches: O(1) time complexity O(n) space
deffreqQuery(queries):num_freq=defaultdict(int)freq_freq=defaultdict(int)ans=[]forqueryinqueries:ifquery[0]==1:# the freq of this number plus 1# the freq of this freq also plus 1# remove the old frequency since the freq of this number has increasedifquery[1]innum_freq:old_freq=num_freq[query[1]]freq_freq[old_freq]-=1iffreq_freq[old_freq]==0:freq_freq.pop(old_freq)num_freq[query[1]]+=1freq_freq[num_freq[query[1]]]+=1elifquery[0]==2:ifquery[1]innum_freq:cur_freq=num_freq[query[1]]num_freq[query[1]]-=1ifnum_freq[query[1]]==0:num_freq.pop(query[1])# there is no 0 freq in the freq_freq dictfreq_freq[cur_freq]-=1iffreq_freq[cur_freq]==0:freq_freq.pop(cur_freq)ifcur_freq>1:freq_freq[cur_freq-1]+=1elifquery[0]==3:ifquery[1]infreq_freq:ans.append(1)else:ans.append(0)returnans
Frequency Queries
You are viewing a single comment's thread. Return to all comments →
Two dictionary appraoches: O(1) time complexity O(n) space