Sort Colors 🐘

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.

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:

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

Solution

Time Complexity O(n log n)

Space O(1)

Time Complexity O(n log n)

Space Complexity O(n)

Time Complexity O(2n)

Space Complexity O(1)

Time Complexity O(2n)

Space Complexity O(1)

Do you see that green follow button? 🐌

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store