DSA Tracker

Visualize

Assign Cookies

Greedy smallest-cookie to smallest-greed matching

time O(n log n + m log m)space O(1)

The greedy choice is to satisfy the least demanding child with the smallest cookie that suffices. Giving a large cookie to an easily satisfied child wastes size that could satisfy a greedier child later, while giving a cookie to a child who cannot be satisfied by it wastes the cookie. By sorting both greed factors and cookie sizes, we scan both arrays with two pointers: if the current cookie satisfies the current child, we match them and move both pointers forward; otherwise, this cookie is too small for anyone remaining, so we discard it and try the next larger cookie.

Details

Animated on: g = [1, 2, 3] (greed factors), s = [1, 1] (cookie sizes) — maximize the number of content children.

Problem:Assign CookiesEasy

Greedy smallest-cookie to smallest-greed matching

step 1 / 9

g:1
[0]
g:2
[1]
g:3
[2]
s:1
[3]
s:1
[4]

Sort both arrays. Children g=[1,2,3] at indices 0–2, cookies s=[1,1] at indices 3–4. Start pointers at child=0 (greed 1) and cookie=0 (size 1).

  • child=0· arr[0] = g:1
  • cookie=3· arr[3] = s:1
Pseudocode
1FUNCTION findContentChildren(g, s):
2  sort g ascending, sort s ascending
3  child = 0, cookie = 0
4  WHILE child < length of g and cookie < length of s:
5    IF s[cookie] >= g[child]:
6      move child one step forward
7    move cookie one step forward
8  RETURN child

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Sort both arrays. Children g=[1,2,3] at indices 0–2, cookies s=[1,1] at indices 3–4. Start pointers at child=0 (greed 1) and cookie=0 (size 1).
  2. Compare cookie s[0]=1 with child g[0]=1. Since size 1 >= greed 1, this cookie satisfies child 0 perfectly without wasting excess size.
  3. Child 0 is content! Increment child from 0 to 1 (1 child satisfied so far).
  4. Advance cookie to index 4 (s[1]=1) to look for a match for the next child.
  5. Both pointers are still in bounds: child=1 < 3 and cookie=1 < 2. Check the next cookie.
  6. Compare cookie s[1]=1 with child g[1]=2. Size 1 < greed 2, so cookie 1 cannot satisfy child 1.
  7. Because children are sorted, cookie 1 cannot satisfy any remaining child either. Cookie is exhausted.
  8. Cookie pointer reached s.length (2 cookies used). No cookies left, so the while loop terminates.
  9. Return child = 1. Exactly 1 child (greed 1) received a matching cookie (size 1).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Assign Cookies in the editorAll Greedy problemsBack to roadmap