Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

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

.....

.....

.....

Like the course? Get enrolled and start learning!
C

CaptainKidd

· 3 years ago

There are implied rules that only come up when you explain answers.

Show 2 replies
D

dsgn623

· a year ago

The core idea is to prioritize the removal of elements with higher frequencies first

Rather it should be lower frequencies first

M

Michael Latman

· 5 years ago

Is example 3's explanation correct? Seems like you could remove one instance of 5 and one instance of 4. But removing 4 alone does not jive with K=2

Show 1 reply
I

Ike Nwankwo

· 3 years ago

The solution says it can be optimized to run in KLOGK but it doesn't list the optimization. Can someone post it?

Show 1 reply
L

lejafilip

· 2 years ago

    auto greaterCountCmp = [](auto lhs, auto rhs){return lhs.second > rhs.second;};
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(greaterCountCmp)> minHeap;