Sort Colors
Medium About 20 min Free, no account needed
Sort an array of 0s, 1s and 2s in a single pass.
The brief
Given an array nums containing only 0, 1 and 2 (red, white, blue),
return the array sorted ascending, without calling a library sort.
The obvious approach hand-rolls a quadratic sort, O(n2), which is far too slow on the
hidden 150,000-element test. You need O(n). The tiny value domain (only 0,
1, 2) is the lever.
Starter code
using System;
public class Solution
{
// TODO: return nums sorted ascending (values are only 0, 1 and 2).
public int[] SortColors(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Two pointers
- Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.
Related katas
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Find the Duplicate Number Medium Free Find the one repeated value in an array of n+1 numbers from 1..n, without allocating a set to do it.
- Longest Palindromic Substring (Length) Medium Free How long is the longest palindrome hiding in the string?