FastPrep
Problem · Hash Table

Get Minimum Removals

Learn this problem
● EasyAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

Amazon's data analysts are currently working on an exciting new prototype that focuses on data pruning. In this challenge, you are presented with an array of integers named numbers, containing n elements, and an integer called allowedDistinct. The objective is to strategically remove as few elements as possible from the numbers array so that the remaining dataset contains no more than allowedDistinct unique values.

In other words, given the input array data and the parameter max_distinct, your challenge is to determine the minimum number of elements that must be removed so that the resulting array has at most max_distinct unique elements.

To accomplish this, you need to complete the function getMinRemovals with the following parameters:

  • int numbers[n]: The input array of integer data.
  • int allowedDistinct: The maximum number of distinct elements allowed in the pruned array.

    • The function should return an integer representing the minimum number of elements that must be removed to achieve an array with at most allowedDistinct unique elements.

    Function

    getMinRemovals(numbers: int[], alllowedDistinct: int) → int

    Examples

    Example 1

    numbers = [1, 2, 3, 2, 1]alllowedDistinct = 2return = 1
    Example 1 illustration
    The best approach is to remove just one element—the number 3—from the array. This results in the sequence [1, 2, 2, 1], which contains only 2 distinct elements. Therefore, the minimum number of removals required is 1.

    Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ numbers[i] ≤ 10^9
  • 1 ≤ allowedDistinct ≤ 10^5

    • More Amazon problems

    drafts saved locally
    public int getMinRemovals(int[] numbers, int allowedDistinct) {
  // write your code here
}
    numbers[1, 2, 3, 2, 1]
    alllowedDistinct2
    expected1
    checking account