Assign Cookies

📋

Assign Cookies

Edge cases:

</>

IDE

def findContentChildren(g: list[int], s: list[int]) -> int:public int findContentChildren(int[] g, int[] s)int findContentChildren(vector<int> &g, vector<int> &s)function findContentChildren(g, s)

def findContentChildren(g, s):
    # Write your solution here
    pass

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findContentChildren(vector<int> &g, vector<int> &s) {
    // Write your solution here
    return 0;
}

function findContentChildren(g, s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Not sorting arrays and assigning cookies in input order, missing possible matches.✅ Sort both greed and cookie arrays before assignment.

Wrong: 2Assigning cookies without checking if cookie size >= greed factor (using > instead of >=).✅ Use >= comparison when assigning cookies to children.

Wrong: 3Reusing cookies multiple times (unbounded assignment) instead of one-to-one assignment.✅ Assign each cookie at most once using two pointers or a used array.

Wrong: 4Greedy trap: assigning cookies without sorting, leading to overcounting content children.✅ Sort both arrays and assign cookies starting from smallest greed and cookie.

Wrong: 2Off-by-one error in pointer increments causing skipping last child or cookie.✅ Ensure both pointers increment correctly after assignment and loop conditions are correct.

✓

Test Cases

Handle empty and minimal input cases carefully to avoid crashes.

Consider common greedy pitfalls like reusing cookies or wrong pointer increments.

Optimize your solution to avoid nested loops and use sorting with two pointers.

t1_01basic

Input{"g":[1,2,3],"s":[1,1]}

Expected1

⏱ Performance - must finish in 2000ms

Only one child with greed 1 can be content with a cookie of size 1.

💡 Sort both greed and cookie arrays to assign smallest cookies first.

💡 Use two pointers to assign cookies greedily to children.

💡 Increment child pointer only when a cookie satisfies the child's greed.

Why it failed: Returned count too high or low due to not sorting arrays or incorrect pointer increments. Fix by sorting both arrays and using two pointers to assign cookies.

✓ Correctly assigns cookies to maximize content children.

t1_02basic

Input{"g":[1,2],"s":[1,2,3]}

Expected2

⏱ Performance - must finish in 2000ms

Both children can be content: greed 1 with cookie 1, greed 2 with cookie 2 or 3.

💡 Assign smallest cookie that satisfies each child's greed.

💡 Sorting both arrays helps to efficiently match children and cookies.

💡 Use two pointers to iterate through children and cookies simultaneously.

Why it failed: Incorrect count due to not assigning cookies greedily or skipping suitable cookies. Fix by sorting and using two pointers to assign cookies in order.

✓ Correctly matches all children with suitable cookies.

t2_01edge

Input{"g":[],"s":[1,2,3]}

Expected0

⏱ Performance - must finish in 2000ms

No children to assign cookies to, so result is 0.

💡 Check for empty greed array before processing.

💡 If no children, return 0 immediately.

💡 Avoid index errors by handling empty arrays explicitly.

Why it failed: Code crashes or returns non-zero when greed array is empty. Fix by adding a check for empty greed array and returning 0.

✓ Handles empty greed array correctly.

t2_02edge

Input{"g":[1],"s":[]}

Expected0

⏱ Performance - must finish in 2000ms

No cookies available, so no children can be content.

💡 Check for empty cookie array before processing.

💡 If no cookies, return 0 immediately.

💡 Avoid index errors by handling empty arrays explicitly.

Why it failed: Code crashes or returns non-zero when cookie array is empty. Fix by adding a check for empty cookie array and returning 0.

✓ Handles empty cookie array correctly.

t2_03edge

Input{"g":[5],"s":[5]}

Expected1

⏱ Performance - must finish in 2000ms

Single child and cookie with equal size satisfy the child.

💡 Check equality condition when cookie size equals greed factor.

💡 Sorting is trivial but still necessary for consistency.

💡 Assign cookie if cookie size >= greed factor.

Why it failed: Fails to assign cookie when sizes are equal due to strict inequality. Fix by using >= comparison instead of >.

✓ Correctly assigns cookie when sizes are equal.

t2_04edge

Input{"g":[10,20,30],"s":[1,2,3]}

Expected0

⏱ Performance - must finish in 2000ms

All children have greed larger than any cookie size, so no child can be content.

💡 Check if any cookie can satisfy the smallest greed child.

💡 If no cookie is large enough, result is zero.

💡 Sorting helps to quickly identify if assignment is possible.

Why it failed: Returns non-zero when no cookie satisfies any child's greed. Fix by ensuring cookie size >= greed factor before assignment.

✓ Correctly returns zero when no cookies satisfy any child.

t3_01corner

Input{"g":[1,2,3],"s":[1,1,1]}

Expected1

⏱ Performance - must finish in 2000ms

Only one cookie of size 1 can satisfy the child with greed 1; others cannot be satisfied.

💡 Greedy approach must assign smallest cookie to smallest greed child first.

💡 Avoid assigning large cookies to small greed children prematurely.

💡 Sort arrays and use two pointers to assign cookies correctly.

Why it failed: Greedy trap: assigning cookies without sorting or in wrong order leads to overcount. Fix by sorting both arrays and assigning smallest cookie to smallest greed child first.

✓ Correctly handles greedy trap by sorting and two-pointer assignment.

t3_02corner

Input{"g":[2,2,2],"s":[1,2,3]}

Expected2

⏱ Performance - must finish in 2000ms

Two cookies (2 and 3) can satisfy two children with greed 2; cookie size 1 is too small.

💡 Ensure each cookie is assigned to at most one child.

💡 Do not reuse cookies for multiple children.

💡 Use a boolean or pointer approach to track used cookies.

Why it failed: Confuses 0/1 knapsack with unbounded: reusing cookies multiple times. Fix by assigning each cookie only once using two pointers or used flags.

✓ Correctly enforces one-to-one cookie assignment.

t3_03corner

Input{"g":[1,2,3,4],"s":[1,2,2,3]}

Expected3

⏱ Performance - must finish in 2000ms

Three children can be satisfied with cookies 1, 2, and 3; child with greed 4 cannot be satisfied.

💡 Check off-by-one errors in pointer increments.

💡 Ensure both pointers advance correctly after assignment.

💡 Verify loop termination conditions to avoid skipping children or cookies.

Why it failed: Off-by-one error causes skipping last child or cookie. Fix by carefully incrementing both pointers only when assignment occurs and checking loop conditions.

✓ Correctly handles pointer increments and loop termination.

t4_01performance

Input{"g":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"s":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 children and cookies, O(n log n) sorting and O(n) assignment must complete within 2 seconds.

💡 Sorting both arrays is necessary for efficient assignment.

💡 Use two-pointer technique to assign cookies in O(n) after sorting.

💡 Avoid nested loops to prevent O(n^2) time complexity.

Why it failed: TLE due to nested loops or brute force O(n*m) approach. Fix by sorting and using two pointers for O(n log n) solution.

✓ Efficient O(n log n) solution confirmed by passing performance test.

Practice

1. Given the following code snippet implementing the optimal candy distribution algorithm, what is the final returned value when input ratings = [1, 0, 2]?

easy

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Trace left-to-right pass

   ratings = [1,0,2], candies init = [1,1,1] - i=1: ratings[1]=0 < ratings[0]=1, no change - i=2: ratings[2]=2 > ratings[1]=0, candies[2] = candies[1]+1 = 2 candies after pass: [1,1,2]

2. Step 2: Trace right-to-left pass

   i=1: ratings[1]=0 < ratings[2]=2, no change i=0: ratings[0]=1 > ratings[1]=0 and candies[0]=1 <= candies[1]=1, update candies[0] = candies[1]+1 = 2 candies after pass: [2,1,2] Sum = 2+1+2 = 5

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum matches expected output 5 [OK]

Hint: Sum candies after two passes for final answer [OK]

Common Mistakes:

• Forgetting to update candies in right-to-left pass
• Off-by-one errors in loops
• Misreading comparison operators

2. Consider the following Python function that calculates the minimum number of platforms needed. Given the input arrivals = [900, 940, 950] and departures = [910, 1200, 1120], what is the value of max_platforms after processing the second train (index 1)?

easy

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Sort trains by arrival time

   Sorted trains: [(900, 910), (940, 1200), (950, 1120)]

2. Step 2: Process trains up to index 1

   After first train: heap=[910], max_platforms=1 Second train arrival=940, heap top=910 ≤ 940, pop 910 Push 1200, heap=[1200], max_platforms=max(1,1)=1 Since question asks after second train, max_platforms=1

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap size after second train is 1, max_platforms updated to 1 [OK]

Hint: Heap pops departures ≤ arrival before push [OK]

Common Mistakes:

• Not popping from heap before push
• Confusing max_platforms update timing
• Off-by-one in iteration

3. The following code attempts to compute the minimum cost to connect sticks using a min-heap. Identify the bug that causes incorrect results or infinite loops.

medium

A. Line 3: Incorrect base case check for single stick

B. Line 9: Adding cost before popping sticks

C. Line 6: Not heapifying the sticks before processing

D. Line 11: Not pushing the merged stick back into the heap

Solution

1. Step 1: Review the merge loop

   The loop pops two smallest sticks and sums their lengths as cost.

2. Step 2: Check if merged stick is reinserted

   The merged stick must be pushed back into the heap to continue merging. Missing this causes infinite loop or incorrect cost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without pushing merged stick, heap shrinks incorrectly -> infinite loop or wrong result [OK]

Hint: Merged sticks must be pushed back to heap [OK]

Common Mistakes:

• Forgetting to push merged stick back
• Incorrect base case handling
• Misordering heap operations

4. What is the time complexity of the optimal greedy algorithm that finds the largest monotone increasing digits number less than or equal to n, where d is the number of digits in n?

medium

A. O(d), since it scans digits once from right to left and then sets trailing digits

B. O(log n), since the number of digits d is proportional to log n

C. O(d^2), because each decrement may cause re-checking previous digits multiple times

D. O(n * d), where n is the input number and d is the number of digits

Solution

1. Step 1: Understand the relationship between digits and input size

   The number of digits d in n is proportional to log₁₀ n.

2. Step 2: Express complexity in terms of n

   The algorithm runs in O(d) time, which is O(log n) when expressed in terms of n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Expressing complexity in terms of n, O(log n) is correct and more standard [OK]

Hint: Algorithm runs in linear time relative to digit count, which is logarithmic in n [OK]

Common Mistakes:

• Confusing input size n with digit count d
• Assuming repeated decrements cause quadratic time
• Ignoring that digit count is log n

5. Consider the following buggy code for partitioning labels. Which line contains the subtle bug that can cause incorrect partitions?

def partitionLabels(s):
    last = [0] * 26
    for i, c in enumerate(s):
        last[ord(c) - ord('a')] = i
    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = last[ord(c) - ord('a')]  # Bug here: missing max()
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

medium

A. Line 3: Updating last occurrence map

B. Line 13: Calculating partition size with end - start + 1

C. Line 8: Initializing end to 0

D. Line 11: Updating end without taking max

Solution

1. Step 1: Understand role of end variable

   End must track the furthest last occurrence of any character seen so far to avoid premature partitioning.

2. Step 2: Identify bug in updating end

   Assigning end directly to last occurrence of current character without max() loses track of previous furthest last occurrence, causing incorrect partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing max() causes partitions to cut too early [OK]

Hint: Always update end = max(end, last[c]) [OK]

Common Mistakes:

• Forgetting max() when updating partition end
• Off-by-one errors in partition size calculation
• Not precomputing last occurrences