Back to Main
Learn DSA
Depth-First Search
Greedy Algorithms
Get Premium
Two Pointers
Sort Colors
medium
DESCRIPTION (credit Leetcode.com)
Write a function to sort a given integer array nums in-place (and without the built-in sort function), where the array contains n integers that are either 0, 1, and 2 and represent the colors red, white, and blue. Arrange the objects so that same-colored ones are adjacent, in the order of red, white, and blue (0, 1, 2).
Input:
Output:
Explanation
We can understand this algorithm by looking at the invariants which hold true after each iteration:
- All elements to the left of the left are 0s.
- All elements between left and i - 1 are 1s.
- All elements between i and right are unsorted.
- All elements to the right of right are 2s.
Let's now see how we maintain these invariants as we iterate through the array.
Sorting 0s
When i is equal to 0, invariant 2 tells us there are two possible values for left: 0 or 1.
Let's consider the case when left == 1 first. We swap i with left. This allows us to increment the left pointer to maintain invariant 1. Since we know that the new item at i is a 1, we can also increment i to maintain variant 2.
Now let's consider what happens when left == 0, which happens when we haven't encountered any 1s yet and i == left. We swap i with left (which is itself) and increment left to maintain invariant 1. Since we still haven't encountered any 1s, we can increment i to maintain invariant 2. In other words, the "ones" region remains empty.
Sorting 1s
When i == 1, we can simply increment i to maintain invariant 2.
Sorting 2s
When i == 2, we swap i with right. This allows us to decrement right to maintain invariant 4. But since the new item at i came from the unsorted region, the new item at i is still unsorted, so we have to go through another iteration to correctly sort it.
Termination
When i surpasses right the unsorted region is empty and the entire array is sorted.
Solution
sort colors
0 / 20
Python
Login to track your progress
Your account is free and you can post anonymously if you choose.