How should I practice Minimum Contiguous Replacements?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Minimum Contiguous Replacements associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

Minimum Contiguous Replacements

Learn this problem

● MediumAmazonOA

See Amazon hiring insights

Problem 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[]) → int

Complete minOperations.

int arr[n]: the array to transform

Returns

int: the minimum number of replacement operations.

Examples

Example 1

arr = [1,2,1]return = 1

Replace every occurrence of 2 with 1, producing [1,1,1].

Example 2

arr = [1,2,3,1,2,3]return = 2

One valid sequence is to replace all 2s with 1, then replace all 3s with 1.

Example 3

arr = [1,2,1,2]return = 1

Replacing every occurrence of either value with the other makes the array one contiguous block.

Constraints

1 <= arr.length <= 1000
1 <= arr[i] <= 1000