IntermediateGreedy & Sorting

Sorting + Greedy

Solve problems by sorting with custom orders and making locally optimal choices that lead to a global optimum

Time: O(n log n) typical

Space: O(1)–O(n)

Pattern Overview

Core Idea

Sort data to expose structure, then take greedy steps based on problem-specific criteria (comparators, endpoints, frequencies).

When to Use

Use when ordering unlocks a simple greedy rule (intervals, scheduling, top-k, custom orderings) or when range/keys are small (counting/bucket).

General Recognition Cues

General indicators that this pattern might be applicable

Intervals to merge or schedule
Pick smallest/largest by a rule
Custom comparison or tie-breakers
Small value range (counting/bucket)
Proof by exchange/greedy stays optimal

Pattern Variants & Approaches

Different methodologies and implementations for this pattern

Custom Comparators

Define ordering logic to drive greedy selection or grouping

When to Use This Variant

Sort with tie-breakers
Lexicographic or custom key
Greedy after sorting

Use Case

Task/interval ordering, largest number from array, custom ranking

Advantages

Simple once order is right
Works with standard sorts
Expressive control of ordering

Implementation

from functools import cmp_to_key

def custom_sort_pairs(pairs):
    # Example: sort by first asc, then second desc (custom comparator)
    def cmp(a, b):
        if a[0] != b[0]:
            return -1 if a[0] < b[0] else 1
        # tie-break on second descending
        if a[1] != b[1]:
            return -1 if a[1] > b[1] else 1
        return 0
    pairs.sort(key=cmp_to_key(cmp))
    return pairs

def largest_number(nums):
    # Classic comparator usage example
    arr = list(map(str, nums))
    def cmp(a, b):
        if a + b > b + a: return -1
        if a + b < b + a: return 1
        return 0
    arr.sort(key=cmp_to_key(cmp))
    res = ''.join(arr).lstrip('0')
    return res or '0'

Merge Intervals

Sort by start and combine overlapping intervals

When to Use This Variant

Intervals overlap/merge
Return minimal disjoint set
Timeline consolidation

Use Case

Scheduling, calendar merges, coverage

Advantages

O(n log n) with sort
Single pass merge
Handles chains of overlaps

Implementation

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for s, e in intervals:
        if not merged or s > merged[-1][1]:
            merged.append([s, e])
        else:
            merged[-1][1] = max(merged[-1][1], e)
    return merged

Bucket/Counting Sort

Exploit bounded key range for linear-time grouping and ordering

When to Use This Variant

Small integer key range
Frequencies then rebuild
Near-linear grouping

Use Case

Grades, age buckets, top-k by frequency

Advantages

O(n + k) time
Stable when implemented carefully
Low constant factors

Implementation

def counting_sort(arr, max_val=None):
    if not arr:
        return []
    if max_val is None:
        max_val = max(arr)
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1
    i = 0
    for v, c in enumerate(count):
        for _ in range(c):
            arr[i] = v
            i += 1
    return arr

Common Pitfalls

Watch out for these common mistakes

Incorrect comparator (tie-break rules)
Greedy choice without proof
Forgetting to sort before merging
Overflow when computing keys
Unstable sort when stability needed

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 dominates unless using counting/bucket with small key range.

Space Complexity

O(1)–O(n)

In-place sort often O(1); counting/bucket needs O(k) buckets.

Ready to test your knowledge?

Test your pattern recognition with interactive questions