Skip to main content

Assign Cake

This question is asked by Amazon. You are at a birthday party and are asked to distribute cake to your guests. Each guest is only satisfied if the size of the piece of cake they're given matches their appetite (i.e., is greater than or equal to their appetite). Given two arrays, appetite and cake where the ith element of appetite represents the ith guest's appetite, and the elements of cake represents the sizes of cake you have to distribute, return the maximum number of guests that you can satisfy.

Example(s)​

Example 1:

Input: appetite = [1, 2, 3], cake = [1, 2, 3]
Output: 3
Explanation:
- Guest 1 (appetite=1) can get cake[0]=1 → satisfied ✓
- Guest 2 (appetite=2) can get cake[1]=2 → satisfied ✓
- Guest 3 (appetite=3) can get cake[2]=3 → satisfied ✓
All 3 guests can be satisfied.

Example 2:

Input: appetite = [3, 4, 5], cake = [2]
Output: 0
Explanation:
- Guest 1 (appetite=3) needs cake ≥ 3, but cake[0]=2 < 3 ✗
- Guest 2 (appetite=4) needs cake ≥ 4, but cake[0]=2 < 4 ✗
- Guest 3 (appetite=5) needs cake ≥ 5, but cake[0]=2 < 5 ✗
No guests can be satisfied.

Example 3:

Input: appetite = [2, 3, 4], cake = [1, 2, 3, 4, 5]
Output: 3
Explanation:
- Guest 1 (appetite=2) can get cake[1]=2 → satisfied ✓
- Guest 2 (appetite=3) can get cake[2]=3 → satisfied ✓
- Guest 3 (appetite=4) can get cake[3]=4 → satisfied ✓
All 3 guests can be satisfied.

Solution​

The solution uses a greedy approach with sorting:

  1. Sort both arrays: Sort appetites and cake sizes in ascending order
  2. Greedy matching: For each guest (smallest appetite first), assign the smallest cake that satisfies them
  3. Maximize count: This strategy maximizes the number of satisfied guests

JavaScript Solution - Greedy

/**
* Maximum number of guests that can be satisfied
* @param {number[]} appetite - Array of guest appetites
* @param {number[]} cake - Array of cake sizes
* @return {number} - Maximum number of satisfied guests
*/
function assignCake(appetite, cake) {
// Sort both arrays in ascending order
appetite.sort((a, b) => a - b);
cake.sort((a, b) => a - b);

let satisfied = 0;
let cakeIndex = 0;

// For each guest (greedy: start with smallest appetite)
for (let i = 0; i < appetite.length; i++) {
  // Find smallest cake that satisfies this guest
  while (cakeIndex < cake.length && cake[cakeIndex] < appetite[i]) {
    cakeIndex++;
  }
  
  // If we found a cake that satisfies this guest
  if (cakeIndex < cake.length) {
    satisfied++;
    cakeIndex++; // Use this cake, move to next
  }
}

return satisfied;
}

// Test cases
console.log('Example 1:', assignCake([1, 2, 3], [1, 2, 3])); 
// 3

console.log('Example 2:', assignCake([3, 4, 5], [2])); 
// 0

console.log('Example 3:', assignCake([2, 3, 4], [1, 2, 3, 4, 5])); 
// 3

console.log('Test 4:', assignCake([1, 1, 1], [1, 1])); 
// 2
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Using Set/Map)​

Here's an alternative approach using a frequency map:

/**
 * Using frequency map (useful when cake sizes can be reused)
 * Note: This assumes each cake can only be used once
 */
function assignCakeMap(appetite, cake) {
  appetite.sort((a, b) => a - b);
  cake.sort((a, b) => a - b);
  
  const cakeCount = new Map();
  for (const size of cake) {
    cakeCount.set(size, (cakeCount.get(size) || 0) + 1);
  }
  
  let satisfied = 0;
  
  for (const app of appetite) {
    // Find smallest available cake that satisfies
    for (const [size, count] of Array.from(cakeCount.entries()).sort((a, b) => a[0] - b[0])) {
      if (size >= app && count > 0) {
        satisfied++;
        cakeCount.set(size, count - 1);
        if (cakeCount.get(size) === 0) {
          cakeCount.delete(size);
        }
        break;
      }
    }
  }
  
  return satisfied;
}

