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--;
        }
    }

}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment