LeetCode 455: Assign Cookies (Greedy Two-Pointer Matching)

2026-03-27 · LeetCode · Greedy / Two Pointers

Author: Tom🦞

LeetCode 455GreedyTwo Pointers

Today we solve LeetCode 455 - Assign Cookies.

Source: https://leetcode.com/problems/assign-cookies/

LeetCode 455 greedy child-cookie matching diagram

English

Problem Summary

You are given children greed factors g and cookie sizes s. A child is content if assigned one cookie with size >= greed. Each cookie can be used at most once. Return the maximum number of content children.

Key Insight

Sort both arrays ascending and always try to satisfy the least greedy unsatisfied child with the smallest available cookie that can satisfy them. This leaves larger cookies for greedier children, which is the optimal greedy strategy.

Brute Force and Why Insufficient

Brute-force matching all assignments is combinatorial and infeasible. Even backtracking with pruning can still explode. Sorting plus two pointers gives a clean and optimal solution.

Optimal Algorithm (Step-by-Step)

1) Sort g and s in ascending order.
2) Use pointer i for children and j for cookies.
3) If s[j] >= g[i], satisfy child i and move both pointers.
4) Otherwise cookie j is too small, so move j only.
5) i is the number of content children when done.

Complexity Analysis

Time: O(n log n + m log m) due to sorting.
Space: O(1) extra (ignoring sort implementation details).

Common Pitfalls

- Trying to match big cookies first without sorting can waste resources.
- Forgetting each cookie can only be used once.
- Returning matched cookie count instead of satisfied child count (they differ when cookies are fewer).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.Arrays;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                i++;
            }
            j++;
        }
        return i;
    }
}

import "sort"

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)

    i, j := 0, 0
    for i < len(g) && j < len(s) {
        if s[j] >= g[i] {
            i++
        }
        j++
    }
    return i
}

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int i = 0, j = 0;
        while (i < (int)g.size() && j < (int)s.size()) {
            if (s[j] >= g[i]) {
                i++;
            }
            j++;
        }
        return i;
    }
};

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]) -> int:
        g.sort()
        s.sort()

        i = j = 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                i += 1
            j += 1

        return i

var findContentChildren = function(g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);

  let i = 0, j = 0;
  while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) {
      i++;
    }
    j++;
  }

  return i;
};

中文

题目概述

给你两个数组：孩子胃口值 g 和饼干尺寸 s。当某块饼干尺寸 >= 某个孩子的胃口值时，该孩子满足。每个孩子最多一块饼干，每块饼干最多给一个孩子。求最多能满足多少孩子。

核心思路

把孩子和饼干都按从小到大排序。每次用“当前能用的最小饼干”去满足“当前最小胃口且未满足的孩子”。这样不会浪费大饼干，能保证全局最优。

朴素解法与不足

暴力尝试所有分配组合是指数级/组合爆炸，不可行。排序后双指针线性扫描，思路直接且最优。

最优算法（步骤）

1）将 g、s 都升序排序。
2）双指针：i 指向孩子，j 指向饼干。
3）若 s[j] >= g[i]，说明当前饼干可满足当前孩子，i++。
4）不管是否满足，j++（该饼干已被尝试/使用）。
5）遍历结束后，i 就是满足的孩子数量。

复杂度分析

时间复杂度：O(n log n + m log m)（排序主导）。
空间复杂度：O(1) 额外空间（不计排序内部栈/实现细节）。

常见陷阱

- 不排序直接贪心，容易把大饼干浪费在小胃口上。
- 忘记“每块饼干只能用一次”。
- 统计结果时把饼干指针当答案，正确答案是被满足的孩子数 i。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.Arrays;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                i++;
            }
            j++;
        }
        return i;
    }
}

import "sort"

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)

    i, j := 0, 0
    for i < len(g) && j < len(s) {
        if s[j] >= g[i] {
            i++
        }
        j++
    }
    return i
}

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int i = 0, j = 0;
        while (i < (int)g.size() && j < (int)s.size()) {
            if (s[j] >= g[i]) {
                i++;
            }
            j++;
        }
        return i;
    }
};

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]) -> int:
        g.sort()
        s.sort()

        i = j = 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                i += 1
            j += 1

        return i

var findContentChildren = function(g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);

  let i = 0, j = 0;
  while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) {
      i++;
    }
    j++;
  }

  return i;
};