Solution

This problem follows the Top ‘K’ Numbers pattern, and shares similarities with Top ‘K’ Frequent Numbers.

To solve this problem, we need to determine the maximum number of distinct elements that can be left in the array after removing k elements. The core idea is to prioritize the removal of elements with higher frequencies first, as this will maximize the number of distinct elements remaining. By reducing the frequency of these elements, we can potentially convert them into distinct elements.

The algorithm starts by calculating the frequency of each element in the array. Then, we use a min-heap (priority queue) to store elements based on their frequencies in ascending order. This allows us to efficiently access and remove the least frequent elements first. For each element in the min-heap, we reduce its frequency by removing occurrences until either all occurrences are removed or k elements have been removed. Finally, if there are any removals left (k > 0), we decrement the count of distinct elements accordingly.

Step-by-Step Algorithm

1. Initialize Frequency Map:

   • Create a map to store the frequency of each element in the array.
   • Iterate through the array, updating the frequency of each element in the map.

2. Create Min-Heap:

   • Initialize a min-heap (priority queue) to store elements based on their frequency.
   • Iterate through the frequency map:
     • If an element's frequency is 1, increment the count of distinct elements.
     • If an element's frequency is greater than 1, add it to the min-heap.

3. Remove Elements:

   • While k is greater than 0 and the min-heap is not empty:
     • Extract the element with the lowest frequency from the heap.
     • Calculate the number of occurrences to be removed (frequency - 1).
     • Decrement k by this number.
     • If k is non-negative, increment the count of distinct elements.

4. Adjust Distinct Count:

   • If k is still greater than 0 after processing the min-heap, decrement the count of distinct elements by k. It removes remaining elements from the distinct elements.

5. Return Result:

   • Return the count of distinct elements.

Algorithm Walkthrough

Let's walk through the algorithm using the example: nums = [7, 3, 5, 8, 5, 3, 3], k = 2.

1. Initialize Frequency Map:

   • Initialize an empty map to store the frequency of each element.
   • Iterate through the array and update the map:
     • 7: frequency 1
     • 3: frequency 1 (initially), then 2, then 3
     • 5: frequency 1 (initially), then 2
     • 8: frequency 1
   • Final frequency map: {7: 1, 3: 3, 5: 2, 8: 1}

2. Create Min-Heap:

   • Initialize a min-heap (priority queue).
   • Initialize distinctElementsCount = 0.
   • Iterate through the frequency map:
     • 7: frequency is 1, increment distinctElementsCount to 1.
     • 3: frequency is 3, add to the min-heap.
     • 5: frequency is 2, add to the min-heap.
     • 8: frequency is 1, increment distinctElementsCount to 2.
   • Final distinct elements count before processing heap: 2
   • Final min-heap: [(5, 2), (3, 3)] (elements are tuples of (frequency, element))

3. Remove Elements:

   • While k is greater than 0 and the min-heap is not empty:
     • Extract the element with the lowest frequency from the heap:
       • Pop (5, 2) from the heap.
       • To make element 5 distinct, remove 2 - 1 = 1 occurrence.
       • Decrement k by 1 (k = 2 - 1 = 1).
       • Since k is non-negative, increment distinctElementsCount to 3.
     • Extract the next element with the lowest frequency from the heap:
       • Pop (3, 3) from the heap.
       • To make element 3 distinct, remove 3 - 1 = 2 occurrences.
       • Decrement k by 2 (k = 1 - 2 = -1).
       • Since k is now negative, do not increment distinctElementsCount.

4. Adjust Distinct Count:

   • Since k is not greater than 0 after processing the heap, no need to decrement distinctElementsCount.
   • distinctElementsCount remains 3.

5. Return Result:

   • Return distinctElementsCount, which is 3.

So, the maximum number of distinct elements after removing 2 elements from [7, 3, 5, 8, 5, 3, 3] is 3.

Code

Here is what our algorithm will look like: