Jobs

Interviews

Discussions

Least Number of Unique Integers after K Removals

#221 Most AskedMedium

Least Number of Unique Integers after K Removals #221 Most Asked

Medium

Yahoo

7 views

Topics:

ArraysGreedy Algorithms

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Try coding it in LeetCode

Least Number of Unique Integers after K Removals

#221 Most AskedMedium

Least Number of Unique Integers after K Removals #221 Most Asked

Medium

Yahoo

7 views

Topics:

ArraysGreedy Algorithms

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `arr` and the value of `k`?
Can the integer values within `arr` be negative or zero, or are they strictly positive?
What should be the expected output if `k` is greater than or equal to the total number of elements in the array?
Is it possible for the input array `arr` to be empty, and if so, what should be returned?
Is it guaranteed that `k` will always be a non-negative integer?

Brute Force Solution

Approach

The brute force approach is to try out every single possible way of removing the given number of items from our collection. For each combination of removals we try, we count how many different types of numbers remain and we keep track of the smallest count we find.

Here's how the algorithm would work step-by-step:

First, imagine all the possible groups of items you could pick to remove. We need to look at every single group whose size matches the number of removals we're allowed.
Start with the first possible group of items to remove. Mentally take them out of our original collection.
Now, look at the items that are left over. Count how many distinct, or unique, types of numbers you see.
Remember this count. This is our best result so far.
Next, put all the items back and try removing a different group of items.
Again, count the number of unique types of numbers that remain.
Compare this new count to the best result you've remembered. If the new one is smaller, it becomes your new best result.
Repeat this process for every single possible combination of items you could remove.
After checking all possibilities, the final best result you've kept track of is the answer.

Code Implementation

import itertools

def least_num_of_unique_ints_brute_force(numbers_array, num_removals):
    minimum_unique_count = float('inf')
    array_length = len(numbers_array)

    # Generate all possible combinations of indices to remove, matching the number of removals allowed.

    all_removal_index_combinations = itertools.combinations(range(array_length), num_removals)

    for indices_to_remove in all_removal_index_combinations:
        remaining_elements = []
        indices_to_remove_set = set(indices_to_remove)

        for current_index in range(array_length):
            # For each combination, we construct the list of elements that would remain after removal.

            if current_index not in indices_to_remove_set:
                remaining_elements.append(numbers_array[current_index])

        # We count the unique numbers in the remaining list to see how many types are left.

        unique_count_after_removal = len(set(remaining_elements))

        # The goal is to find the minimum possible number of unique integers across all removal scenarios.

        if unique_count_after_removal < minimum_unique_count:
            minimum_unique_count = unique_count_after_removal

    # If k is the length of the array, all items are removed, leaving 0 unique integers.

    return minimum_unique_count if num_removals < array_length else 0

Big(O) Analysis

Time Complexity

O(C(n, k) * n) – The core of this brute force strategy is to generate every possible combination of k items to remove from the initial n items. The number of ways to choose k items from n is given by the binomial coefficient C(n, k). For each of these combinations, we must then iterate through the remaining n-k elements to count the unique integers, which takes O(n) time. Therefore, the total complexity is driven by performing an O(n) operation for every single combination. This results in a total time complexity of C(n, k) * n, which is computationally infeasible for large inputs.

Space Complexity

O(N) – The brute-force approach requires examining combinations of removals, which involves creating temporary collections of the remaining items. In the worst case, a temporary collection holding the items left over after removing k elements will be created, which can contain up to N - k elements. Additionally, counting unique items in this temporary collection might involve using a set or hash map. The space required for these temporary structures is proportional to the number of elements remaining, leading to a space complexity that depends on the original input size N.

Optimal Solution

Approach

To get rid of the most unique numbers, the best strategy is to remove numbers that appear the least frequently. By focusing on the rarest numbers first, we can eliminate unique values using the fewest removals possible.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the collection.
Next, group the numbers based on their counts. For example, all numbers that appear once go into one group, all numbers that appear twice go into another, and so on.
To make the biggest impact, start by removing the numbers that are the least common. This means getting rid of the group of numbers that only appear once.
Keep track of how many removals you have left.
Continue this process, moving to the next least common group (like numbers that appear twice), and remove them completely.
Stop as soon as you don't have enough removals left to eliminate a whole group of numbers with the same count.
Finally, count how many different kinds of numbers are still left. This is your answer.

Code Implementation

from collections import Counter

