Sort Colors

Medium Arrays

Sort an array of 0s, 1s and 2s in a single pass using the Dutch National Flag algorithm (three pointers).

Sample input

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

Sample output

0 0 1 1 2 2

Solution

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
    return nums

print(*sort_colors([2, 0, 2, 1, 1, 0]))

function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
  return nums;
}

console.log(sortColors([2, 0, 2, 1, 1, 0]).join(" "));

import java.util.Arrays;
import java.util.stream.Collectors;

public class Main {
    static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                int t = nums[low]; nums[low] = nums[mid]; nums[mid] = t;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int t = nums[mid]; nums[mid] = nums[high]; nums[high] = t;
                high--;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 0, 2, 1, 1, 0};
        sortColors(nums);
        System.out.println(Arrays.stream(nums).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}

fun sortColors(nums: IntArray) {
    var low = 0
    var mid = 0
    var high = nums.size - 1
    while (mid <= high) {
        when (nums[mid]) {
            0 -> {
                val t = nums[low]; nums[low] = nums[mid]; nums[mid] = t
                low++
                mid++
            }
            1 -> mid++
            else -> {
                val t = nums[mid]; nums[mid] = nums[high]; nums[high] = t
                high--
            }
        }
    }
}

fun main() {
    val nums = intArrayOf(2, 0, 2, 1, 1, 0)
    sortColors(nums)
    println(nums.joinToString(" "))
}

func sortColors(_ nums: inout [Int]) {
    var low = 0, mid = 0, high = nums.count - 1
    while mid <= high {
        if nums[mid] == 0 {
            nums.swapAt(low, mid)
            low += 1
            mid += 1
        } else if nums[mid] == 1 {
            mid += 1
        } else {
            nums.swapAt(mid, high)
            high -= 1
        }
    }
}

var nums = [2, 0, 2, 1, 1, 0]
sortColors(&nums)
print(nums.map(String.init).joined(separator: " "))

void sortColors(List<int> nums) {
  var low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] == 0) {
      final t = nums[low]; nums[low] = nums[mid]; nums[mid] = t;
      low++;
      mid++;
    } else if (nums[mid] == 1) {
      mid++;
    } else {
      final t = nums[mid]; nums[mid] = nums[high]; nums[high] = t;
      high--;
    }
  }
}

void main() {
  final nums = [2, 0, 2, 1, 1, 0];
  sortColors(nums);
  print(nums.join(' '));
}

#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

int main() {
    vector<int> nums = {2, 0, 2, 1, 1, 0};
    sortColors(nums);
    for (int i = 0; i < (int) nums.size(); i++) {
        cout << nums[i];
        if (i < (int) nums.size() - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

int main() {
    int nums[] = {2, 0, 2, 1, 1, 0};
    int n = 6, low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(&nums[low], &nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(&nums[mid], &nums[high]);
            high--;
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d", nums[i]);
        if (i < n - 1) printf(" ");
    }
    printf("\n");
    return 0;
}