medium

Sort an Array of 0s, 1s, and 2s Using Adjacent Swaps

Sort an array of only 0, 1, and 2 values using bubble sort-style adjacent swaps.

1. Define the problem

Sort an Array of 0s, 1s, and 2s Using Adjacent Swaps

Given an array nums containing only the values 0, 1, and 2, sort it in ascending order using only adjacent swaps . Unlike the one-pass partitioning trick for this kind of array, solve it here with bubble sort's repeated compare-and-swap passes — the same technique works no matter how many distinct values the array holds.

Constraints

  • 1 ≤ nums.length ≤ 1000
  • numsi is 0, 1, or 2

Example

Inputnums = [2, 0, 2, 1, 1, 0]
Output[0, 0, 1, 1, 2, 2]

Explanation Repeated adjacent swaps move every 0 to the front and every 2 to the back.

2. Visualize the solution

Bubble sort a three-value array

Bubble sort a three-value array
Statusstart

Initial array [2, 0, 2, 1, 1, 0].

What happens in this step

[2, 0, 2, 1, 1, 0]

Sorting begins with the full array unsorted; pass 1 will compare each neighbor pair left to right, just like with any other values.
Step 1 of 3

Steps to visualize

  1. Walk the array comparing each pair of neighbors.
  2. Swap whenever the left value is bigger than the right value — this works the same whether the values are 0, 1, 2, or anything else.
  3. Repeat passes, shrinking the unsorted region each time, until a pass makes no swaps.
3. 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.

Bubble sort a three-value array
Statusstart

Initial array [2, 0, 2, 1, 1, 0].

What happens in this step

[2, 0, 2, 1, 1, 0]

Sorting begins with the full array unsorted; pass 1 will compare each neighbor pair left to right, just like with any other values.
Step 1 of 3
4. Solution

Solution

solution.tsTypeScript
function sortZeroOneTwo(nums) {
  const arr = nums.slice();
  const n = arr.length;

  for (let pass = 0; pass < n - 1; pass++) {
    let swapped = false;

    for (let i = 0; i < n - 1 - pass; 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^2)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
nums = [2, 0, 2, 1, 1, 0][0, 0, 1, 1, 2, 2]example from the docstring
nums = [0, 0, 0][0, 0, 0]every element is the same value
nums = [2, 2, 2][2, 2, 2]every element is the maximum value
nums = [0, 0, 1, 1, 2, 2][0, 0, 1, 1, 2, 2]already sorted, no swaps needed
nums = [2, 1, 0][0, 1, 2]worst case, fully reverse sorted
nums = [1][1]smallest valid input, a single element
nums = [1, 0, 2, 0, 1, 2][0, 0, 1, 1, 2, 2]values interleaved with no existing order

Keep reading