MUYANG GUO / INDEX

LeetCode

LeetCode 75 Sort Colors - Medium

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the col…

·2 min read·#LeetCode#Medium#Python

75. Sort Colors — Medium

Open on LeetCode

Problem

Given an array 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.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's. Could you come up with a one-pass algorithm using only constant space?

Solution

### two pointers, quicksort partition two pass method:
 
class Solution:
    def sortColors(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        left, right = 0, len(nums) - 1
        new_left = self.partition(nums, left, right, 0)
        self.partition(nums, new_left, right, 1)
                
    def partition(self, nums, left, right, pivot):
        while left <= right:
            while left <= right and nums[right] != pivot:
                right -= 1
            while left <= right and nums[left] == pivot:
                left += 1
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        return left
            
 
### three pointers, best solution, one pass solution:
 
class Solution:
    def sortColors(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        # for all idx < p0 : nums[idx < p0] = 0
        # curr is an index of element under consideration
        p0 = curr = 0
        # for all idx > p2 : nums[idx > p2] = 2
        p2 = len(nums) - 1
 
        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

Comments