Sort Colors

Back to problems

Leetcode

Medium

Arrays

Sorting

Two Pointers

Sort Colors

Reorder an array containing only 0s, 1s, and 2s so that equal values are grouped together in increasing order.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Dutch National Flag

gfg

Primary

Problem Statement

You are given an integer array nums where each element is either 0, 1, or 2. Rearrange the array in place so that all 0s come first, followed by all 1s, and then all 2s.

Do not use built-in sorting for the main solution idea.

The goal is to produce the array in nondecreasing order while using only constant extra space if possible.

Input Format

An integer array nums
Each value in nums is one of 0, 1, or 2

Output Format

Modify nums in place so it is sorted as 0s, then 1s, then 2s

Constraints

1 <= nums.length <= 300
nums[i] is 0, 1, or 2
Try to use $O(1)$ extra space

Examples

Sample cases returned by the problem API.

Example 1

Input

nums = [2,0,2,1,1,0]

Output

[0,0,1,1,2,2]

Explanation

After rearrangement, all 0s appear first, then 1s, then 2s.

Example 2

Input

nums = [2,0,1]

Output

[0,1,2]

Explanation

The array is reordered in nondecreasing order in place.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress