Minimum Contiguous Replacements
Learn this problem
AmazonFULLTIMEOAProblem statement
You are given an array arr of integers. In one operation, choose two distinct values x and y that currently appear in the array, then replace every occurrence of x with y.
Return the minimum number of operations needed to make the array valid.
An array is valid if every distinct value forms exactly one contiguous block. Values do not all need to become the same.
For example, [1,1,2,2,3] is valid, while [1,2,1,3] is not valid because value 1 appears in two separated blocks.
Function
minOperations(arr: int[]) → intComplete minOperations.
int arr[n]: the array to transform
Returns
int: the minimum number of replacement operations.
Examples
Example 1
arr = [1,2,1]return = 1Replace every occurrence of 2 with 1, producing [1,1,1].
Example 2
arr = [1,2,3,1,2,3]return = 2One valid sequence is to replace all 2s with 1, then replace all 3s with 1.
Example 3
arr = [1,2,1,2]return = 1Replacing every occurrence of either value with the other makes the array one contiguous block.
Constraints
- 1 <= arr.length <= 1000
- 1 <= arr[i] <= 1000