Leetcode Sort Colors problem solution

In the Leetcode 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 0, 1, and 2 to represent the color red, white, and blue, respectively.

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

Example 1:

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


Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2.

Solution in C Programming

void swap(int* a,int* b){
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }
    void sort(int* nums, int left, int right){
        int i=left;
        int j=right;
        int x=nums[(left+right)/2];
        do{
            while(nums[i]<x)i++;
            while(nums[j]>x)j--;
            if(i<=j){
                swap(&nums[i],&nums[j]);
                i++;j--;
            }
        }while(i<=j);
        if(left<j)
            sort(nums,left,j);
        if(i<right)
            sort(nums,i,right);
    }

    void sortColors(int* nums, int numsSize){
        sort(nums,0,numsSize - 1);
    }

Solution in C++ Programming

class Solution {
public:
        void sortColors(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        for(int i = 0; i <= r; i++)
        {
            if(nums[i] == 0)
            {
                swap(nums[i], nums[l++]);
            }
            else if(nums[i] == 2)
            {
                swap(nums[i--], nums[r--]);
            }
        }
    }
};

Solution in Java Programming

import java.util.*;
class Solution {
    public void sortColors(int[] nums) {
        
        int low, high, mid, temp;
        low = 0;
        mid = 0;
        temp = 0;
        high = (nums.length - 1);
        while(mid <= high) {
            switch(nums[mid]) {
                case 0: {
                    temp = nums[low];
                    nums[low] = nums[mid];
                    nums[mid] = temp;
                    low++;
                    mid++;
                    break;
                }
                case 1: {
                    mid++;
                    break;
                }
                case 2: {
                    temp = nums[mid];
                    nums[mid] = nums[high];
                    nums[high] = temp;
                    // mid++;
                    high--;
                    break;
                }
            }
        }
    }
}

Solution in Python Programming

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        
        i = 0 
        j = len(nums) - 1
        
        for k in [0,1,2]:
            while i < j:
                if nums[i] == k:
                    i += 1
                elif nums[j] == k:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
                    j -= 1
                else:
                    j -= 1
            j = len(nums) - 1
            if nums[i] == k and i != j:
                i += 1

Solution in C# Programming

public class Solution {
    public void SortColors(int[] nums) {
        int zero=0, two=nums.Length-1, i=0;
    int temp=0;
        while(i<=two){
            if(nums[i] ==0){
               temp = nums[i];
               nums[i] = nums[zero];
               nums[zero] = temp;
                i++;
                zero++;
            }
            else if (nums[i] == 2){
                 temp = nums[i];
               nums[i] = nums[two];
               nums[two] = temp;
                two--;
            }
            else{
                i++;
            }
        }
    }   
}

Also read,

By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.

Leave a Reply

Your email address will not be published. Required fields are marked *