LC-0075 Medium LeetCode

75. Sort Colors

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 67% Topics: Array, Two Pointers, Sorting

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        def triPartition(nums, target):
            i, left, right = 0, 0, len(nums)-1
            while i <= right:
                if nums[i] > target:
                    nums[i], nums[right] = nums[right], nums[i]
                    right -= 1
                else:
                    if nums[i] < target:
                        nums[left], nums[i] = nums[i], nums[left]
                        left += 1
                    i += 1

        triPartition(nums, 1)

Solution from kamyu104/LeetCode-Solutions · MIT