Sort an RGB Record Collection In Place
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Sort an RGB Record Collection In Place
A `RecordCollection` stores a fixed-length list of colored records. Every record has exactly one color, encoded as an integer:
- `0` — Red
- `1` — Green
- `2` — Blue
The collection exposes only three operations, all already implemented for you (you do **not** write them and you have **no** other way to touch the underlying storage):
- `size()` — returns the number of records, `n`.
- `getColor(i)` — returns the color (`0`, `1`, or `2`) of the record at index `i` (`0 <= i < n`).
- `swap(i, j)` — swaps the records at indices `i` and `j` in place.
Write a function that reorders the records **in place** so that all Red records come first, then all Green records, then all Blue records.
You may inspect and rearrange records **only** through `getColor` and `swap` — you cannot read into a separate array, build a counted output, and copy it back. After your function finishes, reading `getColor(0), getColor(1), ..., getColor(n-1)` must yield a non-decreasing sequence (every `0` before every `1`, every `1` before every `2`).
## Requirements
- Run in **O(n)** time.
- Use **O(1)** extra space.
- Make a **single pass** — do not count occurrences and then overwrite by color; rearrange using `swap` only.
## Example
Given a collection whose colors are, by index:
```
index: 0 1 2 3 4 5 6
color: 2 0 2 1 1 0 1 (Blue Red Blue Green Green Red Green)
```
After sorting in place, reading the colors back in index order must give:
```
0 0 1 1 1 2 2 (Red Red Green Green Green Blue Blue)
```
(The exact final positions of equal-colored records need not match any particular original order — only the color grouping and ordering matter.)
## Constraints & Assumptions
- `0 <= n <= 10^5`.
- Every `getColor(i)` returns one of exactly `0`, `1`, or `2`.
- `swap(i, j)` is valid for any `0 <= i, j < n` (including `i == j`, which is a no-op).
- An empty collection (`n == 0`) is already sorted; return without calling any operation.
## Function Signature
Implement:
```
sort_records(collection)
```
where `collection` supports `collection.size()`, `collection.getColor(i)`, and `collection.swap(i, j)`. The function returns nothing; it mutates the collection in place.
Quick Answer: This question evaluates a candidate's ability to implement an in-place, single-pass partitioning algorithm under strict interface constraints, commonly known as the Dutch National Flag problem. It tests practical application of the three-pointer swap technique to achieve O(n) time and O(1) space, assessing algorithmic reasoning within coding interviews for software engineering roles.
You are given a list `nums` representing a collection of colored records. Every record has exactly one color, encoded as an integer:
- `0` — Red
- `1` — Green
- `2` — Blue
Reorder the records **in place** so that all Red records come first, then all Green records, then all Blue records. After sorting, reading the colors left to right must give a non-decreasing sequence (every `0` before every `1`, every `1` before every `2`). Return the same list after sorting it.
**Requirements**
- Run in **O(n)** time.
- Use **O(1)** extra space.
- Make a **single pass** — do **not** count occurrences and then overwrite by color. Rearrange using swaps only.
**Example**
```
Input: [2, 0, 2, 1, 1, 0, 1] (Blue Red Blue Green Green Red Green)
Output: [0, 0, 1, 1, 1, 2, 2] (Red Red Green Green Green Blue Blue)
```
The exact final positions of equal-colored records need not match any particular original order — only the color grouping and ordering matter.
**Constraints**
- `0 <= n <= 10^5`
- Every element is exactly `0`, `1`, or `2`.
- An empty collection (`n == 0`) is already sorted.
Constraints
- 0 <= n <= 10^5
- Every element of nums is exactly 0, 1, or 2
- Must sort in place using O(1) extra space
- Single pass; rearrange using swaps only (no counting-then-overwriting)
Examples
Input: [2, 0, 2, 1, 1, 0, 1]
Expected Output: [0, 0, 1, 1, 1, 2, 2]
Explanation: The example: Blue/Red/Blue/Green/Green/Red/Green groups into two Reds, three Greens, two Blues.
Input: []
Expected Output: []
Explanation: Empty collection is already sorted; no swaps performed.
Input: [1]
Expected Output: [1]
Explanation: Single Green record; nothing to reorder.
Input: [2, 2, 2]
Expected Output: [2, 2, 2]
Explanation: All Blue; the high pointer walks past everything without changing order.
Input: [0, 1, 2]
Expected Output: [0, 1, 2]
Explanation: Already sorted; each element is placed by advancing the pointers, no real movement.
Input: [2, 1, 0]
Expected Output: [0, 1, 2]
Explanation: Fully reversed; the 2 goes to the back, the 0 to the front, the 1 stays put.
Input: [1, 0, 0, 2, 1, 2, 0, 1]
Expected Output: [0, 0, 0, 1, 1, 1, 2, 2]
Explanation: Mixed with duplicates: three Reds, three Greens, two Blues after partitioning.
Hints
- Picture three regions as you scan: a settled block of 0s at the front, a settled block of 2s at the back, and an unexamined middle. Maintain the boundaries with three pointers: low (end of the 0s), mid (the current element), and high (start of the 2s).
- When nums[mid] == 0, swap it into the 0-region and advance both low and mid. When nums[mid] == 1, it is already in the right region, so just advance mid.
- When nums[mid] == 2, swap it to the back (position high) and decrement high, but do NOT advance mid — the value that just came from the back is still unexamined and must be classified on the next iteration.