How should I practice Minimum Operations to Make Array Valid?

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

Is Minimum Operations to Make Array Valid associated with Amazon?

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

Problem · Array

Minimum Operations to Make Array Valid

Learn this problem

● Medium

AmazonOA

See Amazon hiring insights

Problem statement

You are given an array arr of n integers. In one operation, you choose any two distinct values x and y that appear in arr and 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. This means that for any value v, all occurrences of v must appear next to each other in a single continuous segment. Values do not all need to be the same. For example,

[1, 1, 2, 2, 3] is valid because each distinct value appears in one contiguous block.
[1, 2, 1, 3] is not valid because value 1 appears in two separated blocks, with value 2 between them.

If arr is already valid, return 0.

Function

minimumOperationsToMakeArrayValid(arr: int[]) → int

Examples

Example 1

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

Value 1 appears at two positions with value 2 between them. Replacing every occurrence of 2 with 1 yields [1, 1, 1], where 1 forms a single contiguous block. One operation is sufficient.

Example 2

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

One way to make the array valid is:

Replace every occurrence of 2 with 1, giving [1, 1, 3, 1, 1, 3].
Replace every occurrence of 3 with 1, giving [1, 1, 1, 1, 1, 1].

Now the only remaining distinct value is 1, so it forms a single contiguous block

Example 3

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

Constraints

1 ≤ n ≤ 1000
1 ≤ arr[i] ≤ 1000