educative.io

Time complexity should be O(N+N*logK)

Courses
,
#1

Hi, I am wondering if time complexity should be O(N+NlogK)? Hashmap initialization should be O(N) instead of O(NlogN). See the time complexity explanation in “Top K Frequent Number” problem, which is O(N+N∗logK) and O(N) for hashmap initialization.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Maximum Distinct Elements (medium) - Grokking the Coding Interview: Patterns for Coding Questions

#2

Hi @Liu_Yao
As we are inserting values in Hashmap and minheap, both so time complexity of Hashmap is O(n), and minheap is O(logN). So the whole time complexity of both will be O(N*log N). This is mentioned in the first line of the time complexity heading in the lesson.