75. Sort Colors/ Dutch National Flag

Problem Statement

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.

Intuition

"New technique learned 
        Dutch National flag algorithm

Basically, 3 pointers -> 
low : 0's should be to left of it
high : 2's should be to right of it

Mid  pointer does swaps


"

Links

https://leetcode.com/problems/sort-colors/

Video Links

https://www.youtube.com/watch?v=oaVa-9wmpns&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=3

Approach 1:

Dutch National Flag Algorithm

C++

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low=0;
        int mid=0;
        int high=nums.size()-1;
        
        while(mid<=high){
            if(nums[mid]==0)
                swap(nums[mid++],nums[low++]);
            else if(nums[mid]==1)
                mid++;
            else
                swap(nums[mid],nums[high--]);
        }
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems