Flags in Three Colors

Medium

Flags of three colors are planted along a running track. The color of the i-th flag is stored in flags[i]: 0 is red, 1 is white, 2 is blue. Rearrange the flags so that all the red ones come first, then all the white ones, then all the blue ones. Return the rearranged flags. The built-in sort is off limits. Try to do it in a single pass with O(1) extra memory.

Example 1

flags=[2, 1, 0, 1, 2, 0] → [0, 0, 1, 1, 2, 2]

The answer is [0, 0, 1, 1, 2, 2].

Example 2

flags=[1, 0] → [0, 1]

The red flag moves in front of the white one: [0, 1].

Example 3

flags=[2] → [2]

Constraints

1 ≤ len(flags) ≤ 300
flags[i] is 0, 1 or 2

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Sorting

Similar problems

Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Studios for Recording Sessions Medium Triples Under a Limit Medium

Input

flags=[2, 1, 0, 1, 2, 0]

Expected

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

Run checks the first 3 tests in your browser. Submit checks all 38 tests on the server, hidden ones included.