Is Least Number of Unique Integers after K Removals easy or hard?

The problem is rated Medium because it requires recognizing a greedy strategy after converting the array into frequency counts. The implementation is straightforward once the key insight is clear, but identifying that removing the least frequent numbers first leads to the optimal result is the main challenge.

Least Number of Unique Integers after K Removals Python/Java solution

In Python, developers typically use collections.Counter to compute frequencies and heapq or sorting for the greedy step. Java implementations use HashMap for counting and PriorityQueue or Arrays.sort for ordering frequencies. Both approaches follow the same idea: remove the smallest frequency groups until k deletions are exhausted.

How to solve Least Number of Unique Integers after K Removals in O(n)?

A near O(n) solution can be achieved by counting frequencies and using a counting/bucket strategy instead of sorting or a heap. Group numbers by frequency and remove from the lowest frequency bucket first until k deletions are used. This avoids the log factor when the frequency range is limited, though most practical implementations use sorting or a min-heap.

What is the best approach for Least Number of Unique Integers after K Removals?

The optimal strategy uses greedy frequency removal. Count how many times each integer appears, then remove numbers with the smallest frequency first. This minimizes the number of deletions needed to eliminate a unique value. Implementations commonly use either a min-heap or a sorted list of frequencies, both running in O(n + m log m) time where m is the number of unique elements.

Is Least Number of Unique Integers after K Removals asked at Google/Amazon/Meta?

This pattern appears frequently in interviews at companies like Amazon, Google, and Meta because it tests frequency counting, greedy decision making, and efficient data structure usage. Candidates are expected to recognize that removing the least frequent numbers first minimizes the remaining unique elements.

What data structure is used in Least Number of Unique Integers after K Removals?

The solution relies on a hash map to count frequencies of elements. After counting, either a min-heap (priority queue) or a sorted array of frequencies is used to process the smallest counts first. These structures enable efficient greedy removal of elements.

What is the time complexity of Least Number of Unique Integers after K Removals?

The typical solution runs in O(n + m log m) time. O(n) is used to build the frequency map, and O(m log m) comes from either sorting the frequency list or maintaining a min-heap of size m. Space complexity is O(m) for storing the frequency counts of distinct integers.

Description Hints 2 Solution Video 18:27

1481. Least Number of Unique Integers after K Removals

Medium63.8% acceptance7 companies

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Asked at 7 companies

Fivetran Wayfair Morgan Stanley Salesforce Oracle

Google Amazon

Topics

Hints open one at a time

Hint 1

Use a map to count the frequencies of the numbers in the array.

Hint 2

An optimal strategy is to remove the numbers with the smallest count first.

18:27

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution