75.Sort Colors

Tags: [sort], [bucket_sort], [three_pointer], [trick], [quick_sort], [partition], [in_place]

Com: {fb}

Link: https://leetcode.com/problems/sort-colors/#/description

Given an array withnobjects colored red, white or blue, sort them 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.

click to show follow up.

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 an one-pass algorithm using only constant space?

Solution: Swap, Low, Mid, High, Partition, In Place

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return

        low = 0
        mid = 0
        high = len(nums) - 1

        while mid <= high:
            if nums[mid] != 0 and nums[mid] != 2:
                mid += 1
            elif nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            else:
                # nums[mid] = 2
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

Revelation:

• Very similar to quick sort's partition, but quick sort's partition is split the array to two parts: everything <= arr[pivot_index] to the left of the array, everything > arr[pivot_index] to right of the array. But here we want to partition the array to three parts: everything < pivot to left of the array, everything > pivot to right of the array, everything == pivot keep in middle of the array.
• Why If M > H we stop, pleas see the below example:

Note:

• Time complexity = O(n), n is the number of elements in the given array.
• Space complexity = O(1).

Solution: Bucket Sort

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return

        # bucket sort
        buckets = [[] for _ in xrange(3)]
        for num in nums:
            buckets[num].append(num)

        index = 0
        for bucket in buckets:
            for elem in bucket:
                nums[index] = elem
                index += 1

Revelation:

• The bucket sort, the each bucket is an array, so the buckets is an array of array.

Note:

• Time complexity = O(n), n is the number of elements of the given array.
• Space complexity = O(1).