Katkat
Back

Return the K Most Frequent Values with a Larger-Value Tie-Break

OracleBackend Engineer · Onsite
MediumBackend EngineerOnsiteCoding & Algorithms

Last updated

This problem tests proficiency with hash maps for frequency counting and custom sorting logic using priority queues or sorting algorithms.

Problem Statement

Given an array of integers nums and an integer k, return the k most frequent elements. If multiple elements have the same frequency, the element with the larger value should take precedence. The result should be returned in descending order of priority.

Function Signature

def get_top_k(nums: List[int], k: int) -> List[int]:

Constraints

  • 1 <= nums.length <= 10^5
  • nums[i] are integers within a reasonable range.
  • 1 <= k <= number of distinct elements in nums

Examples

Example 1: Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2] Explanation: 1 appears 3 times, 2 appears 2 times. Both are the top two.

Example 2: Input: nums = [4, 4, 2, 2, 3, 3], k = 2 Output: [4, 3] Explanation: Both 4, 3, 2 appear twice. Since frequencies are tied, 4 comes before 3, and 3 comes before 2.

Edge Cases

  • k equals the number of distinct elements.
  • All elements have the same frequency.
  • Array contains only one distinct element.

Hints

Hint 1

Use a hash map to count the frequency of each integer in the input array.

Hint 2

Store the elements as pairs of (frequency, value) in a list and sort them using a custom comparator that handles frequency first (descending) and value second (descending).

Hint 3

Alternatively, use a Min-Heap of size `k` to track the top elements, but ensure the heap comparison logic correctly breaks ties for equal frequencies.

Follow-up questions

  • What is the time complexity of your solution, and how would it change if you were required to return the elements in O(N) time?
  • How would you modify your approach if the input was an infinite stream of numbers rather than a static array?
  • How does the memory complexity change if the number of distinct elements is significantly smaller than the total number of elements?