learningto/pass

Greedy Algorithms

IntermediateAlgorithms

Greedy algorithms make the locally optimal choice at each step. Proving a greedy works requires showing the greedy choice property and optimal substructure. Interval problems are the classic greedy domain.

AVG TIME
O(n log n)
SPACE
O(1)
BEST
O(n log n)
WORST
O(n log n)

Key Concepts

  • 1Interval scheduling: sort by end time, always pick earliest-ending compatible interval
  • 2Activity selection: greedy works because delayed choices cannot improve the solution
  • 3Jump game: track the farthest position reachable
  • 4Gas station: if total gas >= total cost, a solution exists (proof by invariant)
  • 5Proof technique: exchange argument - show swapping to greedy choice never worsens result

In Python

Concept to Code- 2 structures for this topic
declare
nums = [1, 2, 3]
common ops
nums.append(x)
O(1)
nums.pop()
O(1)
nums[i]
O(1)
nums.insert(i, x)
O(n)
x in nums
O(n)
nums.sort()
O(n log n)
len(nums)
O(1)
say in interview
"I'll use an array to store the elements"
Python lists ARE dynamic arrays (like ArrayList in Java), NOT linked lists. Access by index is O(1).

Math You Need For This

Interval scheduling: lay all intervals on a timeline. Sort by end time. Greedily pick the one that ends earliest and does not overlap the previous pick. Each selection is one O(1) step after the O(n log n) sort.

Required concepts
Key math ideas
1 / 1

Local vs global optimum

A local optimum is the best choice right now. A global optimum is the best choice for the entire problem. Greedy algorithms always pick the local optimum at each step and hope (or can prove) this leads to the global optimum. Sometimes it works, sometimes it does not.

Visual: A landscape of hills. The global maximum is the tallest peak. A local maximum is any peak where the ground slopes down in all directions - but it might be a small hill with a bigger mountain nearby. Greedy always climbs the steepest nearby slope.

Think of it this way: Hiking to the tallest mountain. If you always walk uphill, you might reach the top of a small hill and get stuck. To find the tallest peak, sometimes you have to go downhill first (which greedy never does).

For algorithms: Knowing when greedy works (interval scheduling, Huffman coding, Dijkstra) vs when it fails (coin change with arbitrary denominations, general knapsack) is the key insight for this category.

Interactive 3D Visualization

Array
Access: O(1)Search: O(n)Space: O(n)
Drag to orbit - Scroll to zoom

Python Implementation

example.py
Loading...
Now try it yourself
1 challenge with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Greedy Algorithms into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Big-O Notation
Greedy Algorithms
Next: Big-O Notation