Sorting Practice Problems

How to Use This Problem List

Sorting problems in interviews divide cleanly into two categories: problems where sorting is the entire solution, and problems where sorting is the first step that unlocks a faster technique (two-pointer, binary search, greedy scan). Recognising which category a problem belongs to is the key skill.

The second insight: many problems that look different on the surface — merge intervals, meeting rooms, task scheduling — all have "sort first, then linear scan" as their core pattern.

Practice one pattern at a time. After four or five problems from the same pattern, the approach becomes automatic.

Pattern 1: Sort and Scan — Greedy After Sorting

Sort first to establish order, then apply a single linear scan to solve the problem greedily. Sorting converts a multi-dimensional overlap/scheduling/grouping problem into a one-dimensional sequence problem.

Complexity target: O(n log n) for sort + O(n) scan = O(n log n) total.

Recognition signal: "intervals", "meetings", "overlapping", "scheduling", "arrange groups". The problem involves ranges or events that interact based on their order.

Pattern 2: Custom Comparator Sorting

The sort key or comparison rule is non-trivial — not simply ascending or descending by one field. The problem is solved entirely by defining the right comparison function.

Complexity target: O(n log n) with custom comparator.

Recognition signal: "arrange to maximise/minimise", "sort by custom rule", "group by property", "wiggle", "interleave". The difficulty is defining the comparison, not the sorting itself.

Pattern 3: Sort and Binary Search

Sort the collection once, then answer multiple queries with binary search. The amortised cost is O(n log n + q log n) instead of O(q × n).

Complexity target: O(n log n) sort + O(log n) per query = O(n log n + q log n).

Recognition signal: "sorted array", "find pair/triple/quadruple", "k closest", "repeated queries on the same data". Sort once, query many times.

Pattern 4: QuickSelect and Order Statistics

Finding the k-th smallest/largest element, or the median, without sorting the entire array. QuickSelect achieves O(n) average using the partition step from QuickSort.

Complexity target: O(n) average for QuickSelect, O(n log k) for heap-based.

Recognition signal: "k-th largest/smallest", "k closest", "k most frequent", "find median". The problem asks for a rank or order statistic, not a full sort.

Pattern 5: Counting and Bucket Sort Applications

Problems where the natural domain (small integer range, character frequencies) allows O(n) sorting or grouping without comparison.

Complexity target: O(n + k) where k is the range or number of distinct values.

Recognition signal: "sort with limited values", "character frequencies", "group by property", "anagram", "bucket". The domain is bounded — use counting/bucket sort instead of comparison sort.

Pattern 6: Permutations, Cycles, and Inversion Counting

Problems rooted in permutation theory — minimum swaps, inversion counts, cycle detection in rearrangement problems.

Complexity target: O(n log n) for merge-sort inversion count; O(n) for cycle-based swap count.

Recognition signal: "minimum swaps", "count inversions", "permutation", "cycles in rearrangement". The problem involves rearranging elements and measuring the cost.

Recommended Study Order

Week 1 — Sort and Apply
  Pattern 1 (Greedy): Merge Intervals, Meeting Rooms, Non-overlapping Intervals
  Pattern 2 (Custom): Sort Colors, Largest Number, Sort by Frequency

Week 2 — Selection and Search
  Pattern 3 (Binary Search): Two Sum II, 3Sum, H-Index
  Pattern 4 (QuickSelect): Kth Largest Element, Top K Frequent Elements

Week 3 — Advanced Sorting Techniques
  Pattern 5 (Counting): Group Anagrams, Maximum Gap, Top K Frequent Words
  Pattern 6 (Permutations): Count Inversions, Minimum Swaps, Next Permutation

Week 4 — Hard Problems and Mixed Patterns
  Pattern 1 (Hard): Task Scheduler, Car Fleet
  Pattern 4 (Hard): Wiggle Sort II, Find Median from Data Stream
  Pattern 6 (Hard): Couples Holding Hands
  Revisit any pattern that felt unclear

Problem-Solving Checklist for Sorting Problems

Before writing code, answer these questions:

1. Is sorting the solution or the first step?
   → Only sorting needed: Custom Comparator (Pattern 2)
   → Sort then linear scan: Sort and Scan (Pattern 1)
   → Sort then binary search: Sort and Search (Pattern 3)

2. What key (comparator) should elements be sorted by?
   → Natural order (ascending/descending)? → Default sort
   → By a computed property (freq, length, ratio)? → key= or lambda
   → By a pairwise comparison that is not transitive on single values? → custom comparator (e.g. Largest Number)

3. Does the problem have a special domain?
   → Small integer range [0, k]? → Counting Sort
   → Fixed-length integers/strings? → Radix Sort
   → Uniform float distribution? → Bucket Sort
   → Only 3 distinct values? → 3-way partition (Dutch National Flag)

4. Does the problem ask for a rank, not a sorted array?
   → k-th largest/smallest? → QuickSelect (O(n) avg)
   → Dynamic median? → Two heaps (O(log n) per insert)

5. Does stability matter?
   → Equal elements must preserve original order? → Use stable sort
   → Two-pass sort (secondary then primary key)? → Both passes must be stable

6. Edge cases for sorting problems:
   → Empty array or single element → typically trivial, but check
   → All equal elements → 3-way partition O(n); QuickSelect O(n)
   → Already sorted input → insertion sort / TimSort O(n); QuickSort O(n²) with naive pivot
   → Custom comparator that is not a valid strict weak ordering → undefined sort behaviour

Pattern Recognition Quick Reference

Difficulty Progression Reference

Common Interview Topics by Company Focus

Product-based companies (FAANG-tier):

• ›Merge Intervals and Meeting Rooms — canonical sort-and-scan problems
• ›Kth Largest Element — QuickSelect is the expected approach
• ›Find Median from Data Stream — two-heap design
• ›Largest Number — custom comparator
• ›Sort Colors — Dutch National Flag (frequently asked as a warmup)
• ›Count Inversions — merge sort application
• ›Top K Frequent Elements — heap vs QuickSelect discussion

Service-based and on-campus:

• ›Sort Colors, Merge Intervals — fundamental
• ›3Sum, Two Sum II — sort + two-pointer standard
• ›Kth Largest — basic QuickSelect
• ›Group Anagrams — sort each string as key

Startup and mid-size tech:

• ›Task Scheduler — real-world scheduling model
• ›Reorder Log Files — practical multi-criteria sort
• ›Minimum Swaps to Sort — permutation graph application
• ›Next Permutation — permutation theory

Progress Tracking

After solving each problem, record:

1. ›Pattern — which of the 6 patterns does this belong to?
2. ›Sort key — what did you sort by and was a custom comparator needed?
3. ›Step after sorting — linear scan, binary search, QuickSelect, or pure comparison?
4. ›Stability needed — did equal elements need to preserve order?
5. ›Edge case missed — empty input? All equal? Already sorted?
6. ›Time to solve — target 20-25 minutes for medium problems under interview conditions

The decisive signal that pattern recognition is working: when you see "merge overlapping intervals" and immediately think "sort by start time, then linear scan" before reading the constraints — and when you see "k-th largest" and immediately think "QuickSelect, O(n) average, partition into one half" instead of "sort the whole array."