educative.io

Educative

Time complexity can be O(n + klogn)?

If we filter from the frequency map to create an array of only duplicates, which will take O(n), can’t we build the heap using this duplicates array in O(n) time?

This will take multiple O(n) operations and space, but the overall time complexity would still be in the order of O(n + klogn) and space complexity of O(n)?

Hi @DongHun_Lee. I hope you are doing well. Can you please paste the lesson link here? I am not able to find the question that you are talking about. Thankyou.