Complexity​

  • Time Complexity: O(n log n + m log m) - Where n is the number of guests and m is the number of cake pieces. We sort both arrays, then do a linear pass.
  • Space Complexity: O(1) - Only using a constant amount of extra space (not counting the input arrays).

Approach​

The solution uses a greedy algorithm with sorting:

  1. Sort both arrays:

    • Sort appetites in ascending order
    • Sort cake sizes in ascending order

  2. Greedy matching:

    • Process guests in order of increasing appetite
    • For each guest, assign the smallest cake that satisfies them
    • This leaves larger cakes for guests with larger appetites

  3. Why it works:

    • If we can satisfy a guest with a small cake, we should
    • This leaves larger cakes available for guests who need them
    • Maximizes the total number of satisfied guests

Key Insights​

  • Greedy approach: Always assign smallest satisfying cake to current guest
  • Sort first: Makes it easy to find the smallest satisfying cake
  • Process in order: Start with guests who have smallest appetites
  • Two pointers: Use indices to track position in sorted arrays
  • Maximizes count: This strategy is optimal

Step-by-Step Example​

Let's trace through Example 1: appetite = [1, 2, 3], cake = [1, 2, 3]

After sorting:
  appetite = [1, 2, 3]
  cake = [1, 2, 3]

Process guests:
  Guest 1 (appetite=1):
    Find smallest cake ≥ 1: cake[0]=1
    Assign cake[0] to guest 1
    satisfied = 1
    cakeIndex = 1
  
  Guest 2 (appetite=2):
    Find smallest cake ≥ 2: cake[1]=2
    Assign cake[1] to guest 2
    satisfied = 2
    cakeIndex = 2
  
  Guest 3 (appetite=3):
    Find smallest cake ≥ 3: cake[2]=3
    Assign cake[2] to guest 3
    satisfied = 3
    cakeIndex = 3

Result: 3 satisfied guests

Visual Representation​

Example 1: appetite = [1, 2, 3], cake = [1, 2, 3]

Sorted:
  Guests:  [1]  [2]  [3]
  Cakes:   [1]  [2]  [3]
            ↓    ↓    ↓
          Match Match Match
          
Result: 3 satisfied

Example 2: appetite = [3, 4, 5], cake = [2]

Sorted:
  Guests:  [3]  [4]  [5]
  Cakes:   [2]
            ↓
          Too small for all guests
          
Result: 0 satisfied

Example 3: appetite = [2, 3, 4], cake = [1, 2, 3, 4, 5]

Sorted:
  Guests:  [2]  [3]  [4]
  Cakes:   [1]  [2]  [3]  [4]  [5]
            ✗    ↓    ↓    ↓
          Skip  Match Match Match
          
Result: 3 satisfied

Edge Cases​

  • No cake: Return 0
  • No guests: Return 0
  • All cakes too small: Return 0
  • More cakes than guests: Return number of satisfied guests
  • More guests than cakes: Return number of satisfied guests
  • Duplicate appetites: Works correctly
  • Duplicate cake sizes: Works correctly

Important Notes​

  • Greedy is optimal: This greedy approach gives the maximum number
  • Sort both arrays: Essential for the greedy strategy
  • Smallest satisfying cake: Always assign the smallest cake that works
  • Two pointers: Efficiently track position in sorted arrays
  • O(n log n) time: Dominated by sorting

Why Greedy Works​

Proof sketch:

  • If we can satisfy a guest with appetite A using cake size C, we should
  • Using a larger cake for this guest would waste it
  • The greedy choice (smallest satisfying cake) leaves more options for future guests
  • This maximizes the total number of satisfied guests
  • Assign Cookies: Similar problem (LeetCode 455)
  • Meeting Rooms: Different greedy problem
  • Non-overlapping Intervals: Different greedy problem
  • Two Sum: Different problem

Takeaways​

  • Greedy algorithm maximizes the number of satisfied guests
  • Sort both arrays to enable greedy matching
  • Smallest satisfying cake should be assigned first
  • O(n log n) time dominated by sorting
  • O(1) extra space for the algorithm