Find minimum swaps to sort array with duplicates
Company: Akuna Capital
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
### Problem
Given an integer array `nums` of length `n` that may contain duplicate values, you may perform swaps where you choose **any two indices** `i` and `j` and swap `nums[i]` and `nums[j]`.
Return the **minimum number of swaps** required to reorder `nums` into **non-decreasing** order.
### Input
- An integer array `nums`.
### Output
- An integer: the minimum number of swaps needed to make `nums` sorted in non-decreasing order.
### Constraints
- `1 <= n <= 2 * 10^5`
- `-10^9 <= nums[i] <= 10^9`
### Notes
- Because duplicates exist, there can be multiple valid sorted targets; your answer should be the minimum swaps over all valid ways to reach a sorted array.
### Examples
1. `nums = [2, 1, 2]` → sorted form is `[1, 2, 2]`, answer `1` (swap indices 0 and 1).
2. `nums = [1, 5, 1, 5]` → answer `1` (swap the two middle elements to get `[1,1,5,5]`).
Quick Answer: This question evaluates array manipulation and permutation-based reasoning for minimizing swap operations, including handling of duplicate values and performance considerations, within the Coding & Algorithms domain for a Data Scientist role.
Given an integer array `nums` of length `n` that may contain duplicate values, you may perform a swap by choosing **any two indices** `i` and `j` and exchanging `nums[i]` and `nums[j]`.
Return the **minimum number of swaps** required to reorder `nums` into **non-decreasing** order.
Because duplicates may exist, there can be multiple valid sorted arrangements (equal elements are interchangeable). Your answer must be the minimum number of swaps over **all** valid ways to reach a non-decreasing arrangement.
**Examples**
- `nums = [2, 1, 2]` -> `1` (swap indices 0 and 1 to get `[1, 2, 2]`).
- `nums = [1, 5, 1, 5]` -> `1` (swap the two middle elements to get `[1, 1, 5, 5]`).
**Constraints**
- `1 <= n <= 2 * 10^5`
- `-10^9 <= nums[i] <= 10^9`
Constraints
- 1 <= n <= 2 * 10^5
- -10^9 <= nums[i] <= 10^9
- A swap may exchange any two indices (not just adjacent ones).
- Equal values are interchangeable; answer is the minimum over all valid sorted targets.
Examples
Input: [2, 1, 2]
Expected Output: 1
Explanation: Swap indices 0 and 1 -> [1, 2, 2]. One swap.
Input: [1, 5, 1, 5]
Expected Output: 1
Explanation: Swap the two middle elements -> [1, 1, 5, 5]. One swap.
Hints
- Sort a copy of nums to get the target. Map this to a permutation problem: minimum swaps to realize a permutation is (#elements that move) - (#cycles).
- With duplicates you may choose which equal element goes to which equal slot. To minimize swaps you want to MAXIMIZE the number of cycles, so model it on VALUES: add an edge value_here -> value_that_belongs_here for every out-of-place position.
- Every 2-cycle (a pair of values pointing at each other) is the shortest possible cycle and can always be taken first. After removing all 2-cycles, decompose each remaining component into as many cycles as possible. Beware: greedy shortest-cycle-first is NOT always optimal -- e.g. [2,4,3,6,5,1,3,2,1] needs an exact decomposition (answer 6).