Minimum Swaps to Sort

Given an array of n distinct integers, find the minimum number of swaps required to sort the array in ascending order.

A swap exchanges any two elements in the array (not necessarily adjacent).

Examples

Example 1:

Input: nums = [2, 3, 1]

Output: 2

Explanation: Swap 2 and 1 → [1, 3, 2], then swap 3 and 2 → [1, 2, 3]. Total: 2 swaps.

Example 2:

Input: nums = [4, 3, 2, 1]

Output: 2

Explanation: Swap 4 and 1 → [1, 3, 2, 4], then swap 3 and 2 → [1, 2, 3, 4]. Total: 2 swaps.

Example 3:

Input: nums = [1, 5, 4, 3, 2]

Output: 2

Explanation: Swap 5 and 2 → [1, 2, 4, 3, 5], then swap 4 and 3 → [1, 2, 3, 4, 5]. Total: 2 swaps.

Constraints

• 1 <= nums.length <= 10^5
• All elements of nums are distinct
• 1 <= nums[i] <= 10^6