Greedy Algorithms

Sample Problem

You are given two integer arrays:

• greeds, where greeds[i] represents the minimum size of a cookie that a child needs to to be satisfied.
• cookies, where cookies[j] represents the size of a cookie.

Assign cookies such that as many children as possible are satisfied. Each child can receive at most one cookie, and each cookie can be given to only one child.

A Greedy Algorithm

def num_satisfied_children(greeds: List[int], cookies: List[int]) -> int:
  greeds.sort()
  cookies.sort()

  count = 0
  g_idx, c_idx = 0, 0
  while g_idx < len(greeds) and c_idx < len(cookies):
    if cookies[c_idx] >= greeds[g_idx]:
      count += 1
      g_idx += 1

    c_idx += 1

  return count

When to Go Greedy

Greedy algorithms are correct when 3 properties hold.

Greedy Choice Property

By repeatedly making a locally optimal (greedy) choice, we can arrive at a globally optimal solution.

In num_satisfied_children, the greedy choice is to give each child the smallest cookie that will satisfy them. After iterating through the children, we’ll have maximized the number of satisfied children (globally optimal solution).

Consider the longest subsequence problem, e.g., \([10, 13, 2, 5, 3, 7, 101, 18] \rightarrow [2, 3, 7, 101]\). The greedy choice does not apply here, e.g., choosing \(10\) makes us choose \(13\), and then ignore \(2\). The greedy choice affects our ability to choose the optimal subsequence later on.

Optimal Substructure

The optimal solution to the problem can be constructed from the optimal solutions to its subproblems.

In num_satisfied_children, once we’ve assigned a cookie, then the problem reduces to assigning the remaining cookies to the remaining children.

No Backtracking

Make a decision once and do not revisit it. In num_satisfied_children, we don’t take back the cookie and give it to another child, nor do we give the child a different cookie.

References

1. Greedy Algorithms Overview | Hello Interview. www.hellointerview.com . Accessed Jun 6, 2026.