Question:

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.

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

Implement the function sortColors(nums: List[int]) -> None to solve the problem in-place.

Example:

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

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

Note:

• You are not allowed to use the sort function.
• You should solve the problem with constant space complexity (in-place) and linear time complexity.

Answer:

To solve this problem, we can use the Two Pointers technique. We can create three pointers, low, mid, and high. The low pointer will point to the index where the next 0 should be placed, the mid pointer will traverse the array, and the high pointer will point to the index where the next 2 should be placed. Initially, low and mid will be set to 0, and high will be set to the last index of the array. We will iterate until mid <= high and perform the following steps:

• If nums[mid] is 0, we swap the elements at indices low and mid and increment both low and mid by 1. This ensures that the next 0 will be placed at index low.
• If nums[mid] is 1, we increment mid by 1 and continue to the next iteration as the order of 1s should remain unchanged.
• If nums[mid] is 2, we swap the elements at indices mid and high and decrement high by 1. This ensures that the next 2 will be placed at index high.

Finally, when the iteration is completed, the array will be sorted in place with all 0s at the beginning, all 1s in the middle, and all 2s at the end.

Here is the implementation in Python:

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1

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

    return nums

The time complexity of this approach is O(n) since we traverse the array only once. The space complexity is O(1) as we are sorting the array in place without using any extra space.