Minimize Replacements So Equal Product Values Are Contiguous
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# Minimize Replacements So Equal Product Values Are Contiguous
You are given the quality value of each product in a line. In one operation, choose two distinct values `x` and `y` and replace every occurrence of `x` with `y`. The cost of the operation is the number of elements replaced.
Find the minimum total cost needed to make every value that remains in the array occupy exactly one contiguous block.
```python
def min_contiguous_replacement_cost(quality: list[int]) -> int:
...
```
You may perform any number of operations, and a replacement can merge a value into another value that already exists. Return only the minimum cost; you do not need to return the operations.
## Constraints
- `0 <= len(quality) <= 200_000`
- `-10^9 <= quality[i] <= 10^9`
- The answer fits in a signed 64-bit integer.
## Examples
```text
Input: quality = [1, 2, 1, 3, 3]
Output: 1
Explanation: Replacing the single 2 with 1 makes each remaining value contiguous.
```
```text
Input: quality = [1, 2, 1, 2]
Output: 2
```
```text
Input: quality = [4, 4, 7, 7, 9]
Output: 0
```
Quick Answer: Minimize the replacement cost needed so every remaining product value occupies one contiguous block, where one operation changes all occurrences of one value into another. The challenge tests compression of repeated runs, global merge effects, weighted decisions, and scalable reasoning for arrays with up to 200,000 entries.
