How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Akuna Capital.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Akuna Capital during technical interviews.

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.

Input: [1, 2, 3]

Expected Output: 0

Explanation: Already non-decreasing; no swaps needed.

Input: [3, 2, 1]

Expected Output: 1

Explanation: Swap indices 0 and 2 -> [1, 2, 3]. The 2 is already in place, forming a single 2-cycle.

Input: [5]

Expected Output: 0

Explanation: Single element is trivially sorted.

Input: [2, 2, 2, 2]

Expected Output: 0

Explanation: All equal; every arrangement is already non-decreasing.

Input: [4, 3, 2, 1]

Expected Output: 2

Explanation: Two disjoint swaps: (0,3) and (1,2) -> [1, 2, 3, 4].

Input: [2, 1, 3, 1, 2]

Expected Output: 2

Explanation: Duplicates let you pick targets so the work splits into two cycles -> sorts in 2 swaps.

Input: [-1, -1, 0, -2]

Expected Output: 2

Explanation: Negatives and a duplicate -1; minimum is 2 swaps to reach [-2, -1, -1, 0].

Input: [2, 4, 3, 6, 5, 1, 3, 2, 1]

Expected Output: 6

Explanation: A tangled case where greedy shortest-cycle-first would report 7; the exact max-cycle decomposition yields 3 cycles over 9 misplaced elements, so 6 swaps.

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).

Quick Overview

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.