0075.Sort Colors

Link: 75. Sort Colors
Track: Amazon Tag

Question

Restate the problem

• Given an integer array nums containing only 0, 1, and 2,
• Sort the array in-place so that all 0s come first, then 1s, then 2s
• Without using built-in sort
• have negtive number

Edge Case

• [-1, -1, -1]
• nums = []
• already sorted

---

Method 1 - Counting
Method 2 - Dutch National Flag (Three pointers, One-pass)

Method 2 - Dutch National Flag (Three pointers, One-pass)

Approach

• Use three pointers to partition the array in one pass:
  • left: next position to place 0
  • mid: current index scanning the array
  • right: next position to place 2

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Code

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        left, right = 0, len(nums) - 1
        mid = 0
        while mid <= right:
            if nums[mid] == 0:
                nums[mid], nums[left] = nums[left], nums[mid]
                mid += 1
                left += 1
            elif nums[mid] == 1:
                mid += 1
            elif nums[mid] == 2:
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1
                # mid += 1

---

History

• Feb-15-2026 Peeked
  • wrong approach