def find_least_num_of_unique_ints(integer_array, removals_left):
    if removals_left >= len(integer_array):
        return 0

    number_frequencies = Counter(integer_array)

    # Sorting by frequency is crucial to greedily remove the least common elements first.

    sorted_frequencies = sorted(number_frequencies.values())

    number_of_unique_integers = len(sorted_frequencies)

    for frequency_of_number in sorted_frequencies:
        # We check if we can remove all occurrences of numbers with this frequency.

        if removals_left >= frequency_of_number:
            removals_left -= frequency_of_number
            number_of_unique_integers -= 1
        else:
            # If we cannot remove all occurrences of this group, we can't remove any more unique numbers.

            break

    return number_of_unique_integers

Big(O) Analysis

Time Complexity

O(n log n) – The initial step of counting the frequency of each of the n elements takes O(n) time using a hash map. Let's say there are u unique numbers. Sorting the frequencies of these u numbers, which is the most expensive operation in this approach, takes O(u log u) time. Since the number of unique elements u can be at most n, the worst-case complexity for sorting is O(n log n). The final loop iterates through the sorted frequencies at most u times, which is O(n). Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The primary driver of auxiliary space is the need to store frequency counts for each number. In the worst-case scenario where all N elements in the input are unique, we would need a hash map with N entries to satisfy the first step of counting occurrences. The second step of grouping these counts also requires space, which at most would hold N distinct frequencies. Therefore, the space complexity is directly proportional to the number of elements in the input array, resulting in O(N).

Edge Cases

Case	How to Handle
Input array `arr` is empty or null	The number of unique integers is zero, so the function should return 0.
`k` is zero, meaning no elements can be removed	The solution should simply return the initial count of unique elements in the array.
`k` is greater than or equal to the total number of elements in the array	All elements will be removed, so the solution should return 0 unique integers.
All elements in the array are identical	The logic correctly identifies one unique group, and since k is less than array length, it will not be removed, returning 1.
All elements in the array are unique	The solution will remove k unique elements one by one, resulting in `initial_unique_count - k` remaining integers.
`k` is large, but not large enough to remove all elements of any group	The greedy removal strategy handles this by reducing counts but not eliminating any unique groups, correctly returning the initial unique count.
The array contains negative numbers, zeros, and positive numbers	A hash map handles any integer value correctly, as they are just keys, so the logic is unaffected.
The input array size is very large (e.g., up to 10^5)	The O(N log N) or O(N) solution based on counting and sorting frequencies scales efficiently and avoids timeouts.

Input array `arr` is empty or null

How to Handle:

The number of unique integers is zero, so the function should return 0.

`k` is zero, meaning no elements can be removed

How to Handle:

The solution should simply return the initial count of unique elements in the array.

`k` is greater than or equal to the total number of elements in the array

How to Handle:

All elements will be removed, so the solution should return 0 unique integers.

All elements in the array are identical

How to Handle:

The logic correctly identifies one unique group, and since k is less than array length, it will not be removed, returning 1.

All elements in the array are unique

How to Handle:

The solution will remove k unique elements one by one, resulting in `initial_unique_count - k` remaining integers.

`k` is large, but not large enough to remove all elements of any group

How to Handle:

The greedy removal strategy handles this by reducing counts but not eliminating any unique groups, correctly returning the initial unique count.

The array contains negative numbers, zeros, and positive numbers

How to Handle:

A hash map handles any integer value correctly, as they are just keys, so the logic is unaffected.

The input array size is very large (e.g., up to 10^5)

How to Handle:

The O(N log N) or O(N) solution based on counting and sorting frequencies scales efficiently and avoids timeouts.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `arr` and the value of `k`?
Can the integer values within `arr` be negative or zero, or are they strictly positive?
What should be the expected output if `k` is greater than or equal to the total number of elements in the array?
Is it possible for the input array `arr` to be empty, and if so, what should be returned?
Is it guaranteed that `k` will always be a non-negative integer?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine all the possible groups of items you could pick to remove. We need to look at every single group whose size matches the number of removals we're allowed.
Start with the first possible group of items to remove. Mentally take them out of our original collection.
Now, look at the items that are left over. Count how many distinct, or unique, types of numbers you see.
Remember this count. This is our best result so far.
Next, put all the items back and try removing a different group of items.
Again, count the number of unique types of numbers that remain.
Compare this new count to the best result you've remembered. If the new one is smaller, it becomes your new best result.
Repeat this process for every single possible combination of items you could remove.
After checking all possibilities, the final best result you've kept track of is the answer.

Code Implementation

