Sort Colors

Sort Colors is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the In-place Array Modification subpattern.

Problem statement

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?

Topics and companies

Topics: Array, Two Pointers, Sorting.

Reported in interviews at Microsoft, Facebook, eBay, Amazon, Oracle, Adobe, Nvidia, Expedia.

How to practise Sort Colors on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) — Each element is visited at most once, so the algorithm runs in linear time relative to the size of the input array. time and O(1) — The algorithm uses only a constant amount of extra space for pointers and temporary variables, regardless of input size. space.

Open Sort Colors in the code editor, or read the Sort Colors editorial for a worked solution with its approach and complexity analysis.

Where Sort Colors sits in the DSA pattern sheet

• Two Pointers pattern guide
• In-place Array Modification subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Sort Colors

Other problems that use the same In-place Array Modification and Two Pointers techniques:

• Intersection of Two Arrays — Easy, same subpattern
• Move Pieces to Obtain a String — Medium, same subpattern
• Move Zeroes — Easy, same subpattern
• Remove Duplicates from Sorted Array — Easy, same subpattern
• Remove Duplicates from Sorted Array II — Medium, same subpattern
• Remove Element — Easy, same subpattern