leetExpert

Module 14 · Sorting

Practice

Practice~1 min

How to practice this module

Sorting drills reward knowing what order buys you: sort once, then scan, merge, or compare. Sort-an-array proves you can implement the workhorse; merge-intervals and meeting-rooms show sort-then-sweep; largest-number and kth-largest need custom ordering and partitioning. Done when all five show Solved in the hub.

Problems

Sorting — work them in order; difficulty ascends.

0/5

solved

  1. 1Sort an ArrayMediumComparison sort (merge / quicksort)Watch for: In-place quicksort needs the partition right; merge sort needs the temp array — worst case O(n log n), never accidental O(n^2)
  2. 2Merge IntervalsMediumSort by start, then mergeWatch for: Sort by start; extend current.end while the next.start <= current.end, else push the interval and move on
  3. 3Largest NumberMediumCustom comparatorWatch for: Compare concatenations a+b vs b+a, not numeric value; strip leading zeroes from the final result
  4. 4Meeting Rooms IIMediumSweep with heap / eventsWatch for: Sort by start and free a room by earliest end; or sweep +1/-1 events and track the peak
  5. 5Kth Largest Element in an ArrayMediumQuickselect / size-k min-heapWatch for: After partitioning, recurse into only the side holding the target index — that is what makes quickselect near-linear

Cheatsheet

Sorting — Order enables linear scans — know when to sort first.

Smell → pattern

  • Order doesn’t matter, then scanSort + two pointers
  • Custom rank / interval orderSort by key
  • Count small alphabetCounting sort

Patterns

Sort then sweep

Core

Smell: Need adjacent compares or two pointers

Once sorted, adjacent comparisons and two pointers become legal. State the O(n log n) sort cost up front.

pivot

Key-based ordering

Safe

Smell: Greedy / merge depends on start or end

Sort by start, by end, or by a derived key. Wrong key ⇒ wrong greedy or merge.

pivot

Counting / bucket

Reach

Smell: Values live in a tiny range

When values sit in a tiny range, count frequencies and rewrite — linear in n + range.

write region

Complexity targets

  • Comparison sort

    Time
    O(n log n)
    Space
    O(n)*
    Note
    *or in-place depending on algo

  • Counting sort

    Time
    O(n + R)
    Space
    O(R)
    Note
    R = value range

Traps

  • Unstable assumptions

    If equal keys must keep input order, confirm your sort’s stability or decorate with original indices.

  • Sorting destroys index answers

    If the output needs original indices, sort pairs (value, index) — sorting values alone loses the mapping.