Minimum Cost to Make Array Elements Distinct

You are given an array of integers. You want to transform it so that every element is distinct. You may apply the following operation any number of times (including zero):

Choose a subarray arr[i..j].
Within this subarray, keep only the first occurrence of each element, remove all duplicates, and preserve the order of the remaining elements.
The cost of this operation is the number of unique elements in the chosen subarray.

Find the minimum total cost needed to make the entire array contain only distinct elements.

Example 1:

Input:[[4,2,3,2]]

Output:2

Example 2:

Input:[[2,7,4,2]]

Output:2

Constraints:

1 ≤ length of arr ≤ 2 * 10^5
1 ≤ arr[i] ≤ 10^9

solution.cpp

Run code to see test results

00:00 / 69:42

Minimum Cost to Make Array Elements Distinct

MediumMed•386 views

You are given an array of integers. You want to transform it so that every element is distinct. You may apply the following operation any number of times (including zero):

Choose a subarray arr[i..j].
Within this subarray, keep only the first occurrence of each element, remove all duplicates, and preserve the order of the remaining elements.
The cost of this operation is the number of unique elements in the chosen subarray.

Find the minimum total cost needed to make the entire array contain only distinct elements.

Example 1:

Input:[[4,2,3,2]]

Output:2

Example 2:

Input:[[2,7,4,2]]

Output:2

Constraints:

1 ≤ length of arr ≤ 2 * 10^5
1 ≤ arr[i] ≤ 10^9

MediumMed•386 views

Time Complexity

Space Complexity

Asked at

Ibm

Author: Amit Dayal

Software Engineer

Expert in Data Structures & Algorithms. Building tools to help developers crack FAANG interviews.