Quick Overview

This question evaluates a candidate's proficiency with frequency counting, selection techniques, use of appropriate data structures, and algorithmic time and space complexity analysis.

Find Top K Frequent Elements

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question LeetCode 347. Top K Frequent Elements – given an integer array nums, return the k most frequent elements. Initial requirement: return the top 3 elements; follow-up: generalize to arbitrary k. https://leetcode.com/problems/top-k-frequent-elements/description/

Overview: This question evaluates a candidate's proficiency with frequency counting, selection techniques, use of appropriate data structures, and algorithmic time and space complexity analysis.

Given an integer array nums and an integer k, return a list of the k elements that appear most frequently in nums. Order the result by descending frequency; for elements with equal frequency, order them by ascending numeric value. Assume 1 <= k <= the number of distinct elements in nums.

Constraints

  • 1 <= len(nums) <= 200000
  • -10^9 <= nums[i] <= 10^9
  • 1 <= k <= number of distinct elements in nums
  • Output length is exactly k
  • Order: descending frequency; ties by ascending value

Hints

  1. Count occurrences with a hash map (e.g., collections.Counter).
  2. Sort distinct elements by (-frequency, value) and take the first k.
  3. Alternatively, use a heap of size k keyed by (frequency, -value) or bucket sort for linear-time selection.

Loading coding console...

Show the approach

Approach

We first count frequencies of each value using a hash map. To produce a deterministic result, we sort the distinct values by descending frequency and, when frequencies tie, by ascending numeric value. Finally, we take the first k values from this sorted order.

Time complexity:
O(n + u log u), where n is len(nums) and u is the number of distinct elements
Space complexity:
O(u)