Design Gurus Logo
Maximum Distinct Elements (medium)

Problem Statement

Given an array of numbers nums and an integer K, find the maximum number of distinct elements after removing exactly K elements from the nums array.

Example 1:

  • Input: nums = [7, 3, 5, 8, 5, 3, 3], K=2
  • Expected Output: 3
  • Explanation: We can remove two occurrences of 3 to be left with 3 distinct numbers [7, 3, 8], we have to skip 5 because it is not distinct and occurred twice. Another solution could be to remove one instance of '5' and '3' each to be left with three distinct numbers [7, 5, 8], in this case, we have to skip 3 because it occurred twice.

Example 2:

  • Input: [3, 5, 12, 11, 12], and K=3
  • Expected Output: 2
  • Explanation: We can remove one occurrence of 12, after which all numbers will become distinct. Then we can delete any two numbers which will leave us 2 distinct numbers in the result.

Example 3:

  • Input: [1, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5], and K=2
  • Expected Output: 3
  • Explanation: We can remove one occurrence of '4' to get three distinct numbers 1, 2 and 4.

Constraints:

  • 1 <= arr.length <= 10<sup>5</sup>
  • 1 <= arr[i] <= 10<sup>9</sup>
  • 0 <= k <= arr.length

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory