Greedy Algorithms

Make the locally optimal choice at each step, trusting that this leads to a global optimum — only works when the problem has the greedy-choice property.

When to use it

Activity/interval selection (scheduling non-overlapping tasks).
Minimum spanning tree (Kruskal's, Prim's), Huffman coding.
Problems where sorting and choosing greedily (earliest end time, smallest element) provably works.

Signals in the problem statement

Asked to maximize/minimize something by making a series of choices.
A sorting + greedy scan solution feels natural and can be proven correct.
Keywords: 'minimum coins', 'jump game', 'gas station', 'assign'.

Common pitfalls

Assuming greedy works without proof — many problems seem greedy but actually need DP (e.g. coin change with arbitrary denominations).
Forgetting to sort first when the greedy choice depends on order (e.g. interval scheduling by end time).

Practice Problems

Jump Game

Medium

Asked at: Amazon, Google, Meta

Practiced

Given an array where each element represents your maximum jump length from that position, determine if you can reach the last index.

Time: O(n) · Space: O(1)

Gas Station

Medium

Asked at: Amazon, Meta

Practiced

There are n gas stations in a circle. gas[i] is the gas at station i, cost[i] is the cost to travel from i to i+1. Find the starting station index if you can complete the circuit, or -1 if impossible.

Time: O(n) · Space: O(1)