What is the time complexity of the optimal greedy solution that sorts the greed and cookie arrays before assigning cookies to children?

medium🪤 Complexity Trap Q13 of Q15

Greedy Algorithms - Assign Cookies

AO(n + m) because sorting is not needed if arrays are scanned directly

BO(n * m) where n is number of children and m is number of cookies

CO(n log n + m log m) due to sorting both arrays, then O(n + m) for assignment

DO(n^2) because each child is compared to all cookies in worst case

Step-by-Step Solution

Step 1: Identify sorting costs
Sorting greed array of size n costs O(n log n), sorting cookies array of size m costs O(m log m).
Step 2: Analyze assignment loop
Two pointers scan both arrays once, costing O(n + m).
Final Answer:
Option C -> Option C
Quick Check:
Sorting dominates complexity, linear scan is minor [OK]

Quick Trick: Sorting dominates; assignment is linear [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Many think nested loops are needed, but greedy uses two pointers linearly after sorting.

Interviewer Note:

CONTEXT

Master "Assign Cookies" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Greedy Algorithms Quizzes