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. 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

2. Consider the following Python function that returns the largest monotone increasing digits number less than or equal to n. What is the output when n = 332?

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))
    marker = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            digits[i - 1] -= 1
            marker = i
    for i in range(marker, len(digits)):
        digits[i] = 9
    return int(''.join(map(str, digits)))

print(monotoneIncreasingDigits(332))

easy

A. 299

B. 329

C. 2999

D. 322

Solution

1. Step 1: Trace the loop from right to left

   Digits start as [3, 3, 2]. At i=2, digits[2]=2 < digits[1]=3, so digits[1] decrements to 2 and marker=2.

2. Step 2: Set digits from marker to end to 9

   Digits become [3, 2, 9]. Next, at i=1, digits[1]=2 < digits[0]=3, so digits[0] decrements to 2 and marker=1. Then digits from index 1 onward set to 9 -> [2, 9, 9].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final digits [2,9,9] form 299 which is largest monotone ≤ 332 [OK]

Hint: Decrement and set trailing digits to 9 for monotone fix [OK]

Common Mistakes:

• Stopping after first decrement without rechecking previous digits
• Not setting trailing digits to 9
• Returning intermediate digits without full fix

3. What is the time complexity of the optimal greedy algorithm for partitioning labels using a fixed-size array for last occurrences, given a string of length n?

medium

A. O(n) because each character is processed a constant number of times

B. O(n log n) due to sorting characters by last occurrence

C. O(n^2) due to nested scanning for last occurrences

D. O(n * 26) because of fixed alphabet size iteration

Solution

1. Step 1: Analyze last occurrence computation

   We scan the string once to record last occurrence of each character in O(n).

2. Step 2: Analyze partitioning loop

   We iterate over the string once more, updating partition end in O(1) per character.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans over string length n -> O(n) time [OK]

Hint: Two passes over string -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing fixed alphabet size iteration as O(n*26)
• Thinking sorting is needed

4. What is the time complexity of the optimal greedy solution for Two City Scheduling that sorts by cost difference and assigns people in a single pass?

medium

A. O(n^2) because of nested loops to assign people

B. O(n log n) due to sorting the list of 2n people

C. O(n) since assignment is done in one pass after sorting

D. O(n log n) including sorting and constant time assignment

Solution

1. Step 1: Identify sorting cost

   Sorting 2n people by cost difference takes O(n log n) time.

2. Step 2: Identify assignment cost

   Assigning people in a single pass is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting dominates, total complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity [OK]

Common Mistakes:

• Assuming assignment is nested loop causing O(n^2)
• Ignoring sorting cost and claiming O(n)
• Confusing space complexity with time complexity

5. If tasks can be reused infinitely (i.e., unlimited supply of each task type), how should the Task Scheduler algorithm be modified to find the minimum total time with cooldown n?

hard

A. Use the same max-heap approach but reset frequencies after each full cycle

B. Calculate the minimal cycle length as (n + 1) and multiply by the number of unique tasks

C. Since tasks are infinite, schedule tasks in a fixed repeating pattern of length (n + 1) without heap

D. The problem reduces to scheduling one task repeatedly with cooldown, so total time is tasks count

Solution

1. Step 1: Understand infinite reuse implication

   With infinite supply, the scheduler can always pick a different task to fill cooldown slots.

2. Step 2: Optimal scheduling pattern

   Tasks can be scheduled in a fixed repeating pattern of length n + 1, cycling through unique tasks to avoid idle time.

3. Step 3: Algorithm modification

   No need for frequency tracking or heap; just cycle through unique tasks repeatedly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Infinite tasks allow fixed pattern scheduling without heap [OK]

Hint: Infinite tasks -> fixed repeating pattern of length n+1 [OK]

Common Mistakes:

• Trying to use heap with infinite tasks
• Multiplying cycles incorrectly
• Ignoring cooldown constraints