Sort Colors

MediumTwo Pointersdutch national flag

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an integer array nums where every element is one of three values: 0, 1, or 2. These values represent three different colors (think of them as red, white, and blue). Rearrange the elements of the array so that all the 0s come first, followed by all the 1s, and finally all the 2s. In other words, return the array sorted in non-decreasing order. The interesting part of this problem is the follow-up challenge: can you do it in a **single pass** over the array using only **constant extra space**, without relying on a library sort? A common naive approach is to count how many of each value appear and then overwrite the array, but that requires two passes. The classic one-pass technique uses three pointers to partition the array into three regions as you scan. Return the rearranged array.

Examples

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
All zeros are grouped first, then the ones, then the twos.
Input: nums = [2,0,1]
Output: [0,1,2]
Each color appears once, so the result is simply 0, 1, 2.
Input: nums = [0]
Output: [0]
A single element is already sorted.

Constraints

  • `1 <= nums.length <= 300`
  • `nums[i]` is either `0`, `1`, or `2`
  • Aim for a one-pass algorithm using only `O(1)` extra space.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.