75. Sort Colors

Problem Statement

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

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]

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

Solution Approach

The solution utilizes two-pointer technique to segregate colors represented by integers 0, 1, and 2.

Algorithm

1. Initialize three pointers at the start and end of the array.
2. Traverse through the array, swapping 0s to the left and 2s to the right.
3. Move the middle pointer accordingly to ensure all 1s remain in the center.

Implement

    class Solution:
      def sortColors(self, nums: List[int]) -> None:
        p0, p1, p2 =  0, 0, len(nums) - 1
        while p1 <= p2:
            if nums[p1] == 0:
                nums[p0], nums[p1] = nums[p1], nums[p0]
                p0 += 1
                p1 += 1
            elif nums[p1] == 2:
                nums[p1], nums[p2] = nums[p2], nums[p1]
                p2 -= 1
            else:
                p1 += 1

    
    

Twitter  facebook  Email