75. Sort Colors

Sort Colors

Problem Description

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.

 

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Approach) Brute force checking

step1: iterate and count each elem
step2: make the existing arr null to make this algo inplace
step3: print the number of 0,1,2 w,r,t count value

var sortColors = function(arr) {
    let one=0, zero=0, two=0
    
    // step1 
    for(let elem of arr){
        if(elem == 0) zero++
        else if ( elem == 1) one ++
        else two ++
    }

    // step2
    arr.length=0

    // step3
    for(let i=0;i<zero;i++) arr.push(0)
    for(let i=0;i<one;i++) arr.push(1)
    for(let i=0;i<two;i++) arr.push(2)    
  
};

Approach) Brute force 

IDEA: lets calc for 0 and 1 alone, and based on it, 2 will get auto calculated

step1: iterate and count 0and 1 alone ( skip counting 2)

step2: two's count is : (arr.length) - (one's count) - (zero's count)
step3: make the existing arr null to make this algo inplace
step4: print number of 0,1,2 w,r,t count value

NOTE : this idea saves more than 50% memory for me ( from 30% in previous approach to, 86% efficient in this approach

var sortColors = function(arr) {
    let one=0, zero=0, two=0
    
    // step1 
    for(let elem of arr){
        if(elem == 0) zero++
        else if ( elem == 1) one ++
    }

    // step2
    two = (arr.length) - (zero) - (one) 

	// step3
    arr.length=0

    // step4
    for(let i=0;i<zero;i++) arr.push(0)
    for(let i=0;i<one;i++) arr.push(1)
    for(let i=0;i<two;i++) arr.push(2)    
};

Approach 2: One-pass algorithm

var sortColors = function(arr) {
    
    let low=0, mid=0, high=arr.length-1
    while ( mid <= high ) { 
    
        if( arr[mid] == 0 ){ 
            swap( low, mid ); 
            mid++; 
            low++ ;
        } 
    
        else if( arr[mid] == 1 ) {   
            mid++ ;  
        } 

        else if( arr[mid] == 2 ) {
            swap( mid,high ); 
            high--  
        } 
    }

    function swap(a,b) {
        [arr[b], arr[a]] = [arr[a], arr[b]]
    }
};

Approach) An intuitive approach

two-pass algorithm

var sortColors = function(arr) {
    
    let i=0
    for( let j=0; j<arr.length; j++){
        if(arr[j]==0){ 
            [arr[i], arr[j]] = [arr[j], arr[i]]
            i++
        }
    
    }

    let k=i
    for( let m=0; m<arr.length; m++){
        if(arr[m]==1){
             [arr[m], arr[k]] = [arr[k], arr[m]]
             k++
        }
    }   
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 75. Sort Colors

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!