IntermediateAdvanced Patterns

Greedy

Prove a local choice leads to a global optimum; classic interval scheduling, exchange arguments, and Huffman coding

Time: O(n log n) typical
Space: O(1)–O(n)
Pattern Overview

Core Idea

Identify an invariant or exchange argument that justifies always picking the best local option.

When to Use

Use when feasible solutions exist and a simple rule repeatedly improves or completes the solution.

General Recognition Cues
General indicators that this pattern might be applicable
  • Always pick best local
  • Intervals
  • Proof by exchange
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Interval Scheduling

Sort by end time and pick non-overlapping

When to Use This Variant
  • Earliest finish
Use Case
Max set of intervals
Advantages
  • Optimal
  • Linear after sort
Implementation
def interval_scheduling(intervals):
    intervals.sort(key=lambda x: x[1])
    res=[]; end=-10**18
    for s,e in intervals:
        if s>=end: res.append([s,e]); end=e
    return res
2

Exchange Arguments

Swap to show optimality

When to Use This Variant
  • Swappable structure
Use Case
Various scheduling
Advantages
  • General proof tool
Implementation
# Exchange arguments are proof techniques; example: minimize sum of weighted completion times by sorting by ratio
def schedule_by_ratio(jobs):
    # jobs: (weight, length)
    jobs.sort(key=lambda x: x[0]/x[1], reverse=True)
    return jobs
3

Huffman Coding

Greedy merging by frequency

When to Use This Variant
  • Prefix codes
Use Case
Compression
Advantages
  • Optimal prefix codes
Implementation
import heapq
def huffman_cost(freqs):
    heap=list(freqs); heapq.heapify(heap); cost=0
    while len(heap)>1:
        a=heapq.heappop(heap); b=heapq.heappop(heap); cost+=a+b; heapq.heappush(heap, a+b)
    return cost
Common Pitfalls
Watch out for these common mistakes
  • Unproven greedy choice
  • Wrong sort key
  • Edge-case tie-breaking
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n log n) typical

Sorting + linear selection.

Space Complexity
O(1)–O(n)

Depends on data structures.

Ready to test your knowledge?

Test your pattern recognition with interactive questions