On this page
Description
Sorting is often the step that turns a hard-looking problem into an easy one. Once the data is in order, overlapping intervals sit next to each other, duplicates are neighbors, and two pointers work. This skill covers that move: sort first, then scan. It also covers a faster cousin for data with only a few distinct values, the one-pass Dutch National Flag partition.
We'll go from simple to more technical:
- "Just sort it first" - and what it costs.
- Dutch National Flag: three pointers for three values.
- Where both show up in production (scheduling, priority buckets).
- Choosing between a general sort and a one-pass partition.
The approach: two ideas under one skill
1. "Just sort it first." Without sorting, "do any of these meetings overlap?" means comparing every pair, O(n^2). Sorted by start time, each meeting only needs comparing with the one before it. Take meetings from 13 to 14, 9 to 11, 10 to 12 and 15 to 16:
| Meeting (sorted by start) | Previous meeting ends at | Overlap? |
|---|---|---|
| 9 to 11 | ||
| 10 to 12 | 11 | yes: it starts at 10, before 11 |
| 13 to 14 | 12 | no |
| 15 to 16 | 14 | no |
Merging intervals, finding the closest pair and checking whether two arrays hold the same values all get easier the same way. The cost is O(n log n), and the original order is lost. If a later step needs the original positions, sort (value, originalIndex) pairs instead of bare values.
2. Dutch National Flag (three-pointer partitioning). When there are only a few known values, classically 0, 1 and 2, you don't need a general sort at all. Three pointers split the array as you go: everything before low is 0, everything between low and mid is 1, and everything after high is 2. mid looks at the next unknown element.
Sorting [2, 0, 1, 2, 0]:
| mid sees | Action | Array after | low, mid, high |
|---|---|---|---|
| 2 | swap with high, high down | 0 0 1 2 2 | 0, 0, 3 |
| 0 | swap with low, both up | 0 0 1 2 2 | 1, 1, 3 |
| 0 | swap with low, both up | 0 0 1 2 2 | 2, 2, 3 |
| 1 | mid up | 0 0 1 2 2 | 2, 3, 3 |
| 2 | swap with high, high down | 0 0 1 2 2 | 2, 3, 2 |
mid has passed high, so the array is sorted in one pass.
Java
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) { swap(nums, low++, mid++); }
else if (nums[mid] == 1) { mid++; }
else { swap(nums, mid, high--); } // note: mid does NOT advance here
}
Python
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # note: mid does NOT advance here
After a swap with high, mid stays put. The value that just came in from the end hasn't been looked at yet.
Where you'll see it
Splitting a queue of work into three severity levels in one pass is the same three-pointer shape. "Sort first" is the standard first move for scheduling and conflict checks, such as overlapping room bookings or clashing deployment windows.
Which tool for which job?
| You need | Use |
|---|---|
| Overlaps, merges, closest pairs | sort, then scan neighbors |
| Two or three known values (0/1/2) | a one-pass partition (Dutch National Flag) |
| Small integer range (0..k) | counting sort, O(n + k) |
| Sort, but keep the original positions | sort (value, index) pairs |
| Several sort keys | one sort with a tuple / thenComparing key |
| Only the k smallest | a heap or quickselect, not a full sort |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Dutch National Flag with many distinct values | it doesn't sort | a real sort, or counting sort |
Advancing mid after the high swap | an unexamined value is skipped | leave mid where it is |
| Sorting when the answer needs original indices | indices point into the sorted copy | sort (value, index) pairs |
(a, b) -> a - b as a Java comparator | overflow puts negatives last | Integer.compare(a, b) |
| Sorting numbers stored as strings | "10" comes before "9" | sort by the numeric value |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Dutch National Flag moves mid after a swap with low but not after a swap with high. Why?
Show answer
The value that comes in from low has already been looked at, since everything before mid has been. It's a 0 or a 1, so mid can move past it. The value that comes in from high hasn't been looked at at all. It could be anything, so mid stays to check it.
2. You need the closest pair of values and their original indexes. Why is sorting the bare values a problem?
Show answer
Sorting moves the values and forgets where each one came from. Once sorted, you can't recover the original indexes unless you kept them on purpose, for example by sorting (value, originalIndex) pairs.
3. An array holds only three known values, but a solution uses a general O(n log n) sort. Is the output wrong?
Show answer
No, it's correctly sorted. The miss is speed: an O(n) one-pass partition was available. That still counts in an interview, just differently from using Dutch National Flag where it doesn't apply, which gives wrong output.
Key takeaways
- "Just sort it" costs O(n log n) and works for any values. Dutch National Flag is O(n) and works for a few known values.
- After a swap with
high,midstays put. After a swap withlow, it moves on. - Sorting loses the original order. Sort
(value, originalIndex)pairs if you'll need it back. - Using Dutch National Flag on too many values is a correctness bug. Missing it where it fits is a speed miss.