Assign Cookies

▶

Steps

setup

Sort greed array g

Sort the greed array g to arrange children by increasing greed factor.

💡 Sorting ensures we assign the smallest cookies to the least greedy children first, which is optimal.

Line:

g.sort()

💡 Sorting prepares the data for greedy assignment from smallest greed upwards.

setup

Sort cookie array s

Sort the cookie array s to arrange cookies by increasing size.

💡 Sorting cookies allows us to assign the smallest cookie that satisfies a child's greed first.

Line:

s.sort()

💡 Sorting cookies prepares for efficient greedy matching.

setup

Initialize pointers and count

Initialize pointers i and j to 0, and count to 0. i points to current child, j to current cookie.

💡 Starting pointers at zero means we begin with the least greedy child and smallest cookie.

Line:

i = j = count = 0

💡 Pointers and count track progress through arrays and assignments.

compare

Compare s[j] and g[i]

Compare cookie size s[j]=1 with child's greed g[i]=1 to check if cookie can satisfy child.

💡 This comparison decides if the current cookie can content the current child.

Line:

if s[j] >= g[i]:

💡 Cookie size meets child's greed, so assignment is possible.

insert

Assign cookie to child and increment pointers and count

Since cookie size satisfies child's greed, increment count and move both pointers forward.

💡 Assigning cookie means one more child is contented; move to next child and cookie.

Line:

count += 1
i += 1
j += 1

💡 Matching cookie to child increases content count and advances pointers.

compare

Compare s[j] and g[i] again

Compare cookie size s[j]=1 with child's greed g[i]=2 to check if cookie can satisfy child.

💡 Check if the next cookie can satisfy the next child.

Line:

if s[j] >= g[i]:

💡 Cookie too small to satisfy child's greed.

move_right

Cookie too small, move cookie pointer j

Since cookie size is less than child's greed, move cookie pointer j to try next cookie.

💡 Skipping cookie that cannot satisfy current child to find a bigger cookie.

Line:

else:
    j += 1

💡 Moving cookie pointer tries next cookie without advancing child pointer.

prune

Check while loop condition

Check if pointers i and j are within array bounds and count less than number of children to continue.

💡 Loop continues only if there are children and cookies left and not all children are contented.

Line:

while i < len(g) and j < len(s) and count < len(g):

💡 No more cookies to assign, so algorithm stops.

reconstruct

Prepare to return final count

Prepare to return the count of content children after loop ends.

💡 The count now holds the total number of children contented by cookies.

Line:

return count

💡 Final count is ready to be returned as the answer.

reconstruct

Return final count

Return the count of content children, which is 1.

💡 The count represents how many children have been assigned cookies successfully.

Line:

return count

💡 Final answer is the number of children contented by cookies.

def findContentChildren(g, s):
    g.sort()  # STEP 1
    s.sort()  # STEP 2
    i = j = count = 0  # STEP 3
    while i < len(g) and j < len(s) and count < len(g):  # STEP 8 checks loop condition
        if s[j] >= g[i]:  # STEP 4 compare
            count += 1  # STEP 5 increment count
            i += 1  # STEP 5 move child pointer
            j += 1  # STEP 5 move cookie pointer
        else:
            j += 1  # STEP 7 move cookie pointer when cookie too small
    return count  # STEP 9 return final count

if __name__ == '__main__':
    g = [1,2,3]
    s = [1,1]
    print(findContentChildren(g, s))  # Output: 1

📊

Assign Cookies - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how the greedy approach efficiently matches cookies to children without wasting resources.

none

1

0

2

1

3

2

Result: 0

none

1

0

1

1

Result: 0

none

j

1

0

2

1

3

2

1

3

1

4

Result: 0

compare

j

1

0

2

1

3

2

1

3

1

4

Result: 0

move_right

1

0

j

2

1

3

2

1

3

1

4

Result: 1

compare

1

0

j

2

1

3

2

1

3

1

4

Result: 1

move_right

1

0

i

2

1

j

3

2

1

3

1

4

Result: 1

prune

1

0

i

2

1

j

3

2

1

3

1

4

Result: 1

none

1

0

i

2

1

j

3

2

1

3

1

4

Result: 1

none

1

0

i

2

1

j

3

2

1

3

1

4

Result: 1

Key Takeaways

✓ Sorting both greed and cookie arrays is essential for the greedy approach to work optimally.

Without sorting, the algorithm cannot efficiently assign the smallest sufficient cookie to each child.

✓ The two-pointer technique allows simultaneous traversal of children and cookies, making the assignment process efficient.

Seeing pointers move step-by-step clarifies how the algorithm avoids unnecessary checks.

✓ When a cookie is too small for a child, only the cookie pointer moves forward, showing the algorithm skips unusable cookies without advancing children.

