FastPrepFastPrep
Problem Brief

Get Minimum Removal

NEW GRADFULLTIMEOA
See Amazon online assessment and hiring insights

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 Description

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.

1Example 1

Input
catalogue = [3, 3, 5, 7], k = 1
Output
2
Explanation
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

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 10^5
  • 1 ≤ k ≤ 10^5
  • 1 ≤ catalogue[i] ≤ 10^5
public int getminRemoval(int[] catalogue, int k) {
  // write your code here
}
Input

catalogue

[3, 3, 5, 7]

k

1

Output

2

Sign in to submit your solution.