Skip to main content

59. Sort Colors

mediumAsked at Ola

Sort an array of 0s, 1s, and 2s in-place in one pass.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array nums with n objects colored red, white, or blue (0/1/2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. You must solve this problem without using the library's sort function.

Constraints

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is 0, 1, or 2

Examples

Example 1

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

Example 2

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

Approaches

1. Counting sort

Count 0s, 1s, 2s in one pass; rewrite the array.

Time
O(n)
Space
O(1)
const c = [0,0,0];
for (const x of nums) c[x]++;
let i = 0;
for (let k=0;k<3;k++) while (c[k]--) nums[i++] = k;

Tradeoff:

2. Dutch national flag

Three pointers lo/mid/hi; swap with lo when 0, advance mid when 1, swap with hi when 2.

Time
O(n)
Space
O(1)
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--; }
  }
}

Tradeoff:

Ola-specific tips

Ola interviewers like the Dutch flag; tie it to bucketing live driver-statuses (idle/onTrip/offline) in one in-memory pass for the dispatcher.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Sort Colors and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →