top k frequent

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.9%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Top%20K%20Frequent%20Elements%0A%0A%20%20%20%20**LeetCode%20347%20%C2%B7%20NeetCode%20150%20%E2%80%94%20Heap%20%2F%20Priority%20Queue**%0A%0A%20%20%20%20Given%20an%20integer%20array%20%60nums%60%20and%20an%20integer%20%60k%60%2C%20return%20the%20%60k%60%20most%0A%20%20%20%20frequent%20elements.%20%20The%20answer%20may%20be%20in%20any%20order.%0A%0A%20%20%20%20**ML%20relevance**%3A%20this%20pattern%20is%20everywhere%20%E2%80%94%20top-k%20tokens%20in%20a%20corpus%2C%0A%20%20%20%20most%20popular%20items%20in%20a%20recommendation%20system%2C%20dominant%20feature%20values%2C%0A%20%20%20%20frequent%20categories%20in%20a%20dataset.%20%20Understanding%20it%20also%20unlocks%20the%0A%20%20%20%20*bucket%20sort*%20trick%20useful%20whenever%20values%20are%20bounded.%0A%0A%20%20%20%20%23%23%20Expected%20approaches%0A%0A%20%20%20%20**Heap%20%E2%80%94%20O(n%20log%20k)**%0A%20%20%20%20Count%20frequencies%20with%20a%20dict%2C%20then%20maintain%20a%20min-heap%20of%20size%20k.%0A%0A%20%20%20%20**Bucket%20sort%20%E2%80%94%20O(n)**%20(optimal)%0A%20%20%20%20Frequencies%20are%20in%20%60%5B1%2C%20n%5D%60%2C%20so%20make%20%60n%2B1%60%20buckets%20(bucket%20i%20holds%0A%20%20%20%20elements%20with%20frequency%20i)%2C%20then%20scan%20from%20the%20right.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20%23%20---%20student%3A%20begin%20---%0A%0A%20%20%20%20def%20topKFrequent(nums%3A%20list%2C%20k%3A%20int)%20-%3E%20list%3A%0A%20%20%20%20%20%20%20%20%22%22%22Return%20the%20k%20most%20frequent%20elements%20of%20nums%20(any%20order).%0A%0A%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20nums%3A%20list%20of%20integers%20(may%20contain%20duplicates)%0A%20%20%20%20%20%20%20%20%20%20%20%20k%3A%20%20%20%20how%20many%20top-frequent%20elements%20to%20return%20(1%20%E2%89%A4%20k%20%E2%89%A4%20unique%20elements)%0A%0A%20%20%20%20%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20A%20list%20of%20k%20integers%2C%20each%20being%20one%20of%20the%20most%20frequent%20elements.%0A%20%20%20%20%20%20%20%20%20%20%20%20Order%20does%20not%20matter.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20raise%20NotImplementedError(%22Implement%20topKFrequent%22)%0A%0A%20%20%20%20%23%20---%20student%3A%20end%20---%0A%20%20%20%20return%20(topKFrequent%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20topKFrequent)%3A%0A%20%20%20%20def%20_oracle(nums%2C%20k)%3A%0A%20%20%20%20%20%20%20%20count%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20x%20in%20nums%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20count%5Bx%5D%20%3D%20count.get(x%2C%200)%20%2B%201%0A%20%20%20%20%20%20%20%20return%20%5Bv%20for%20v%2C%20_%20in%20sorted(count.items()%2C%20key%3Dlambda%20p%3A%20-p%5B1%5D)%5B%3Ak%5D%5D%0A%0A%20%20%20%20_cases%20%3D%20%5B%0A%20%20%20%20%20%20%20%20(%5B1%2C%201%2C%201%2C%202%2C%202%2C%203%5D%2C%20%20%20%20%20%20%20%202%2C%20%7B1%2C%202%7D)%2C%0A%20%20%20%20%20%20%20%20(%5B1%5D%2C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201%2C%20%7B1%7D)%2C%0A%20%20%20%20%20%20%20%20(%5B4%2C%204%2C%204%2C%202%2C%202%2C%203%5D%2C%20%20%20%20%20%20%20%20%201%2C%20%7B4%7D)%2C%0A%20%20%20%20%20%20%20%20(%5B1%2C%202%2C%203%2C%204%2C%205%5D%2C%20%20%20%20%20%20%20%20%20%20%20%203%2C%20%7B1%2C%202%2C%203%2C%204%2C%205%7D)%2C%20%20%20%23%20any%203%20of%205%20(all%20freq%3D1)%0A%20%20%20%20%20%20%20%20(%5B5%2C%203%2C%201%2C%201%2C%201%2C%203%2C%2073%2C%201%5D%2C%20%202%2C%20%7B1%2C%203%7D)%2C%0A%20%20%20%20%5D%0A%0A%20%20%20%20_solved%20%3D%20False%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20for%20_nums%2C%20_k%2C%20_expected_set%20in%20_cases%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_got%20%3D%20topKFrequent(_nums%5B%3A%5D%2C%20_k)%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20isinstance(_got%2C%20list)%2C%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22topKFrequent%20must%20return%20a%20list%2C%20got%20%7Btype(_got)%7D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20len(_got)%20%3D%3D%20_k%2C%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22topKFrequent(%7B_nums%7D%2C%20%7B_k%7D)%3A%20expected%20%7B_k%7D%20elements%2C%20got%20%7Blen(_got)%7D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Verify%20each%20returned%20element%20is%20genuinely%20one%20of%20the%20top-k%20frequent%0A%20%20%20%20%20%20%20%20%20%20%20%20_oracle_result%20%3D%20_oracle(_nums%2C%20_k)%0A%20%20%20%20%20%20%20%20%20%20%20%20_oracle_freqs%20%3D%20sorted(set(_oracle_result))%0A%20%20%20%20%20%20%20%20%20%20%20%20_min_oracle_freq%20%3D%20min(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum(1%20for%20x%20in%20_nums%20if%20x%20%3D%3D%20v)%20for%20v%20in%20_oracle_result%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_v%20in%20_got%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_freq%20%3D%20sum(1%20for%20x%20in%20_nums%20if%20x%20%3D%3D%20_v)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20assert%20_freq%20%3E%3D%20_min_oracle_freq%2C%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22topKFrequent(%7B_nums%7D%2C%20%7B_k%7D)%3A%20%7B_v%7D%20has%20freq%3D%7B_freq%7D%20but%20%22%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22min%20top-%7B_k%7D%20freq%20is%20%7B_min_oracle_freq%7D%22%0A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(%22%E2%9C%85%20%60topKFrequent%60%20is%20correct%20on%20all%20test%20cases!%22)%2C%20kind%3D%22success%22)%0A%20%20%20%20%20%20%20%20_solved%20%3D%20True%0A%20%20%20%20except%20NotImplementedError%20as%20e%3A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(f%22%E2%9C%8F%EF%B8%8F%20%7Be%7D%22)%2C%20kind%3D%22neutral%22)%0A%20%20%20%20except%20Exception%20as%20e%3A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(f%22%E2%9D%8C%20%7Be%7D%22)%2C%20kind%3D%22danger%22)%0A%20%20%20%20%23%20---%20capture%20%26%20report%20---%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20import%20inspect%20as%20_inspect%2C%20json%20as%20_json%2C%20js%20as%20_js%0A%20%20%20%20%20%20%20%20from%20pyodide.ffi%20import%20to_js%20as%20_to_js%0A%20%20%20%20%20%20%20%20_srcs%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_fn%20in%20(topKFrequent%2C)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_srcs.append(_inspect.getsource(_fn))%0A%20%20%20%20%20%20%20%20%20%20%20%20except%20Exception%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%20%20%20%20%20%20%20%20_payload%20%3D%20_json.dumps(%7B%22notebookId%22%3A%20%22ml_interview%2Ftop_k_frequent%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22code%22%3A%20%22%5Cn%5Cn%22.join(_srcs)%2C%20%22solved%22%3A%20bool(_solved)%7D)%0A%20%20%20%20%20%20%20%20if%20_solved%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch%20%3D%20_js.BroadcastChannel.new(%22mlp-notebooks%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch.postMessage(_js.JSON.parse(_json.dumps(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22type%22%3A%20%22mlp%3Anotebook-solved%22%2C%20%22notebookId%22%3A%20%22ml_interview%2Ftop_k_frequent%22%7D)))%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch.close()%0A%20%20%20%20%20%20%20%20_js.fetch(%22%2Fapi%2Fnotebook-progress%22%2C%20_to_js(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%22method%22%3A%20%22POST%22%2C%20%22headers%22%3A%20%7B%22Content-Type%22%3A%20%22application%2Fjson%22%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%22credentials%22%3A%20%22include%22%2C%20%22body%22%3A%20_payload%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20dict_converter%3D_js.Object.fromEntries))%0A%20%20%20%20except%20Exception%3A%0A%20%20%20%20%20%20%20%20pass%0A%20%20%20%20mo.output.replace(_result)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A