Sort Colors
- 3 min read
- Array
- LC-Medium
3 years ago
Solution 1 (Two-Pass Bucket Sort)
- Iterate hashmap, storing the frequency of 0, 1, and 2
- Go over the array a second time, this time replacing the values with the number of 0s, 1s, and 2s
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def sortColors(self, nums: List[int]) -> None:
counts = Counter(nums)
i = 0
for num in [0, 1, 2]:
for _ in range(counts[num]):
nums[i] = num
i += 1
Solution 2 (One-Pass QuickSort Partition)
- Variant of Bucket Sort
- Two pointers, left and right which are boundaries of the leftmost and rightmost elements
- Leftmost elements will be 0s, rightmost elements will be 2s
- Think of it like this: all elements before the left pointer will be 0s, and all elements after the right pointer will be 2s
- We iterate through each element, starting from i = 0
- Whenever we encounter a 0 or 2, we swap it with the element at left pointer and right pointer respectively, i.e.
nums[i], nums[l] = nums[l], nums[i] - We need to then increment the left pointer or decrement the right pointer to move the boundaries
- There is just one edge case, whenever we encounter a 2 and then swap it with the right pointer, we should not increment i, since the element that was just swapped with 2 might be a 0 or a 1, and further needs to be processed
- Remember that the number at left pointer could only contain either 0 or 1, it cannot contain a 2 because
imoves faster and any 2 would've been already swapped- Also remember that the right pointer could have either 0, 1, or 2. Hence the edge case. It will be a problem if the right pointer is pointing at a 1
- If we incremented i immediately after the swap, we could end up moving a 0 to the left side of the array, which would violate the sorting rule of the problem
- BRO FAAEZ LOOK FUCKING HERE. USE THE ARRAY [1, 2, 0] TO UNDERSTAND WHY WE SHOULD NOT INCREMENT
iWHENEVER A 2 IS SWAPPED.
- Remember that the number at left pointer could only contain either 0 or 1, it cannot contain a 2 because
def sortColors(self, nums: List[int]) -> None:
i, l, r = 0, 0, len(nums) - 1
while i <= r:
if nums[i] == 0:
nums[i], nums[l] = nums[l], nums[i]
l += 1
elif nums[i] == 2:
nums[i], nums[r] = nums[r], nums[i]
r -= 1
i -= 1
i += 1