← Arrays

Sort Colors

Medium
Python
def sort_colors(nums):
    l=m=0; h=len(nums)-1
    while m<=h:
        if nums[m]==0: nums[l],nums[m]=nums[m],nums[l]; l+=1; m+=1
        elif nums[m]==1: m+=1
        else: nums[m],nums[h]=nums[h],nums[m]; h-=1
Java
public void sortColors(int[] nums){
    int l=0,m=0,h=nums.length-1;
    while(m<=h){
        if(nums[m]==0){int t=nums[l];nums[l]=nums[m];nums[m]=t;l++;m++;}
        else if(nums[m]==1) m++;
        else{int t=nums[m];nums[m]=nums[h];nums[h]=t;h--;}
    }
}

Key Insight

Dutch National Flag. Simultaneous swap vs temp.

Python → Java Differences

  • Simultaneous swap vs temp
  • Dutch National Flag identical
  • l=m=0 chain assign Python
Python
def sort_colors(nums):
    l=m=0; h=len(nums)-1
    while m<=h:
        if nums[m]==0: nums[l],nums[m]=nums[m],nums[l]; l+=1; m+=1
        elif nums[m]==1: m+=1
        else: nums[m],nums[h]=nums[h],nums[m]; h-=1
Java
public void sortColors(int[] nums){
    int l=0,m=0,h=nums.length-1;
    while(m<=h){
        if(nums[m]==0){int t=nums[l];nums[l]=nums[m];nums[m]=t;l++;m++;}
        else if(nums[m]==1) m++;
        else{int t=nums[m];nums[m]=nums[h];nums[h]=t;h--;}
    }
}

Algorithm Steps

1. Three pointers low mid high
2. Partition 0s 1s 2s
← Previous All Arrays Next →