Greedy

Overview

A greedy algorithm makes the locally-optimal choice at each step, betting that local optima accumulate to a global optimum. Greedy is fast (usually O(n) or O(n log n)) but hard to justify: the subtle work is proving that the greedy choice doesn’t paint you into a corner.

Two classic proof structures:

Exchange argument, show that any optimal solution can be rewritten to use the greedy choice without worsening its value.
Monotone invariant, show that a scalar (running max reach, sum, remaining count) strictly dominates the future.

Problems

53. Maximum Subarray (Medium)
55. Jump Game (Medium)
45. Jump Game II (Medium)
134. Gas Station (Medium)
846. Hand of Straights (Medium)
1899. Merge Triplets to Form Target Triplet (Medium)
763. Partition Labels (Medium)
678. Valid Parenthesis String (Medium)

Key patterns unlocked here

Kadane’s algorithm, Maximum Subarray.
Running max reach, Jump Game.
BFS-like level expansion, Jump Game II.
Negative-prefix skip, Gas Station.
Sorted frequencies + rolling consumption, Hand of Straights.
Channel-wise feasibility check, Merge Triplets.
Last-seen index sliding, Partition Labels.
Range tracking of possible ( counts, Valid Parenthesis String.