Sort Colors

medium array three pointers dutch flag

Problem

Sort an array containing only 0s, 1s, and 2s in place using a single pass and constant extra space. Move all 0s to the front, all 2s to the back, and 1s in the middle.

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

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

Three pointers low, mid, high partition the array into three regions.

nums (only 0, 1, 2 — comma-separated)

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] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1
    return nums

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] === 2) {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    } else {
      mid++;
    }
  }
  return nums;
}

class Solution {
    public 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] == 2) {
                int t = nums[mid]; nums[mid] = nums[high]; nums[high] = t;
                high--;
            } else {
                mid++;
            }
        }
    }
}

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

Time: O(n) Space: O(1)