LeetCode 1481 - Least Number of Unique Integers after K Removals

This problem asks us to minimize the number of unique integers in an array after removing exactly k elements. In other words, we are given a list arr and a number k, and we need to strategically remove k elements so that the count of distinct integers left in the array is as…

leetcodemediumarrayhash-tablegreedysortingcounting

LeetCode Problem 1481

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting, Counting

Solution

Problem Understanding

This problem asks us to minimize the number of unique integers in an array after removing exactly k elements. In other words, we are given a list arr and a number k, and we need to strategically remove k elements so that the count of distinct integers left in the array is as small as possible.

The input array arr contains integers that can be as large as 10^9 and can have up to 10^5 elements. This means the solution must be efficient in both time and space. The integer k represents exactly how many elements we must remove, so we cannot remove fewer or more.

The expected output is a single integer representing the minimum number of unique elements remaining in the array after the removals.

Important edge cases include scenarios where k is zero (no removal) or k equals the length of the array (all elements removed), and when multiple numbers have the same frequency, which could affect the removal strategy.

Approaches

Brute Force Approach

A naive approach would attempt to remove elements in all possible combinations to see which combination minimizes the number of unique integers. This could be implemented by generating all subsets of size k from the array, removing them, and counting the distinct integers in each result. This method is guaranteed to find the correct answer because it explores every possibility, but it is computationally infeasible. For an array of length n and k removals, the number of subsets to consider is C(n, k), which grows factorially with n and is far too large for n = 10^5.

Optimal Approach

The key insight for a better solution is frequency-based removal. We should remove integers that occur the fewest times first because removing them reduces the count of unique integers most efficiently. By counting the frequency of each integer and sorting them by frequency, we can greedily remove integers starting with the least frequent until k elements are removed. This approach is optimal because removing a higher-frequency integer first would consume more of k without reducing the number of unique integers as effectively.

Approach Time Complexity Space Complexity Notes
Brute Force O(C(n, k) * n) O(n) Tries all combinations of removals; infeasible for large arrays
Optimal O(n log n) O(n) Frequency counting and sorting, then greedy removal

Algorithm Walkthrough

  1. Count Frequencies: Iterate through the array and create a hash map or dictionary to count how many times each integer appears. This allows us to understand which integers are cheap to remove.
  2. Sort by Frequency: Convert the frequency dictionary into a list of (number, frequency) pairs and sort it by frequency in ascending order. This ensures that we prioritize removing integers with the smallest frequency first.
  3. Greedy Removal: Initialize a counter for the number of unique integers. Iterate through the sorted frequency list, and for each integer, check if its frequency is less than or equal to the remaining k. If so, remove it entirely, decrement k by its frequency, and reduce the unique counter. If the frequency is greater than k, remove k elements from this integer and stop because we have used all removals.
  4. Return the Result: After finishing the iteration or using all k removals, the remaining count of unique integers is the answer.

Why it works: The algorithm guarantees the minimum number of unique integers because removing integers in order of increasing frequency ensures that each unit of k contributes maximally to reducing the unique count. This greedy choice maintains an optimal invariant.

Python Solution

from typing import List
from collections import Counter

class Solution:

    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        # Step 1: Count frequencies
        freq = Counter(arr)
        
        # Step 2: Sort integers by frequency
        freq_list = sorted(freq.values())
        
        # Step 3: Greedy removal
        unique_count = len(freq_list)
        for f in freq_list:
            if k >= f:
                k -= f
                unique_count -= 1
            else:
                break
        
        return unique_count

This code first counts the frequency of each integer in arr using Counter, then sorts the frequencies. By iterating through the sorted list, we greedily remove the least frequent integers until k is exhausted, decrementing the count of unique integers each time. The remaining unique_count is returned.

Go Solution

import "sort"

func findLeastNumOfUniqueInts(arr []int, k int) int {
    freq := make(map[int]int)
    for _, num := range arr {
        freq[num]++
    }

    freqList := make([]int, 0, len(freq))
    for _, count := range freq {
        freqList = append(freqList, count)
    }

    sort.Ints(freqList)

    uniqueCount := len(freqList)
    for _, f := range freqList {
        if k >= f {
            k -= f
            uniqueCount--
        } else {
            break
        }
    }

    return uniqueCount
}

In Go, we use a map to count frequencies and a slice to sort them. The logic is identical to the Python version, with attention to slice creation and map iteration.

Worked Examples

Example 1

Input: arr = [5,5,4], k = 1

Step Action Remaining k Unique Count Notes
1 Count frequencies - - 5:2, 4:1
2 Sort by frequency - 2 Sorted frequencies: [1,2]
3 Remove 4 (freq 1) 0 1 k used up, stop

Output: 1

Example 2

Input: arr = [4,3,1,1,3,3,2], k = 3

Step Action Remaining k Unique Count Notes
1 Count frequencies - - 1:2, 2:1, 3:3, 4:1
2 Sort by frequency - 4 Sorted frequencies: [1,1,2,3]
3 Remove 2 (1) 2 3 k=3-1=2
4 Remove 4 (1) 1 2 k=2-1=1
5 Remove 1 (2) partially 0 2 Only 1 element removed, stop

Output: 2

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Counting frequencies is O(n), sorting the frequency list is O(n log n), iteration is O(n)
Space O(n) Hash map and frequency list each take O(n) space

The complexity is dominated by the sorting step. Frequency counting and iteration are linear, so the overall algorithm is efficient for the given constraints.

Test Cases

# Provided examples
assert Solution().findLeastNumOfUniqueInts([5,5,4], 1) == 1  # Single removal
assert Solution().findLeastNumOfUniqueInts([4,3,1,1,3,3,2], 3) == 2  # Multiple removals

# Boundary cases
assert Solution().findLeastNumOfUniqueInts([1], 0) == 1  # No removal
assert Solution().findLeastNumOfUniqueInts([1], 1) == 0  # Remove the only element

# Larger arrays
assert Solution().findLeastNumOfUniqueInts([1,2,3,4,5], 5) == 0  # Remove all
assert Solution().findLeastNumOfUniqueInts([1,2,2,3,3,3], 3) == 1  # Remove least frequent first

# Edge with equal frequencies
assert Solution().findLeastNumOfUniqueInts([1,1,2,2,3,3], 2) == 2  # Remove any two elements from lowest frequency
Test Why
[5,5,4], k=1 Single removal, simple case
[4,3,1,1,3,3,2], k=3 Mixed frequencies, multiple removals
[1], k=0 No removal
[1], k=1 All removed
[1,2,3,4,5], k=5 Remove all elements
[1,2,2,3,3,3], k=3 Greedy removal on uneven frequencies
[1,1,2,2,3,3], k=2 Equal frequency handling

Edge Cases

One important edge case is when k = 0. In this scenario, the algorithm should immediately return the total number of unique integers because no elements are removed. The Python and Go implementations handle this naturally, as the loop will never decrement k.

Another edge case occurs when k equals the length of the array. This means all elements must be removed, resulting in zero unique integers. Both implementations reduce `