Fewest Kinds After Removals

Medium

A box holds parts; items[i] is the kind of the i-th part. Throw out exactly removals parts so that as few distinct kinds as possible stay in the box. Return that smallest number of kinds.

Example 1

items=[7, 7, 2, 9, 9, 9], removals=2 → 2

Throwing out both 7s leaves kinds 2 and 9. Two kinds cannot go with two removals: the rarest (2) costs one removal and the next (7) costs two more.

Example 2

items=[4, 1, 4, 3], removals=4 → 0

Everything is removed, no kinds remain.

Example 3

items=[5, 6, 5], removals=0 → 2

Constraints

1 ≤ len(items) ≤ 10⁵
1 ≤ items[i] ≤ 10⁹
0 ≤ removals ≤ len(items)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Hash Table Counting Sorting

Similar problems

Jobs With a Cooldown Medium Spread Out the Labels Medium Pick Within Tag Limits Medium Palindromes From Shared Letters Medium More Than a Third of the Votes Medium

Input

items=[7, 7, 2, 9, 9, 9], removals=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.