Sort Colors

Clarify the problem:

• The problem requires us to sort an array containing only 0s, 1s, and 2s in-place without using any library sort functions.
• We need to modify the original array to have the numbers in the order of 0s, 1s, and 2s.

Analyze the problem:

• Input: An array containing only 0s, 1s, and 2s.
• Output: The same array sorted in-place.
• Constraints:
  • The length of the array is between 1 and 300.
  • The array elements can only be 0, 1, or 2.

Design an algorithm:

• We can solve this problem using the Dutch National Flag algorithm, also known as the Three-Way Partitioning algorithm.
• The algorithm uses three pointers to divide the array into three sections: 0s, 1s, and 2s.
• We initialize three pointers: low, mid, and high.
• The low pointer points to the start of the array, the mid pointer points to the current element being processed, and the high pointer points to the end of the array.
• We iterate through the array using the mid pointer.
• If the element at the mid pointer is 0, we swap it with the element at the low pointer and increment both low and mid pointers.
• If the element at the mid pointer is 1, we simply increment the mid pointer.
• If the element at the mid pointer is 2, we swap it with the element at the high pointer and decrement the high pointer.
• We continue this process until the mid pointer crosses the high pointer, ensuring that all elements are in the correct position.

Explain your approach:

• We will implement the Dutch National Flag algorithm to sort the array in-place.
• We initialize three pointers: low, mid, and high.
• We iterate through the array using the mid pointer.
• If the element at the mid pointer is 0, we swap it with the element at the low pointer and increment both low and mid pointers.
• If the element at the mid pointer is 1, we simply increment the mid pointer.
• If the element at the mid pointer is 2, we swap it with the element at the high pointer and decrement the high pointer.
• We continue this process until the mid pointer crosses the high pointer, ensuring that all elements are in the correct position.
• Finally, the array will be sorted in-place.

Write clean and readable code:

python

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], nums[high] = nums[high], nums[mid]
            high -= 1

Test your code:

• We can test the code with multiple test cases, including edge cases and corner cases, to ensure its correctness.
• For example:

  python

• # Example 1
  nums = [2,0,2,1,1,0]
  sortColors(nums)
  print(nums)
  # Output: [0, 0, 1, 1, 2, 2]
  
  # Example 2
  nums = [2,0,1]
  sortColors(nums)
  print(nums)
  # Output: [0, 1, 2]
  
  # Example 3
  nums = [0]
  sortColors(nums)
  print(nums)
  # Output: [0]
  

Optimize if necessary:

• The Dutch National Flag algorithm is an optimal solution with a time complexity of O(n), where n is the length of the input array.
• The algorithm performs a single pass through the array, ensuring that all elements are in the correct position.
• Therefore, no further optimization is necessary.

Handle error cases:

• There are no specific error cases to handle for this problem.
• The problem guarantees that the input array will contain only 0s, 1s, and 2s.

Discuss complexity analysis:

• The time complexity of the solution is O(n) since we perform a single pass through the array.
• The space complexity is O(1) since we sort the array in-place without using any additional data structures.
• The solution is efficient for the given constraints and provides the correct output.