Sort Colors - Solution
Solutions and explanations
It is a two-pass approach that sorts elements by first recording the frequency of each color and then rebuilding the array in the correct order.
from collections import Counter
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
freq = collections.Counter(nums)
idx = 0
for color in range(3):
while(freq[color]):
nums[idx] = color
freq[color] -= 1
idx += 1
Complexity Analysis
- Time Complexity:
O(n) - Space Complexity:
O(1)— as it uses a counter of size 3 or less, which is technically constant. Also, since the sorting is done in-place, no additional space is required for the output.
Here, n is input size.
-
It is a one-pass approach that sorts elements into three distinct sections, just like the Dutch flag has three separate color bands.
-
The algorithm is very similar to partitioning and uses three pointers to sort the elements:
- left: tracks where the next 0 should go.
- right: tracks where the next 2 should go.
- idx: current index being checked.
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
left, right = 0, len(nums) - 1
idx = 0
while idx <= right: # Important condition
if nums[idx] == 0:
nums[left], nums[idx] = nums[idx], nums[left] # Swap with left
left += 1
idx += 1
elif nums[idx] == 1: # No swap needed for 1
idx += 1
else:
nums[idx], nums[right] = nums[right], nums[idx] # Swap with right
right -= 1
Complexity Analysis
- Time Complexity:
O(n)— each element is examined at most once. - Space Complexity:
O(1)— the sorting is done in-place here, so no additional space is required for the output.
Here, n is the input size .