75. Sort Colors — LeetCode(Python)

2 min readJul 5, 2022

I got you!

Problem:

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.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Solution:

We can use bucket sort, which would give us the required runtime and space complexity, but let’s use a less trivial algorithm.

l, r = 0, len(nums) - 1
i = 0
        
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

Explanation —

We are using the famous Dutch National Flag algorithm, using two-pointers.

We initialize two pointers, l and r at the opposite ends of the array, and then we traverse through the array.

If the value of nums[i] is 0, we swap nums[i] and nums[l]. And we increment the left pointer.

If the value of nums[i] is 2, we swap nums[i] and nums[r]. And we increment the right pointer.

And after every iteration, we increment the current i pointer.

Note that in the 2nd case, when nums[i] == 2, we decrement i because we do not want it to shift right now. This is because, we still might have a zero in the middle of the array, which we don’t want. So we only shift the i pointer, when we are sure that the left part of the array, before index i has been filled with 0's.

Time and Space Complexity —

Since we are only traversing through the array at most once, we can say that our algorithm runs in linear time. Also, we require constant extra space since only a few pointers have been used.

Thus, if n is the length of the array nums,

Time Complexity: O(n)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