This decision prevents wasting cookies and ensures children are only assigned suitable cookies.

Practice

1. You are given an array representing daily stock prices. You want to maximize profit by making as many buy-sell transactions as you like, but you must sell before you buy again. Which algorithmic approach guarantees the optimal total profit?

easy

A. Greedy approach summing all positive price differences between consecutive days

B. Dynamic Programming with memoization to explore all buy-sell pairs

C. Single pass to find the maximum single buy-sell pair profit

D. Divide and conquer to split the array and combine profits

Solution

1. Step 1: Understand the problem constraints

   The problem allows unlimited transactions but requires selling before buying again, so multiple buy-sell pairs can be combined.

2. Step 2: Identify the approach that captures all profitable segments

   Summing all positive consecutive day price differences captures every profitable transaction, ensuring maximum total profit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Summing positive differences matches the optimal profit for all test cases [OK]

Hint: Sum all positive consecutive price differences [OK]

Common Mistakes:

• Trying to find only one best buy-sell pair
• Using complex DP when greedy suffices
• Ignoring multiple transactions allowed

2. Consider the following code snippet implementing the peak-valley approach to maximize stock profit. What is the final returned profit when the input prices are [1, 2, 3]?

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] >= prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] <= prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

easy

A. 2

B. 0

C. 3

D. 1

Solution

1. Step 1: Trace first while loop to find valley

   i=0, prices[0]=1, prices[1]=2, 1 < 2 so inner loop skips, valley=1

2. Step 2: Trace second while loop to find peak

   i increments while prices[i] <= prices[i+1]: i=0 to 1 (2 <= 3), i=1 to 2 (3 no next), peak=3

3. Step 3: Calculate profit and return

   profit += 3 - 1 = 2, loop ends, return 2

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Profit matches sum of positive differences (2) [OK]

Hint: Sum of (3-1) = 2 profit [OK]

Common Mistakes:

• Off-by-one error missing last peak
• Confusing valley and peak assignments
• Returning zero if no decreasing sequence found

3. Given the following code and input, what is the final output printed?

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

boxTypes = [[1,3],[2,2],[3,1]]
truckSize = 4
print(maximumUnits(boxTypes, truckSize))

easy

A. 7

B. 8

C. 9

D. 6

Solution

1. Step 1: Sort boxTypes by units descending

   Sorted list: [[1,3],[2,2],[3,1]] (already sorted)

2. Step 2: Iterate and pick boxes until truckSize=0

   Take 1 box with 3 units -> totalUnits=3, truckSize=3 left; take 2 boxes with 2 units -> totalUnits=3+4=7, truckSize=1 left; take 1 box with 1 unit -> totalUnits=7+1=8, truckSize=0 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by units descending and pick greedily [OK]

Common Mistakes:

• Off-by-one in take calculation
• Not stopping when truckSize=0
• Incorrect sorting order

4. You are given a positive integer n. The task is to find the largest integer less than or equal to n such that its digits are in non-decreasing order from left to right. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Divide and conquer splitting the number into halves and solving recursively

B. Dynamic Programming that tries all digit combinations to build the largest monotone number

C. Brute force decrementing from n downwards checking monotonicity for each number

D. Greedy algorithm scanning digits from right to left, adjusting digits and setting trailing digits to 9

Solution

1. Step 1: Understand the problem constraints

   The problem requires the largest number ≤ n with digits in non-decreasing order, which suggests a digit-wise adjustment rather than enumerating all numbers.

2. Step 2: Identify the approach that efficiently fixes digits from right to left

   The greedy right-to-left scan decreases digits when a violation is found and sets subsequent digits to 9, ensuring the largest monotone number ≤ n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy right-to-left fix is optimal and efficient [OK]

Hint: Greedy right-to-left digit fix ensures optimal monotone number [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Assuming DP is needed for digit monotonicity
• Believing divide and conquer applies here

5. Identify the bug in the following code snippet for the Maximum Units on a Truck problem:

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1])  # Sort ascending instead of descending
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

medium

A. Line 2: Sorting boxTypes in ascending order instead of descending

B. Line 5: Missing check for truckSize == 0

C. Line 7: Incorrect calculation of take using min(boxes, truckSize)

D. Line 8: Incorrect update of totalUnits by multiplying take and units

Solution

1. Step 1: Examine sorting order

   Sorting ascending by units per box causes picking boxes with lowest units first, leading to suboptimal total units.

2. Step 2: Verify other lines

   Check for early stopping (line 5) is correct; min calculation and totalUnits update are correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order is critical for greedy correctness [OK]

Hint: Sort descending by units per box to maximize units [OK]

Common Mistakes:

• Sorting ascending instead of descending
• Forgetting to break when truckSize=0
• Off-by-one in min calculation