FastPrep
Problem · Hash Table

Get Minimum Removal

Learn this problem
● EasyAmazonNEW GRADFULLTIMEOA
See Amazon hiring insights

Problem statement

There are n products in an Amazon catalogue, where the category of the ith product is represented by the array catalogue.

The catalogue will be called valid if the number of distinct product categories in it is at most k. If the catalogue is not valid initially, then make it valid by removing some products from the catalogue.

Given n products and an array catalogue, find the minimum number of products to remove from the catalogue to make it valid.

Function

getminRemoval(catalogue: int[], k: int) → int

Complete the function getminRemoval in the editor below.

getminRemoval has the following parameter(s):

  1. int catalogue[n]: the category of the products
  2. int k: the maximum number of distinct product categories

Returns

int: the minimum number of elements to remove from catalogue to make it valid.

Examples

Example 1

catalogue = [3, 3, 5, 7]k = 1return = 2
Example 1 illustration
We can also remove [3, 3, 5] or [3, 3, 7]. However, the number of removed products in these cases is 3, which is not the minimum. Hence, the answer is 2.

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ k ≤ 10^5
  • 1 ≤ catalogue[i] ≤ 10^5

More Amazon problems

drafts saved locally
public int getminRemoval(int[] catalogue, int k) {
  // write your code here
}
catalogue[3, 3, 5, 7]
k1
expected2
checking account