Why it works
- A recipe reaches 0 missing only after each of its ingredients has come out of the queue, and only supplies and made recipes ever go into it.
- A made recipe goes into the queue like a supply, so a recipe that needs it, such as pasta after dough, gets its turn.
- An ingredient that is neither a supply nor a makeable recipe never comes out of the queue, so a recipe that needs it, and every recipe after it, keeps a count above 0. A loop of recipes stays above 0 the same way.
Complexity
Time O(r + i + s) for r recipes, i ingredients in all the lists and s supplies: each list entry becomes one arrow and is followed once, and each item enters the queue at most once. Memory O(r + i + s) for the arrows, the counts and the queue.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