LeetCode #75 Sort Colors Solution & Explanation

LeetCode Problem

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.

LeetCode #75 Examples
LeetCode #75 Constraints

Solution

The first solution came out my mind definitely was Bubble SortBubble sort – Wikipedia

That is a easy way to sort a array

C# Solution

Solution1 – bubble sort

public class Solution {
    public void SortColors(int[] nums) {
        
        int n = nums.Length;
        while(n>1)
        {
            n--;
            for(int i =0;i<nums.Length-1;i++)
            {
               if(nums[i] > nums[i+1]) 
               {
                   int tmp = nums[i];
                   nums[i] = nums[i+1];
                   nums[i+1] = tmp;
               }
            }
        }
    }
}

Time Complexity : O(n2)

Solution2

public class Solution {
    public void SortColors(int[] nums) {
        int a = 0;
        int b = 0;
        int c = 0;
        
        //1.iterate and count each color
        foreach(int num in nums)
        {
            switch(num)
            {
                case 0:
                    a+=1;
                    break;
                case 1:
                    b+=1;
                    break;
                case 2:
                    c+=1;
                    break;
            }
        }
        
        //2.rewrite array
        int cnt = 0;
        while(a>0)
        {
            nums[cnt] = 0;
            a--;
            cnt++; 
        }
        
        while(b>0)
        {
            nums[cnt] = 1;
            b--;
            cnt++; 
        }
        
        while(c>0)
        {
            nums[cnt] = 2;
            c--;
            cnt++; 
        }
        
    }
}

Time Complexity : O(n)

We can found out there are just three color int this problem, so another way to solve this problem is to set three variables to store count of each color.

Java Solution

Solution1

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        while(n>1)    
        {
            n--;
            for(int i =0;i<nums.length-1;i++)
            {
               if(nums[i] > nums[i+1]) 
               {
                   int tmp = nums[i];  
                   nums[i] = nums[i+1];
                   nums[i+1] = tmp;
               }
            }
        } 
    }
}

Time Complexity : O(n2)

Runtime : 12ms、4ms、4ms

Solution2

class Solution {
    public void sortColors(int[] nums) {
        int a = 0;
        int b = 0;
        int c = 0;
        
        //1.iterate and count each color
        for(int num : nums)
        {
            switch(num)
            {
                case 0:
                    a+=1;
                    break;
                case 1:
                    b+=1;
                    break;
                case 2:
                    c+=1;
                    break;
            }
        }
        
        //2.rewrite array
        int cnt = 0;
        while(a>0)
        {
            nums[cnt] = 0;
            a--;
            cnt++; 
        }
        
        while(b>0)
        {
            nums[cnt] = 1;
            b--;
            cnt++; 
        }
        
        while(c>0)
        {
            nums[cnt] = 2;
            c--;
            cnt++; 
        }
    }
}

Time Complexity : O(n)

Runtime : 0ms、0ms、0ms

Python3 Solution

Solution1

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        while(n>1):
            n-=1
            
            for i in range(len(nums)-1):
               if(nums[i] > nums[i+1]):
               
                   tmp = nums[i]
                   nums[i] = nums[i+1]
                   nums[i+1] = tmp

Solution2

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        a = 0
        b = 0
        c = 0
        
        for num in nums:
            if num == 0:
                a+=1
            elif num == 1:
                b+=1
            else:
                c+=1
      
        cnt = 0
        while(a>0):
            nums[cnt] = 0
            a-=1
            cnt+=1
        
        while(b>0):
            nums[cnt] = 1
            b-=1
            cnt+=1
        
        while(c>0):
            nums[cnt] = 2
            c-=1
            cnt+=1

JavaScript Solution

Solution1

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    var n = nums.length;
    while(n>1)    
    {
        n--;
        
        for (let i=0; i<nums.length-1; i++) {
            if(nums[i] > nums[i+1]) 
            {
                let tmp = nums[i];  
                nums[i] = nums[i+1];
                nums[i+1] = tmp;
            }
        }
    }
};

Solution2

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    var a = 0;
    var b = 0;
    var c = 0;
    
    nums.forEach(function(num){
        switch(num)
        {
            case 0:
                a+=1;
                break;
            case 1:
                b+=1;
                break;
            case 2:
                c+=1;
                break;
        }
    });
    
    var cnt = 0;
    while(a>0)
    {
        nums[cnt] = 0;
        a--;
        cnt++; 
    }

    while(b>0)
    {
        nums[cnt] = 1;
        b--;
        cnt++; 
    }

    while(c>0)
    {
        nums[cnt] = 2;
        c--;
        cnt++; 
    }
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot

If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)

The problem link : Sort Colors – LeetCode

Latest Post

Leave a Reply

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