Sort Colors LeetCode Solution

January 9, 2024

Sort Color 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 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 :

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

Output: [0,0,1,1,2,2]

Minimum Window Substring Leetcode Problem Solution :

Constraints :

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

Example 1:

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

Idea to solve:

The problem requires us to sort an array of integers representing colors in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We are given that the colors red, white, and blue are represented by the integers 0, 1, and 2 respectively.

Approach:

The Dutch National Flag algorithm, also known as 3-way partitioning, is an algorithm for sorting an array containing three distinct values. The algorithm was designed to solve the problem of sorting an array containing only 0s, 1s, and 2s, which is similar to the problem in the given question.

The algorithm works by maintaining three pointers: low, mid, and high. The low pointer points to the beginning of the array, the high pointer points to the end of the array, and the mid pointer starts at the beginning of the array and moves through it.

The idea behind the algorithm is to keep all the 0s before the low pointer, all the 2s after the high pointer, and all the 1s between the low and high pointers. The algorithm moves the mid pointer through the array, comparing the value at each position with 1. If the value is 0, the element is swapped with the element at the low pointer, and the low and mid pointers are incremented. If the value is 2, the element is swapped with the element at the high pointer, and the high pointer is decremented. If the value is 1, the mid pointer is simply incremented.

The algorithm terminates when the mid pointer crosses the high pointer, indicating that all the elements have been processed and the array is sorted.

Complexity:

Time complexity: O(n)
Space complexity: O(1)

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

C++

Java

Python

C++

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

Java

public class Solution {
    public void sortColors(int[] nums) {
        int l = 0;
        int m = 0;
        int h = nums.length - 1;
        
        while (m <= h) {
            if (nums[m] == 0) {
                int temp = nums[l];
                nums[l] = nums[m];
                nums[m] = temp;
                l++;
                m++;
            } else if (nums[m] == 1) {
                m++;
            } else if (nums[m] == 2) {
                int temp = nums[m];
                nums[m] = nums[h];
                nums[h] = temp;
                h--;
            }
        }
    }
}

Python

class Solution:
    def sortColors(self, nums):
        l = 0
        m = 0
        h = len(nums) - 1
        
        while m <= h:
            if nums[m] == 0:
                nums[l], nums[m] = nums[m], nums[l]
                l += 1
                m += 1
            elif nums[m] == 1:
                m += 1
            elif nums[m] == 2:
                nums[m], nums[h] = nums[h], nums[m]
                h -= 1

Unlock this article for Free,
by logging in

Sort Colors LeetCode Solution

Sort Color Leetcode Problem :

Minimum Window Substring Leetcode Problem Solution :

Constraints :

Example 1:

Idea to solve:

Approach:

Complexity:

Prime Course Trailer

Related Banners

Code :

30+ Companies are Hiring

Unlock this article for Free, by logging in

Sort Colors LeetCode Solution

Sort Color Leetcode Problem :

Minimum Window Substring Leetcode Problem Solution :

Constraints :

Example 1:

Idea to solve:

Approach:

Complexity:

Prime Course Trailer

Related Banners

Code :

30+ Companies are Hiring

Unlock this article for Free,
by logging in