hard

Sort a Nearly Sorted Array (Elements at Most K Away)

Sort an array where every element is at most k positions from its sorted position.

1. Define the problem

Sort a Nearly Sorted Array (Elements at Most K Away)

Given an integer array nums where every element is at most k positions away from its position in the fully sorted array, and an integer k, sort nums in ascending order and return it. Because no element needs to travel far, bubble sort settles this array much faster than the general case: run at most k + 1 full passes , stopping early the moment a pass makes no swaps. Every out-of-place element moves at least one step toward its final spot on every pass, so k + 1 passes are always enough.

Constraints

  • 1 ≤ nums.length ≤ 105
  • 0 ≤ k < nums.length
  • -104 ≤ numsi ≤ 104
  • Every element of nums is at most k positions from its position in the sorted array

Example

Inputnums = [3, 1, 2, 6, 4, 5, 8, 7], k = 2
Output[1, 2, 3, 4, 5, 6, 7, 8]

Explanation No element is more than 2 positions from its sorted position, so at most 3 bubble sort passes are needed — here it finishes in 2.

2. Know the words first

In plain terms

Full pass
One walk across the entire array comparing and swapping every adjacent pair, left to right.
3. Visualize the solution

Bound the number of passes by k + 1

Bound the number of passes by k + 1
Statusstart

Initial array [3, 1, 2, 6, 4, 5, 8, 7], k = 2, so at most 3 passes will run.

What happens in this step

[3, 1, 2, 6, 4, 5, 8, 7], k = 2, maxPasses = k + 1 = 3

Every element starts at most 2 positions from its final sorted spot, so at most 3 passes will ever be needed — far fewer than the n - 1 passes plain bubble sort might take.
Step 1 of 3

Steps to visualize

  1. Run a full pass over the array, comparing and swapping every adjacent pair.
  2. If the pass made no swaps, the array is sorted — stop.
  3. Otherwise, run another pass, up to a maximum of k + 1 passes total.
  4. Because every element starts at most k away from its sorted position, k + 1 passes are always enough to finish.
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.

Bound the number of passes by k + 1
Statusstart

Initial array [3, 1, 2, 6, 4, 5, 8, 7], k = 2, so at most 3 passes will run.

What happens in this step

[3, 1, 2, 6, 4, 5, 8, 7], k = 2, maxPasses = k + 1 = 3

Every element starts at most 2 positions from its final sorted spot, so at most 3 passes will ever be needed — far fewer than the n - 1 passes plain bubble sort might take.
Step 1 of 3
5. Solution

Solution

solution.tsTypeScript
function sortKSortedArray(nums, k) {
  const arr = nums.slice();
  const n = arr.length;
  const maxPasses = k + 1;

  for (let pass = 0; pass < maxPasses; pass++) {
    let swapped = false;

    for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        const temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }

    if (!swapped) break;
  }

  return arr;
}
Time
O(n * k)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [3, 1, 2, 6, 4, 5, 8, 7], k = 2[1, 2, 3, 4, 5, 6, 7, 8]example from the docstring
nums = [1, 2, 3, 4], k = 0[1, 2, 3, 4]k = 0 means the array must already be sorted
nums = [2, 1, 4, 3], k = 1[1, 2, 3, 4]every element is at most one position away from sorted
nums = [4, 1, 5, 2, 6, 3], k = 3[1, 2, 3, 4, 5, 6]a larger displacement bound needing more passes
nums = [5], k = 0[5]smallest valid input, a single element
nums = [2, 1], k = 1[1, 2]boundary case, exactly two elements
nums = [2, 2, 1, 3], k = 1[1, 2, 2, 3]duplicate values within the displacement bound

Keep reading