FastPrep
Problem

Get Minimum Amount

NEW GRADOA
See Amazon online assessment and hiring insights

The manager of an Amazon warehouse wants to change the inventory so it becomes optimal. There are n products, and the quality of the i-th product after quality checks is represented by quality[i].

An inventory is optimal if all occurrences of each quality value are contiguous. In other words, after the changes, no quality value should appear in two separated groups.

The manager may perform the following operation any number of times:

  1. Choose two quality values x and y.
  2. Replace every product with quality x by quality y.
  3. The operation costs num_replacements, where num_replacements is the number of products whose quality was changed.

Given the array quality, return the minimum amount of money needed to convert the inventory into an optimal inventory.

Note: Product quality can be negative, indicating that the product is of poor quality.

Function Description

Complete the function getMinAmount.

getMinAmount has the following parameter:

  1. int quality[n]: the quality values of the products

Returns

int: the minimum amount of money needed to convert the inventory into an optimal inventory.

Examples
01 · Example 1
quality = [7, 7, 5, 7, 3, 5, 3]
return = 4

One optimal way is to replace all products with quality 3 by 7, costing 2, and then replace all products with quality 5 by 7, costing another 2. The final inventory contains only quality 7, so it is optimal. The total cost is 4.

02 · Example 2
quality = [1, 2, 1]
return = 1

Replace the single product with quality 2 by quality 1. The resulting inventory is [1, 1, 1], and the cost is 1.

Constraints
  • 1 <= n <= 2 * 10^5
  • -10^9 <= quality[i] <= 10^9
More Amazon problems
drafts saved locally
public int getMinAmount(int[] quality) {
  // write your code here
}
quality[7, 7, 5, 7, 3, 5, 3]
expected4
sign in to submit