Back to DSA

Sort Colors

medium
Acceptance: 48%
SortingArraysTwo Pointers

An array contains n elements, each being 0, 1, or 2 (representing three categories). Rearrange the array in-place so that all 0s come first, then all 1s, then all 2s. Accomplish this in a single pass through the array without using a sorting library.

Examples

Example 1:
Input:nums = [1,0,2,1,0,2]
Output:[0,0,1,1,2,2]
Example 2:
Input:nums = [0,2,1]
Output:[0,1,2]

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyBest Time to Buy and Sell StockeasyTwo SumeasyValid PalindromeeasyMerge Sorted Arrayeasy
00:00
class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                int temp = nums[low]; nums[low] = nums[mid]; nums[mid] = temp;
                low++; mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int temp = nums[mid]; nums[mid] = nums[high]; nums[high] = temp;
                high--;
            }
        }
    }
}
Time complexityO(n)
Space complexityO(1)