Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Maximum Distinct Elements

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.

Here a number counts as distinct only when it appears exactly once in what is left. A number that still has two or more copies is not counted at all, and neither are its copies. So the way to gain a distinct number is to remove every copy of it but one, which costs one fewer removal than its current count.

Example 1:

  • Input: nums = [7, 3, 5, 8, 5, 3, 3], K=2
  • Expected Output: 3

.....

.....

.....

Like the course? Get enrolled and start learning!
Leandro Casuso

Leandro Casuso

· 13 hours ago

The C# solutions need reviews. Multiple times, they are not following the right styling and standards for the language, and sometimes they misuse libraries, etc., affecting performance and time complexity.

In the specific case of problems that should use heaps (priority queues), the implementations lack consensus. I understand that the versions and tech that you are using probably make it difficult to use the priority queue that comes with the standard libraries from some version ago, but as an alternative, it would be better if you create one that mirrors the standard and use it always.

Show 1 reply
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

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;
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
C

CaptainKidd

· 3 years ago

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

Show 2 replies
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

Reading Progress

0%

Vote for new content