Sort Colors Problem Solution

Sort Colors Problem Solution: Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 01, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Example :

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

Sort Colors Problem Solution

Problem Solution In Python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        curr = 0
        for _ in range(len(nums)):
            if nums[curr] == 0:
                nums.pop(curr)
                nums.insert(0, 0)
                curr += 1
            elif nums[curr] == 2:
                nums.pop(curr)
                nums.append(2)
            else:
                curr += 1
        return

Problem Solution In Java

public void sortColors(int[] nums) {
        int len = nums.length;
        int zero=0,one=0,two=0;
        for(int i=0;i<len;i++){
            if(nums[i] == 0){
                zero++;
            }else if(nums[i]==1){
                one++;
            }else{
                two++;
            }
        }
        for(int i=0;i<zero;i++){
            nums[i] = 0;
        }
        for(int i=zero;i<zero+one;i++){
            nums[i] = 1;
        }
        for(int i=zero+one;i<len;i++){
            nums[i] = 2;
        }
}

Problem Solution In C++

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int top = 0; 
        int bot = nums.size()-1;
        int ct1 = 0;
        int ct2 = 0;
        while (top<=bot) {
            if (nums[top] == 0) ct1++;
            if (nums[top] == 1) ct2++;            
            top++;
        }
        for (int i = 0; i <= bot; i++) {
            if (ct1-->0) nums[i] = 0;
            else if(ct2-->0) nums[i] = 1;
            else nums[i] = 2;
        }
        
    }
};

Problem Solution In C

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

void sortColors(int* nums, int numsSize){
    
    int zeros = 0, ones = 0, twos = numsSize - 1;
    
    while (ones <= twos) {
        if (nums[ones] == 0) {
            if (ones != zeros)
                swap(&nums[ones], &nums[zeros]);
            ones++;
            zeros++;
        } else if (nums[ones] == 1) {
            ones++;
        } else {
            if (twos != ones)
                swap(&nums[twos], &nums[ones]);
            twos--;
        }
    }

}

Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment