Member-only story
Leetcode: Sort Colors Python Solution
The Question:
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
We are given a follow up and told to solve this problem without using the library’s sort function and also whether we can up with a one-pass algorithm using only 0(1) constant space.
Here is an example of how the output should look like once solved
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]This is a leetcode medium level question.common during coding interviews as well! See, the obvious or rather straightforward solution here would be using a counting sort whereby, you first iterate the array counting the numbers of zeros,ones, and twos and then overwriting the array with the total number of zeros,ones and followed by twos. However this solution has a space limitation. It’s space complexity is 0(n) which means it will be need more space should the array be bigger. Hence the reason why we are being asked whether we can come up with a one-pass algorithm using only constant-space
