Skip to main content

58. Sort Colors

mediumAsked at Salesforce

Sort an array of 0s, 1s, and 2s in-place. Salesforce uses this to test the Dutch National Flag (DNF) three-way partitioning algorithm.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses DNF in their priority-queue bucketing for the Bulk API queue.
  • LeetCode Discuss (2025-10)— Common Salesforce filter for three-way partition awareness.

Problem

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. 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 (two pass)

Count 0s, 1s, 2s. Overwrite the array with counts.

Time
O(n)
Space
O(1)
function sortColors(nums) {
  const count = [0, 0, 0];
  for (const n of nums) count[n]++;
  let idx = 0;
  for (let v = 0; v < 3; v++) for (let i = 0; i < count[v]; i++) nums[idx++] = v;
}

Tradeoff: Two passes. Acceptable but Salesforce wants single-pass DNF.

2. Dutch National Flag (single pass)

lo, mid, hi pointers. If nums[mid] == 0, swap with lo and advance both. If 1, advance mid. If 2, swap with hi and decrement hi.

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: Single pass. The invariant: [0, lo) are all 0; [lo, mid) are all 1; (hi, end) are all 2. Stop when mid > hi.

Salesforce-specific tips

Salesforce uses DNF for prioritized job queues in their Bulk API (high/medium/low priority bucketing). They grade on whether you can articulate the three-region invariant and explain why mid doesn't advance after a 2-swap. Bonus signal: explain that NOT advancing mid is intentional (the swapped-in value from hi is unknown and must be re-checked).

Common mistakes

  • Advancing mid after swapping with hi — corrupts the invariant (the unknown swapped value isn't checked).
  • Using mid < hi instead of mid <= hi — misses the last element.
  • Initializing all pointers incorrectly — lo=0, mid=0, hi=n-1 is the canonical setup.

Follow-up questions

An interviewer at Salesforce may pivot to one of these next:

  • Generalize to k colors (counting sort).
  • Sort an array of just 0s and 1s in one pass.
  • Wiggle sort (LC 280).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why doesn't mid advance after swapping with hi?

Because the value swapped in from hi is unknown (could be 0, 1, or 2). We must re-examine the new nums[mid].

Why DOES mid advance after swapping with lo?

Because the value swapped in from lo is already a 1 (by the invariant that [lo, mid) are all 1s). We've already classified it correctly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →