Sort Colors (One-Pass, Constant Space) Medium 0 attempts
LeetCode ↗

Sort Colors (One-Pass, Constant Space)

Medium Two Pointer LeetCode

You're given an array whose elements are only 0, 1, or 2. Sort it in-place in a single pass without using extra space for counting — this is a variant of the classic Dutch National Flag problem.

Input Format
Implement sortColors(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Modify argument 1 in place. The editor compares its final value; the function return value is ignored.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums = [1]
Output
[1]
Constraints
  • 1 <= N <= 10^3
  • 0 <= arr[i] <= 2
Test Cases (2)
Case 1
Args: [[2,0,2,1,1,0]] Expected: [0,0,1,1,2,2]
Case 2
Args: [[1]] Expected: [1]
Topics
Two Pointer

Three-Way Partitioning

javascript
function sortColors(nums) {
  let lo = 0, mid = 0, hi = nums.length - 1;
  while (mid <= hi) {
    if (nums[mid] === 0) { [nums[lo], nums[mid]] = [nums[mid], nums[lo]]; lo++; mid++; }
    else if (nums[mid] === 1) mid++;
    else { [nums[mid], nums[hi]] = [nums[hi], nums[mid]]; hi--; }
  }
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript