Sort Colors

Number of Provinces

Non-overlapping Intervals

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

Given an array `nums` containing only `0`, `1`, and `2`, reorder it in-place so equal values are grouped together in the order red, white, blue. Return the final array after the in-place updates.

## Example
```
Input: {"nums":[2,0,2,1,1,0]}
Output: [0,0,1,1,2,2]
```

**Constraints**
- 0 <= nums.length <= 300
- nums[i] is 0, 1, or 2

**Follow-up**
Can you solve it in one pass with constant extra space and without using counting sort?

- Sort an array containing only 0s, 1s, and 2s in a single in-place pass, without calling a general sort and without a two-pass counting sort (the follow-up explicitly asks for one pass).
- "In-place" plus "one pass" rules out building a new array or scanning the array twice — the pointers have to make a final decision about each value as they go.

Understand the Goal

- The Dutch National Flag partition: maintain three pointers `low`, `mid`, `high` that divide the array into four regions at all times: `[0, low)` is all 0s, `[low, mid)` is all 1s, `[mid, high]` is unknown/unprocessed, and `(high, n)` is all 2s.
- `mid` is the scanning cursor; `low` and `high` are the boundaries of the two settled regions, and they only ever move inward.

Choose the Core Pattern

- While `mid <= high`, look at `nums[mid]`:
  - If it's 0: swap it with `nums[low]`, then advance both `low` and `mid`. Advancing `mid` is safe: if `low < mid`, the value moved from `low` is a previously classified 1; if `low == mid`, the swap is a no-op. In either case, the value now at `mid` needs no further inspection.
  - If it's 1: it's already in the right region, just advance `mid`.
  - If it's 2: swap it with `nums[high]`, then decrement `high` only — do **not** advance `mid`. The value swapped in from `high` came from the unprocessed region and hasn't been classified yet, so `mid` must look at it again next iteration.

Build the Algorithm

- Empty or single-element array: the loop condition `mid <= high` is false or true-once, both handled without special-casing.
- Already sorted (`[0,0,1,1,2,2]`): every comparison takes the "already in place" branch (0-swap-with-self or the 1 case), no wasted work.
- All one color (`[1,1,1]`): `mid` just walks to the end, `low`/`high` never move.
- All same color at the boundary, e.g. all 2s (`[2,2,2]`): each step swaps `nums[mid]` with `nums[high]` (sometimes a no-op self-swap) and shrinks `high`, until `mid > high`.