LeetMotion
Given an array nums with n objects colored red, white, or blue, represented by integers 0, 1, and 2 respectively, sort them in-place so that objects of the same color are adjacent, in the order red, white, and blue.
You must solve this problem without using the library's sort function.
lo are all 0s, elements after hi are all 2s, elements between lo and mid are all 1s.nums[mid]=0: swap with lo, advance lo and mid. If nums[mid]=1: just advance mid. If nums[mid]=2: swap with hi, decrease hi (don't advance mid — need to check again).ER systems categorize patients as critical (0), moderate (1), or stable (2). The Dutch National Flag algorithm sorts patients in a single linear scan without additional memory — crucial when the system processes thousands of arrivals simultaneously. Just as the algorithm partitions the array in-place using three pointer boundaries, an ER triage system can re-order its patient queue on the fly with no extra storage, ensuring critical patients are always at the front.
Count the frequency of 0s, 1s, and 2s in a first pass, then overwrite the array in a second pass using those counts.
count[0] zeros, then count[1] ones, then count[2] twos.Why it's not optimal: It requires two passes over the data and doesn't sort in a single scan. The Dutch National Flag algorithm achieves the same result in a single pass.
def sortColors(nums): count = [0, 0, 0] for n in nums: count[n] += 1 idx = 0 for color in [0, 1, 2]: for _ in range(count[color]): nums[idx] = color; idx += 1
Maintain three pointers: lo, mid, and hi. The invariant is: all elements before lo are 0, all elements after hi are 2, and all elements between lo and mid are 1.
lo = mid = 0, hi = n - 1.mid <= hi, inspect nums[mid].nums[mid] == 0: swap nums[lo] and nums[mid], then increment both lo and mid.nums[mid] == 1: increment mid only.nums[mid] == 2: swap nums[mid] and nums[hi], then decrement hi (do not advance mid — the swapped value needs checking).A single pass of O(n) with O(1) space — no extra memory needed beyond the three pointer variables.
Discussion
…