Minimize Global Replacements to Make Values Contiguous
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
## Problem
In one operation, choose two distinct values `x` and `y` that currently appear and replace every occurrence of `x` with `y`. Find the minimum operations needed so that every remaining value appears in exactly one contiguous block.
## Function Contract
Implement `minimum_contiguous_replacements(values)` and return an integer.
## Rules
- A value that occurs once already forms one contiguous block.
- Adjacent equal values belong to the same block.
- One operation changes all occurrences of the selected source value, not a single position.
- The target value must already be present when the operation is performed.
## Constraints
- `0 <= len(values) <= 500000`.
- Every value is an exact integer in `[-9007199254740991, 9007199254740991]`.
## Examples
```text
values = [1, 2, 1, 3, 3]
output = 1
```
Replacing every `2` with `1` yields `[1, 1, 1, 3, 3]`.
Quick Answer: Find the fewest global value-replacement operations needed so every remaining value occupies one contiguous block, accounting for compressed runs and replacements that affect all occurrences at once.
In one operation, choose two distinct values x and y that currently appear and replace every occurrence of x with y. Return the minimum operations needed so every remaining value appears in exactly one contiguous block. Adjacent equal values are part of the same block, values occurring once already form a block, and the target value of every operation must already be present.
Constraints
- 0 <= len(values) <= 500000.
- Every value is an exact integer in [-9007199254740991, 9007199254740991].
- One operation replaces every occurrence of one present value with another present value.
- Adjacent equal values belong to the same block.
- Every remaining value must occupy exactly one contiguous block.
Examples
Input: ([1, 2, 1, 3, 3],)
Expected Output: 1
Explanation: Replacing every 2 with 1 leaves one block of 1 and one block of 3.
Input: ([],)
Expected Output: 0
Explanation: An empty array already satisfies the condition.
Hints
- One global replacement always reduces the number of distinct values by exactly one.
- A valid boundary cannot split the first-to-last occurrence interval of any original value.