Dashboard/Coding patterns/11. Greedy Techniques

CODING PATTERNS · LESSON 11 OF 28 · 73 MIN VIDEO · 25 PROBLEMS

Greedy Techniques

Module Progress (0 / 25 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (73 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Greedy Techniques — How the Pattern Works

Greedy algorithms construct a globally optimal solution incrementally by committing to the locally best choice at each step without backtracking. Correctness relies on two properties—greedy-choice safety (verified via an exchange argument showing no alternative decision yields a strictly better downstream state) and optimal substructure. When both hold, greedy techniques collapse exponential O(2^n) or O(n!) searches and O(n^2) dynamic programming tables into O(n) single/dual-pass scans or O(n log n) sort-and-heap passes.

WHEN TO USE THIS PATTERN
  • Optimization prompts requesting a minimum or maximum count, cost, profit, or numerical/lexicographical value where candidates admit a strict ranking (by value, marginal delta a - b, or pairwise concatenation order).
  • Reachability or minimum-jump interval problems where reaching index r automatically makes every earlier index 0..r reachable.
  • Capacity-constrained pairing, assignment, or circular prefix-sum problems where an exchange argument proves matching extremes (lightest with heaviest) or discarding negative-balance prefixes never eliminates an optimal solution.
  • Deferred-selection or sequence-minimization problems where past options can be buffered in a max-heap or monotonic stack and committed/evicted only when fuel runs short or an inversion appears.
  • Directional boundary or two-neighbor inequality problems where right-hand limits constrain left-hand splits (right-to-left scan) or independent left and right passes resolve bidirectional constraints.
COMMON INTERVIEW PITFALLS
  • Assuming greedy works without proving the exchange property: on non-canonical coin systems like [6, 5, 1] for target 10, greedy picks 6 + 1 + 1 + 1 + 1 (5 coins) instead of the optimal 5 + 5 (2 coins), which requires dynamic programming.
  • Sorting by raw value instead of marginal difference or custom pairwise order: Two City Scheduling must sort by costA - costB rather than costA, and Largest Number must compare b + a vs a + b rather than numeric value.
  • Breaking ties on the wrong side or forgetting leading-zero normalization: Maximum Swap must swap with the rightmost occurrence of the largest suffix digit (1993 -> 9913, not 9193), while Largest Number, Largest Palindromic Number, and Remove K Digits must collapse leading zeros ('00' -> '0').
  • Scanning in the wrong direction when constraints propagate asymmetrically: upper-bounded array splitting (Minimum Replacements) requires a right-to-left scan, whereas bidirectional neighbor rules (Candy) require both a left-to-right pass and a right-to-left pass combined with max.
Running Frontier / Reach Expansion ScanTrack maximum reachable index, implicit BFS jump layers, or running extremum in a single O(n) pass.
def greedy_reach_scan(nums):
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True
Sort + Two-Pointer Extremes PairingPair elements under a capacity limit so the most restrictive item is always matched with the easiest partner first.
def sort_and_pair(items, limit):
    items.sort()
    left, right = 0, len(items) - 1
    groups = 0
    while left <= right:
        if items[left] + items[right] <= limit:
            left += 1
        right -= 1
        groups += 1
    return groups
Deferred Greedy Selection with a Max-HeapPass available resources and retroactively claim the largest reward in O(log n) time only when current capacity falls short.
import heapq
def deferred_greedy(target, fuel, stations):
    reach, i, stops, passed = fuel, 0, 0, []
    while reach < target:
        while i < len(stations) and stations[i][0] <= reach:
            heapq.heappush(passed, -stations[i][1])
            i += 1
        if not passed:
            return -1
        reach -= heapq.heappop(passed)
        stops += 1
    return stops
Lexicographical Minimization with a Monotonic StackDelete up to k inversions left-to-right to produce the smallest possible numerical or lexicographical sequence.
def remove_k_inversions(seq, k):
    stack = []
    for ch in seq:
        while k > 0 and stack and stack[-1] > ch:
            stack.pop()
            k -= 1
        stack.append(ch)
    return stack[:-k] if k else stack
🔒 PRO PROBLEMTarget: O(n) time · O(1) space

11. Can Place Flowers

Pattern Trigger: spacing rule, fit the most → take the first spot

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

The coins are six, five and one, and we want ten cents. How many coins does the greedy rule use?