CodeMosa

Master LeetCode Patterns

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)

What is Greedy?

#
Definition:

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

Code Templates

#
Sort by the right key and repeatedly take the locally optimal choice (e.g., earliest finish for intervals) justified by an exchange argument.
# Greedy Template (Interval Scheduling)
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

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

Related Patterns

#
BacktrackingFenwick Tree (Binary Indexed Tree)KMP AlgorithmMath & BitsRange QueriesSegment Tree

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