PATTERN 6: Sorting & Ordering Logic
D
Qubits of DPK
April 11, 2026
Core DSA
Core Idea (lock this)
“Impose an order so the problem becomes simpler or deterministic.”
Sorting is not the solution —
sorting is the setup.
How to Recognize This Pattern
Think Sorting & Ordering when:
- Relative order matters
- You see intervals, overlaps, scheduling
- Greedy decisions are unclear before ordering
- Comparisons decide correctness
If brute force tries all permutations →
If sorted order removes ambiguity →
30 MUST-DO INTERVIEW PROBLEMS
(10 Easy → 10 Medium → 10 Hard)
EASY (1–10): Sorting as a Tool
Goal: get comfortable using sorting without overusing it.
- #Sort Colors – LC 75
- #Kth Largest Element in an Array – LC 215
- #Largest Number – LC 179
- #Minimum Difference Between Highest and Lowest of K Scores – LC 1984
- #Sort the People – LC 2418
- #Sort Array by Increasing Frequency – LC 1636
- #Sort Characters By Frequency – LC 451
- #Height Checker – LC 1051
- #Relative Sort Array – LC 1122
- #Sort Integers by The Number of 1 Bits – LC 1356
After these:
You should instinctively ask, "What if I sort first?"
️ MEDIUM (11–20): Sorting + Logic
English explanation first.
- #Merge Intervals – LC 56
- #Non-overlapping Intervals – LC 435
- #Minimum Number of Arrows to Burst Balloons – LC 452
- #Queue Reconstruction by Height – LC 406
- #Maximum Units on a Truck – LC 1710
- #K Closest Points to Origin – LC 973
- #Campus Bikes – LC 1057
- #Largest Perimeter Triangle – LC 976
- #Two City Scheduling – LC 1029
- #Destroying Asteroids – LC 2126
Interview signal:
Can you explain
HARD (21–30): Ordering Enables Greedy
These test decision-making depth.
- #Russian Doll Envelopes – LC 354
- #Maximum Profit in Job Scheduling – LC 1235
- #Count of Smaller Numbers After Self – LC 315
- #Split Array Into Consecutive Subsequences – LC 659
- #Divide Array Into Minimum Number of Groups – LC 2406
- #Create Maximum Number – LC 321
- #Minimum Initial Energy to Finish Tasks – LC 1665
- #Wiggle Sort II – LC 324
- #Minimum Possible Integer After at Most K Adjacent Swaps – LC 1505
- #The Skyline Problem – LC 218
These problems become:
- Impossible without sorting
- Trivial with correct order
Interviewer’s Hidden Check
They are asking:
“Does this candidate know
Say this explicitly in interviews:
“I’ll sort first to simplify decisions.”
Common Mistakes
- Sorting when O(N) solution exists
- Not justifying comparator
- Forgetting stability issues
- Mixing greedy without proof
INTERVIEW REVISION CARD — Pattern 6
1️⃣ Pattern in One Line
"Impose an order first — sorting is the setup, not the solution."
2️⃣ Recognize It When...
- Relative order determines correctness
- Intervals, scheduling, overlap problems
- Greedy decisions are unclear before ordering
- Trigger words: "merge intervals", "overlap", "schedule", "arrange", "closest"
3️⃣ Don't Confuse With...
- Greedy (P9) → greedy makes local choices; sorting just enables those choices
- Binary Search (P7) → BS searches sorted input; P6 creates sorted order
- Heap (P12) → heap gives dynamic order; sorting gives static order
4️⃣ Approach in 3 Steps
- #Identify what to sort by — and justify WHY that order works
- #Apply greedy/logic on sorted input
- #Handle ties in sort comparator carefully
5️⃣ Invariant to Maintain
"After sorting, each decision only depends on elements already processed — no backtracking needed."
6️⃣ Complexity to Justify
- Sort: O(N log N)
- Processing: O(N)
- Total: O(N log N) — dominated by sort
- Why: Sorting eliminates ambiguity in decision making
7️⃣ Edge Cases to Always Check
- Single element array
- All elements same
- Already sorted input
- Reverse sorted input
- Ties in comparator — stability matters
8️⃣ One Line to Say in Interview
"I'll sort by [criterion] first — this makes each subsequent decision locally unambiguous, giving O(N log N) overall."