Minimize Global Replacements to Make Values Contiguous

Problem Statement

You are given an array of integers nums. In a single operation, you can choose any value x currently present in nums and replace all occurrences of x with another value y.

An array is considered valid if every distinct value remaining in the array appears in exactly one contiguous block (that is, no value appears in two or more disjoint segments separated by other values).

Return the minimum number of replacement operations required to make nums valid.

Function Signature

def minReplacements(nums: list[int]) -> int:
    pass

Input and Output

• Input: A list of integers nums.
• Output: An integer representing the minimum number of replacement operations.

Constraints

• 1 <= len(nums) <= 2 * 10^5
• 1 <= nums[i] <= 10^9

Examples

Example 1

Input: nums = [1, 2, 1, 3, 3]
Output: 1
Explanation:
Replace all occurrences of 2 with 1. The array becomes [1, 1, 1, 3, 3].
Value 1 forms a single contiguous block [0..2] and value 3 forms [3..4].
Only 1 operation is needed.

Example 2

Input: nums = [1, 2, 3, 1, 2]
Output: 2
Explanation:
Value 1 spans indices 0 to 3, value 2 spans indices 1 to 4, and value 3 is at index 2.
Because their spans overlap, they must all be collapsed into a single value.
Replacing 2 with 1 and 3 with 1 yields [1, 1, 1, 1, 1], requiring 2 operations.

Example 3

Input: nums = [5, 5, 6, 6, 6, 7]
Output: 0
Explanation:
Every distinct value already appears in a single contiguous block. No replacements are needed.

Edge Cases to Consider

• Arrays where all elements are already equal or already grouped.
• Arrays with completely distinct elements (each element is its own contiguous block of length 1, requiring 0 operations).
• Deeply nested spans, e.g., [1, 2, 3, 2, 1], where inner values must merge with outer values.