import itertools

def least_num_of_unique_ints_brute_force(numbers_array, num_removals):
    minimum_unique_count = float('inf')
    array_length = len(numbers_array)

    # Generate all possible combinations of indices to remove, matching the number of removals allowed.

    all_removal_index_combinations = itertools.combinations(range(array_length), num_removals)

    for indices_to_remove in all_removal_index_combinations:
        remaining_elements = []
        indices_to_remove_set = set(indices_to_remove)

        for current_index in range(array_length):
            # For each combination, we construct the list of elements that would remain after removal.

            if current_index not in indices_to_remove_set:
                remaining_elements.append(numbers_array[current_index])

        # We count the unique numbers in the remaining list to see how many types are left.

        unique_count_after_removal = len(set(remaining_elements))

        # The goal is to find the minimum possible number of unique integers across all removal scenarios.

        if unique_count_after_removal < minimum_unique_count:
            minimum_unique_count = unique_count_after_removal

    # If k is the length of the array, all items are removed, leaving 0 unique integers.

    return minimum_unique_count if num_removals < array_length else 0

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the collection.
Next, group the numbers based on their counts. For example, all numbers that appear once go into one group, all numbers that appear twice go into another, and so on.
To make the biggest impact, start by removing the numbers that are the least common. This means getting rid of the group of numbers that only appear once.
Keep track of how many removals you have left.
Continue this process, moving to the next least common group (like numbers that appear twice), and remove them completely.
Stop as soon as you don't have enough removals left to eliminate a whole group of numbers with the same count.
Finally, count how many different kinds of numbers are still left. This is your answer.

Code Implementation

from collections import Counter

def find_least_num_of_unique_ints(integer_array, removals_left):
    if removals_left >= len(integer_array):
        return 0

    number_frequencies = Counter(integer_array)

    # Sorting by frequency is crucial to greedily remove the least common elements first.

    sorted_frequencies = sorted(number_frequencies.values())

    number_of_unique_integers = len(sorted_frequencies)

    for frequency_of_number in sorted_frequencies:
        # We check if we can remove all occurrences of numbers with this frequency.

        if removals_left >= frequency_of_number:
            removals_left -= frequency_of_number
            number_of_unique_integers -= 1
        else:
            # If we cannot remove all occurrences of this group, we can't remove any more unique numbers.

            break

    return number_of_unique_integers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array `arr` is empty or null	The number of unique integers is zero, so the function should return 0.
`k` is zero, meaning no elements can be removed	The solution should simply return the initial count of unique elements in the array.
`k` is greater than or equal to the total number of elements in the array	All elements will be removed, so the solution should return 0 unique integers.
All elements in the array are identical	The logic correctly identifies one unique group, and since k is less than array length, it will not be removed, returning 1.
All elements in the array are unique	The solution will remove k unique elements one by one, resulting in `initial_unique_count - k` remaining integers.
`k` is large, but not large enough to remove all elements of any group	The greedy removal strategy handles this by reducing counts but not eliminating any unique groups, correctly returning the initial unique count.
The array contains negative numbers, zeros, and positive numbers	A hash map handles any integer value correctly, as they are just keys, so the logic is unaffected.
The input array size is very large (e.g., up to 10^5)	The O(N log N) or O(N) solution based on counting and sorting frequencies scales efficiently and avoids timeouts.

Input array `arr` is empty or null

How to Handle:

The number of unique integers is zero, so the function should return 0.

`k` is zero, meaning no elements can be removed

How to Handle:

The solution should simply return the initial count of unique elements in the array.

`k` is greater than or equal to the total number of elements in the array

How to Handle:

All elements will be removed, so the solution should return 0 unique integers.

All elements in the array are identical

How to Handle:

The logic correctly identifies one unique group, and since k is less than array length, it will not be removed, returning 1.

All elements in the array are unique

How to Handle:

The solution will remove k unique elements one by one, resulting in `initial_unique_count - k` remaining integers.

`k` is large, but not large enough to remove all elements of any group

How to Handle:

The greedy removal strategy handles this by reducing counts but not eliminating any unique groups, correctly returning the initial unique count.

The array contains negative numbers, zeros, and positive numbers

How to Handle:

A hash map handles any integer value correctly, as they are just keys, so the logic is unaffected.

The input array size is very large (e.g., up to 10^5)

How to Handle:

The O(N log N) or O(N) solution based on counting and sorting frequencies scales efficiently and avoids timeouts.

0/237 Yahoo questions completed

0/237 completed