algoadvance

You have an array with n objects colored red, white, or blue, represented by the integers 0, 1, and 2, respectively. Sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

You must solve this problem without using the library’s sort function.

Clarifying Questions

1. What is the range of values in the input array?
   • The values are exclusively 0, 1, and 2.
2. Can I use extra space for another array or data structure?
   • No, the solution must be in-place.
3. What should be the input and output of the function?
   • The function should modify the input array in place, with no return value.

Strategy

We can solve this problem using the Dutch National Flag problem algorithm, which efficiently sorts the array with one pass (O(n) time complexity) and constant space (O(1) space complexity).

The idea is to use three pointers:

• low to track the end of the red zone (0s).
• mid to iterate through the array.
• high to track the start of the blue zone (2s).

We’ll move the mid pointer through the array and swap values to ensure that all 0s are before it and all 2s are after it, while keeping 1s in the middle.

Code

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[high], nums[mid] = nums[mid], nums[high]
            high -= 1

# Example usage:
nums = [2, 0, 2, 1, 1, 0]
sortColors(nums)
print(nums)  # Output should be [0, 0, 1, 1, 2, 2]

Time Complexity

• Time Complexity: O(n), where n is the length of the array. This is because we make a single pass through the array with the mid pointer, and each element is evaluated at most once.

• Space Complexity: O(1), as we are sorting the array in place without using any extra space.

This approach ensures that the array is sorted in a single traversal which is highly efficient for this problem.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?