medium Least Number of Unique Integers after K Removals

Problem Statement

Given an array of integers arr and an integer k, return the least number of unique integers remaining after removing exactly k elements from the array.

Examples

Example 1

• Input: arr = [5, 5, 4, 3, 2, 3, 2, 3, 3, 2], k = 6
• Expected Output: 1
• Justification: After removing 4, all 5, and three instances of 2, the updated array will be [3, 3, 3, 3]. It will have only 1 unique element.

Example 2

• Input: arr = [7, 7, 7, 8, 8, 9], k = 2
• Expected Output: 2
• Justification: Removing two instances of the 8, or 1 instance of 8 and 1 of 9, there will be 2 unique elements in the array.

Example 3

• Input: arr = [1, 2, 2, 3, 4, 3], k = 4
• Expected Output: 1
• Justification: You can remove 1, 4 and either both instances of 2 or 3, and the final array will be [2, 2] or [3, 3], based on which element you have removed from the array.

Constraints:

• 1 <= arr.length <= 10⁵
• 1 <= arr[i] <= 10⁹
• 0 <= k <= arr.length

Solution

To solve this problem, the approach involves tracking the frequency of each integer in the array and then removing the least frequent elements first. This strategy ensures that we maximize the reduction in the number of unique integers. By removing the least frequent elements, we effectively minimize the unique elements left in the array.

The reasoning behind this approach is that removing the least frequent elements impacts the count of unique integers more significantly. This most effective solution ensures that the remaining elements are as few as possible.

Step-by-step Algorithm

1. Frequency Mapping:

   • Initialize an empty hash map elementFrequency to store the frequency of each element.
   • Iterate through each element in arr.
   • For each element, update the count in elementFrequency map.

2. Frequency Counting:

   • Initialize an array frequencyCount of size n + 1 (where n is the length of arr) to count the total occurrences of each frequency.
   • Iterate through the values in elementFrequency map.
   • For each frequency value, increment the corresponding index in frequencyCount array.

3. Initialize Unique Elements Count:

   • Set uniqueElements to the size of the elementFrequency map (number of unique keys), storing total number of unique elements in the given array.

4. Remove Elements:

   • Iterate through possible frequencies from 1 to n.
   • For each frequency i:
     • Calculate elementsToRemove as the minimum of k // i and frequencyCount[i]. Here, k//i is the maximum number of elements we can remove which has frequency equal to i with the remaining k value, and frequencyCount[i] is actual number of elements we can remove, which has a frequency equal to i. for example, if we have 3 elements with frequency 2, and remaining k is 4, we can remove only 2 elements with frequency 2.
     • Decrease k by i * elementsToRemove.
     • Decrease uniqueElements by elementsToRemove.
     • If k becomes less than i, break the loop and return uniqueElements as we can't remove more elements.

5. Return Result:

   • If all elements are processed, return uniqueElements.

Algorithm Walkthrough

Let's use the Input arr = [5, 5, 4, 3, 2, 3, 2, 3, 3, 2] and k = 6

1. Frequency Mapping:

   • Initialize elementFrequency as {}.
   • Iterate through arr:
     • Add 5: elementFrequency becomes {5: 1}.
     • Add 5: elementFrequency becomes {5: 2}.
     • Add 4: elementFrequency becomes {5: 2, 4: 1}.
     • Add 3: elementFrequency becomes {5: 2, 4: 1, 3: 1}.
     • Add 2: elementFrequency becomes {5: 2, 4: 1, 3: 1, 2: 1}.
     • Add 3: elementFrequency becomes {5: 2, 4: 1, 3: 2, 2: 1}.
     • Add 2: elementFrequency becomes {5: 2, 4: 1, 3: 2, 2: 2}.
     • Add 3: elementFrequency becomes {5: 2, 4: 1, 3: 3, 2: 2}.
     • Add 3: elementFrequency becomes {5: 2, 4: 1, 3: 4, 2: 2}.
     • Add 2: elementFrequency becomes {5: 2, 4: 1, 3: 4, 2: 3}.

2. Frequency Counting:

   • Initialize frequencyCount as [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
   • Iterate through values in elementFrequency:
     • Frequency of 5: increment frequencyCount[2] to 1.
     • Frequency of 4: increment frequencyCount[1] to 1.
     • Frequency of 3: increment frequencyCount[4] to 1.
     • Frequency of 2: increment frequencyCount[3] to 1.
   • frequencyCount becomes [0, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0].

3. Initialize Unique Elements Count:

   • uniqueElements is set to the size of elementFrequency which is 4.

4. Remove Elements:

   • Iterate through frequencies from 1 to n:
     • Frequency 1:
       • elementsToRemove = min(6 // 1, 1) = 1.
       • k is decreased by 1 * 1 = 1, so k becomes 5.
       • uniqueElements is decreased by 1, so uniqueElements becomes 3.
     • Frequency 2:
       • elementsToRemove = min(5 // 2, 1) = 1.
       • k is decreased by 1 * 2 = 2, so k becomes 3.
       • uniqueElements is decreased by 1, so uniqueElements becomes 2.
     • Frequency 3:
       • elementsToRemove = min(3 // 2, 1) = 1.
       • k is decreased by 1 * 3 = 3, so k becomes 0.
       • uniqueElements is decreased by 1, so uniqueElements becomes 1.
       • Now, K < 3. So, stop iterations, and return uniqueElements.

5. Final Result:

   • The number of least unique elements is uniqueElements, which is 1.

Code

import java.util.*;

public class Solution {

  public int reduceUniqueInts(int[] arr, int k) {
    // Step 1: Count the frequency of each element
    Map<Integer, Integer> elementFrequency = new HashMap<>();
    for (int num : arr) {
      elementFrequency.put(num, elementFrequency.getOrDefault(num, 0) + 1);
    }

    int n = arr.length;

    // Step 2: Array to count how many elements have a certain frequency
    int[] frequencyCount = new int[n + 1];

    // Step 3: Fill the frequencyCount array based on elementFrequency map
    for (int freq : elementFrequency.values()) {
      frequencyCount[freq]++;
    }

    // Total unique elements
    int uniqueElements = elementFrequency.size();

    // Step 4: Iterate through possible frequencies and remove elements
    for (int i = 1; i <= n; i++) {
      int elementsToRemove = Math.min(k / i, frequencyCount[i]);
      k -= (i * elementsToRemove);
      uniqueElements -= elementsToRemove;

      if (k < i) {
        return uniqueElements;
      }
    }

    return 0;
  }

  public static void main(String[] args) {
    Solution reducer = new Solution();
    System.out.println(
      reducer.reduceUniqueInts(new int[] { 5, 5, 4, 3, 2, 3, 2, 3, 3, 2 }, 6)
    ); // Output: 1
    System.out.println(
      reducer.reduceUniqueInts(new int[] { 7, 7, 7, 8, 8, 9 }, 2)
    ); // Output: 2
    System.out.println(
      reducer.reduceUniqueInts(new int[] { 1, 2, 2, 3, 4, 3 }, 4)
    ); // Output: 1
  }
}

Complexity Analysis

Time Complexity

1. We traverse the array arr once to populate the elementFrequency map, which takes time, where n is the array length.
2. We then traverse the elementFrequency map to populate the frequencyCount array. Since the map can have at most n entries, this step also takes time.
3. Finally, we traverse the frequencyCount array, which has a size of n + 1, making this step as well.

Combining all these steps, the overall time complexity is .

Space Complexity

1. We create a elementFrequency map that can have a maximum of n entries.
2. We also create a frequencyCount array with a size of n + 1.

Hence, the total space complexity is .