Make Value Groups Contiguous
MediumAsked in:Amazon•Stage:Online Assessment
arrayhash_tablegreedy
Problem Statement
Given an array of integers, rearrange its elements (using any number of swaps) so that all occurrences of each distinct value form a single contiguous block. The order of the blocks does not matter. Return the minimum number of swaps required to achieve this configuration.
Input Format
The first line contains an integer n, the length of the array. The second line contains n space‑separated integers a1,a2,…,an.
Output Format
Print a single integer – the minimum number of swaps needed to make every value’s occurrences contiguous.
Constraints
- 1 <= n <= 10^5
- -10^9 <= ai <= 10^9