Pattern — Sort Then Search

Khi nào dùng

Bài hỏi cặp / cluster / interval / “k phần tử thoả mãn quan hệ” — nhưng input KHÔNG sorted. Sort trước cho phép two pointers / binary search.

Heuristic

Khi bạn nghĩ tới HashMap/Brute force và thấy O(N²), thử SORT trước. Sort mất $O(N\log N)$ nhưng mở ra:

• Two pointers $O(N)$
• Binary search $O(\log N)$ per query
• Sweep line $O(N)$

Top problems

Bài	LC	Vì sao sort?
3Sum	LC #15	Sort → 3 pointers + skip dup
Meeting Rooms II	LC #253	Sort theo start, sweep theo end
Merge Intervals	LC #56	Sort theo start → merge tuần tự
Non-overlapping Intervals	LC #435	Sort theo end → greedy
Largest Number	LC #179	Sort với custom compare b+a vs a+b
Top K Closest Points	LC #973	Quickselect / sort by distance
Reduce Array Size to Half	LC #1338	Sort freq desc → greedy lấy lớn nhất
Boats to Save People	LC #881	Sort + two pointers
Custom Sort String	LC #791	Sort by custom order
H-Index	LC #274	Sort desc → tìm h

Pitfalls

1. Sort mất O(N log N) — nếu bài cần O(N), sort không phải đáp án.
2. Lost original order: nếu cần index gốc, lưu [value, originalIndex] rồi sort.
3. Stable sort matter: JS Array.sort từ ES2019 stable; cẩn thận với engine cũ.
4. Custom compare overflow: (a, b) => a - b có thể overflow với int64 — JS dùng float64 OK.

→ Nguồn: 06-Sorting-Merge-Quick, 15-Intervals