Skip to main content

75. Sort Colors

https://leetcode.com/problems/sort-colors/

Python​

Bubble Sort​

  • Time: O(N^2)
  • Space: O(1)
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        for i in range(len(nums)):
            for j in range(len(nums)):
                if nums[i] < nums[j]:
                    nums[i], nums[j] = nums[j], nums[i]

Two Pointer​

  • Time: O(N)
  • Space: O(1)

Since the only possible value in nums are 0, 1, 2 Exhaustive the values with one-pass loop

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0, p1, p2 = 0, 0, len(nums)-1
        
        while p1 <= p2:
            # print(p0, p1, p2, nums)
            if nums[p1] == 0:
                nums[p0], nums[p1] = nums[p1], nums[p0]
                p0 += 1
                p1 += 1  # Prevnt infinity loop
                continue
            
            if nums[p1] == 2:
                nums[p1], nums[p2] = nums[p2], nums[p1]
                p2 -= 1
                continue

            # nums[p1] == 1
            p1 += 1