Sort an Array Minimizing Swaps

1. Define the problem

Given an array nums of distinct integers sort it in ascending order while performing the fewest possible swaps . Selection sort's find-the-minimum-then-swap pattern is provably optimal here: each swap places at least one element into its final position , so the total swap count never exceeds n - 1, and for arrays whose elements form cycles, it never does fewer either. Return the sorted array.

Constraints

1 ≤ nums.length ≤ 1000
-10⁵ ≤ nums_i ≤ 10⁵
All values in nums are distinct

Example

Inputnums = [4, 3, 2, 1]

Output[1, 2, 3, 4]

Explanation Selection sort swaps index 0 with index 3 (placing 1), then index 1 with index 2 (placing 2) — 2 swaps total, the minimum possible for this array.

2. Know the words first

In plain terms

Distinct integers: No value repeats, so every value has exactly one correct final position.
Cycle: A group of values that are all out of place relative to each other and can only reach their correct positions by rotating through one another — for example in [3, 1, 2], the values 1, 2, and 3 form a single 3-element cycle.

3. Visualize the solution

Every swap places one more value into its final position

Statuspass 1

Scan all 4 values — the minimum is 1 at index 3.

What happens in this step

arr = [4, 3, 2, 1], sortedEnd = 0, min so far = 4 (index 0)

  idx 1: 3 < 4  →  new min = 3 at index 1
  idx 2: 2 < 3  →  new min = 2 at index 2
  idx 3: 1 < 2  →  new min = 1 at index 3

Every candidate improves on the last, so the scan ends with 1 at index 3 as the minimum.

Step 1 of 5

Steps to visualize

Scan the unsorted region for its minimum value.
If the minimum is already at the front of the unsorted region, skip the swap entirely — it costs nothing.
Otherwise, swap the minimum into place — this single swap finishes that position for good.
Each swap never needs to be undone, so the total count is minimal.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Every swap places one more value into its final position

Statuspass 1

Scan all 4 values — the minimum is 1 at index 3.

What happens in this step

arr = [4, 3, 2, 1], sortedEnd = 0, min so far = 4 (index 0)

  idx 1: 3 < 4  →  new min = 3 at index 1
  idx 2: 2 < 3  →  new min = 2 at index 2
  idx 3: 1 < 2  →  new min = 1 at index 3

Every candidate improves on the last, so the scan ends with 1 at index 3 as the minimum.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function sortArrayMinSwaps(nums) {
  const arr = nums.slice();

  for (let sortedEnd = 0; sortedEnd < arr.length - 1; sortedEnd++) {
    let minIndex = sortedEnd;

    for (let scan = sortedEnd + 1; scan < arr.length; scan++) {
      if (arr[scan] < arr[minIndex]) {
        minIndex = scan;
      }
    }

    if (minIndex !== sortedEnd) {
      const temp = arr[sortedEnd];
      arr[sortedEnd] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }

  return arr;
}

Time: O(n^2)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [4, 3, 2, 1]`	`[1, 2, 3, 4]`	example from the docstring
`nums = [1, 2, 3, 4]`	`[1, 2, 3, 4]`	already sorted, zero swaps needed
`nums = [1, 3, 2, 4]`	`[1, 2, 3, 4]`	only one pair is out of place
`nums = [5, 4, 3, 2, 1]`	`[1, 2, 3, 4, 5]`	fully reversed, larger input
`nums = [9]`	`[9]`	smallest valid input, a single element
`nums = [2, 1]`	`[1, 2]`	boundary case, exactly two elements out of order
`nums = [0, -5, 10, -3, 7]`	`[-5, -3, 0, 7, 10]`	negative and positive values mixed together

Sort an Array Minimizing Swaps