You are given an array nums where each value is 0, 1 or 2 (think red, white and blue). Sort it in place so that all 0s come first, then all 1s, then all 2s. Do not use a library sort.
Example 1
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2
Input: nums = [2,0,1]
Output: [0,1,2]
Constraints
- 1 <= nums.length <= 300
- nums[i] is 0, 1 or 2
Hints
Frequently asked at: Microsoft, Amazon, Adobe, Flipkart, Samsung
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A general sort is O(n log n), and counting sort needs two passes. The Dutch National Flag algorithm does one pass by keeping three regions: everything before low is 0, everything between low and mid is 1, and everything after high is 2. The unknown region is mid..high. Each step looks at nums[mid] and moves it into the correct region with one swap.
Algorithm
- Set
low = 0,mid = 0,high = n - 1. - While
mid <= high: ifnums[mid] == 0, swap withnums[low], thenlow++andmid++. - If
nums[mid] == 1, justmid++. - If
nums[mid] == 2, swap withnums[high]andhigh--(do not movemid, the swapped-in value is unchecked).
Time:
O(n)Space: O(1)Interview tip: The classic bug is advancing
mid after swapping with high. The value that came from high has not been examined yet, so mid must stay.class Solution: def sortColors(self, nums: List[int]) -> None: 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 # mid stays: new value not checked yetCtrl + Enter runs the examples