Top k Elements

[darwinrlo]

Top K Numbers

Algorithm

• Create a data structure for holding the top k numbers. As we will see later, we'll need to extract the minimum element from the data structure efficiently. So a heap is a suitable data structure, which gives us the ability to do this in O(log k) time.
• Whenever we encounter something that's bigger than the minimum element, we remove the minimum element and add the new number. Extracting the minimum element and inserting an element are both O(log k) operations on a heap.
  • Peeking at the minimum element of a heap is O(1).
  • Note that if a number is bigger than any number in the data structure, it is most certainly bigger than the minimum element and it is the minimum element that should be removed to make room for the new number.

Complexity

• Time: Inserting the first k elements is O(k log k). For each of the next n-k elements, we might extract a number from the heap and insert a number, both of which add up to O(log k). Peeking at the minimum element only takes O(1) time. So it's O((n-k) log k) for the latter n-k elements.
• Space: The heap stores k elements, meaning a space complexity of O(k).

[darwinrlo]

Kth Smallest Number

[darwinrlo]

LeetCode: Sort Characters By Frequency

Complexity

• Let d be the number of distinct characters. The runtime is O(d log d) because we're iterating over the keys of the hash table, of which there are d, and inserting an entry into the heap for each character. In the worst case, all the numbers are distinct, so the worst-case time complexity is O(n log n).
• In the worst case, the hash table is O(n) (and so will the heap).

[darwinrlo]

LeetCode: Kth Largest Element in a Stream

[darwinrlo]

LeetCode: Find K Closest Elements

[darwinrlo]

Grokking: Maximum Distinct Elements

The solution uses a min-heap. Pretty sure a max-heap should be used. Geeks for Geeks agrees with me.

Geeks for Geeks: Maximum distinct elements after removing k elements

The time complexity uses a variable d, which is the number of distinct elements in the array.

[darwinrlo]

Grokking: Sum of Elements

The problem was described ambiguously. It's not retrieving the indices of the k1-st and k2-nd smallest elements and adding up the elements between them. It's adding up the numbers from the k1-st element to the k2-end element in the sorted order.

[darwinrlo]

LeetCode: Reorganize String Grokking: Rearrange String Geeks for Geeks: Rearrange characters in string so that no two adjacent are same

The explanation for this pattern is lacking. I wonder if the author actually understood the algorithm.

If all elements have equal frequencies, then we will go through each element in turn.

[darwinrlo]

LeetCode: Rearrange String k Distance Apart

Why is a max-heap used?