Sort Colors
TIME: O(n)
SPACE: O(1)
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.
Real Engineering Applications
In production systems, this concept directly maps to caching index layers, route lookups optimizations, compiler scope parsing validations, and multi-thread dependency schedulers.
Edge Cases to Consider
- Empty array or array of length 1
- Array containing only 1 color (e.g., [0, 0, 0] or [2, 2])
- Array containing only 2 of the 3 colors (e.g., [0, 2, 0, 2])
Common Traps & Pitfalls
- Incrementing the mid pointer after swapping with high. The swapped element from high must be inspected first.
- Using standard library sort which has O(N log N) runtime complexity.
- Using counting sort (two passes) when a single-pass in-place algorithm is requested.
DevJam Practice Engine v1.0ACCESSIBLE LAB
solution.js
Initializing Code Sandbox...
Console Output