pattern heroPT–23LeetCode Extension

Greedy

At each step take what is best right now and never go back on it. It is far faster than trying everything, but it works only where the best step now never spoils the best overall answer.

P22 Greedy1×

Example problem: whether you can reach the last index of [1, 3, 1, 0, 2, 0, 0, 3], where each value is the longest jump from that index.

0113213042506073reach
not reachable yetreachablecurrent index ipassedunreachable

Only index 0 is reachable so far

reach = 0i = –
01/26
restart · back · play · step
Speed
1function canJump(nums):
2 reach = 0
3 for i from 0 to len(nums) - 1:
4 if i > reach:
5 break
6 reach = max(reach, i + nums[i])
7 return reach >= len(nums) - 1

← → step · space play/pause

How to recognise

an optimum where one choice at each step always looks safe: jump as far as you can, take the meeting that ends first.

How to solve problems like this

  1. Name the choice you make at each step: the farthest jump, the earliest end, the cheapest option.
  2. Check that it is safe: swapping it for any other choice never gives a better answer. If it can, use dynamic programming instead.
  3. Sort first if the choice depends on order: by end time, by deadline, by size.
  4. Make one pass with a single running value, and stop as soon as the answer is known.

Where it's used

  • Compression. The Huffman code in zip, gzip and PNG is built greedily: the two rarest symbols are glued into one, again and again. Common symbols get short codes, rare ones long codes.
  • Routing. Routers running OSPF find shortest paths with Dijkstra's algorithm: each time they settle the nearest point not yet settled and never revisit it.