def freqQuery(queries): freq_table = Counter() answer = [] for q, v in queries: if q == 1: freq_table[v] += 1 elif q == 2: if freq_table[v]: freq_table[v] -= 1 elif q == 3: if v in set(freq_table.values()): answer.append(1) else: answer.append(0) return answer
JAVA 8
The below code was failing test 11 untill I switched from HashMap to LinkedHashMap. Now it passes all tests.
static List freqQuery(List> queries) {
List<Integer> result = new ArrayList<>(); Map<Integer, Integer> counts = new LinkedHashMap<>(); queries.forEach(query ->{ Integer operation = query.get(0); Integer value = query.get(1); Integer current = counts.getOrDefault(value, 0); switch (operation) { case 1: counts.put(value, current+1); break; case 2: if (current > 0) counts.put(value, current-1); break; case 3: boolean count = counts.containsValue(value); result.add(count?1:0); } }); return result; }
in java. * the first hashmap h tracks the integers and their count. * the second hashmap o tracks the counts and occurrences of the counts. * test-11 requires that second hashmap. this is because the getValue method is O(n) if you tried to found counts if you only had hashmap o.
// Complete the freqQuery function below. static List<Integer> freqQuery(List<List<Integer>> queries) { List<Integer> ls = new ArrayList<>(); HashMap<Integer,Integer> h = new HashMap<>(); HashMap<Integer,Integer> o = new HashMap<>(); for(int i=0;i<queries.size();i++){ int a = queries.get(i).get(0); int b = queries.get(i).get(1); int v = 0; // a is choice; b is int; v is count of int; get(v) is occurances of that count switch(a){ case 1: //below is work for counts if(h.containsKey(b)) { v = h.get(b); h.replace(b, v, v+1); } else { h.put(b, 1); v = 0; } //below is work for occurences of counts if(o.containsKey(v) && o.get(v)>0) o.replace(v,o.get(v), o.get(v)-1); v++; //because we're increasing if(o.containsKey(v)) o.replace(v,o.get(v), o.get(v)+1); else o.put(v,1); break; case 2: if(h.containsKey(b)){ v = h.get(b); if(v>1){ h.replace(b,v, v-1); } else h.remove(b); if(o.containsKey(v) && o.get(v)>0) o.replace(v,o.get(v), o.get(v)-1); v--; //because we're reducing if(o.containsKey(v)) o.replace(v,o.get(v), o.get(v)+1); } break; case 3: if(o.containsKey(b) && o.get(b)>0) ls.add(1); else ls.add(0); break; } } return ls; }
O(n) Time solution - track using two data structures
def freqQuery(queries): avail_map = {} freq_map = {} output_arr = [] for o,e in queries: if o == 1: avail_map[e] = avail_map.get(e,0) + 1 freq_map[avail_map[e]] = freq_map.get(avail_map[e],0) + 1 if (avail_map[e] - 1) in freq_map: freq_map[avail_map[e] - 1] -= 1 elif o == 2 and (e in avail_map) and (avail_map[e] > 0): freq_map[avail_map[e]] -= 1 avail_map[e] -= 1 freq_map[avail_map[e]] = freq_map.get(avail_map[e],0) + 1 elif o == 3: if e in freq_map and freq_map[e] > 0: output_arr.append(1) else: output_arr.append(0) return output_arr
Failed in only one test case...
static List<Integer> freqQuery(List<List<Integer>> queries) { List<Integer> ls = new ArrayList<>(); HashMap<Integer,Integer> hs = new HashMap<>(); for(int i=0;i<queries.size();i++){ int a = queries.get(i).get(0); int b = queries.get(i).get(1); switch(a){ case 1: if(hs.containsKey(b)) hs.replace(b, hs.get(b), hs.get(b)+1); else hs.put(b, 1); break; case 2: if(hs.containsKey(b)){ if(hs.get(b)>1){ hs.replace(b, hs.get(b), hs.get(b)-1); } else hs.remove(b); } break; case 3: if(hs.containsValue(b)) ls.add(1); else ls.add(0); break; } } return ls; }
Load more conversations
Sort 805 Discussions, By:
Please Login in order to post a comment