[Solved] 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.

Question

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.

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 01, or 2.

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

Python Solution

class Solution:
    def sortColors(self, A: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l = 0
        r = len(A)-1
        scan = 0
        
        while scan<=r:
            if A[scan]==0:
                A[scan],A[l] = A[l],A[scan]
                l+=1
                scan+=1
            elif A[scan]==2:
                A[scan],A[r] = A[r],A[scan]
                r-=1
            else:
                scan+=1
        return(A)
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 517

Leave a Reply

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