0432MediumArrayHash TableStringGraph TheoryTopological SortDirected Acyclic Graph

Fabrication Cards in a Model Workshop

Tracked in this browser only

Trains the technique from

LeetCode 2115Find All Possible Recipes from Given Supplies

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A model workshop owns a drawer of components and a book of fabrication cards.

Card i makes the part named builds[i], and running it consumes one of every component named in needs[i]. A name on a card may refer to something already in the drawer, to a part that another card makes, or to something the workshop has no way of getting at all.

The drawer starts out holding the components named in stock. A card may be run whenever every name on its list is available, and the part it makes becomes available from then on. Availability is not used up: once a name is available, any number of cards may draw on it, in any order, as often as they like.

Return the names of all the parts the workshop can end up making. The names may be returned in any order.

Every name in builds and stock taken together is distinct, and no card lists the same name twice.

Examples

Example 1

Input: builds = ["cab", "roof", "seat"], needs = [["roof", "seat"], ["ply"], ["ply", "glue"]], stock = ["ply", "glue"]
Output: ["roof", "seat", "cab"]

The drawer holds ply and glue, so the second and third cards can be run at once, and the two parts they make are exactly what the first card lists.

Example 2

Input: builds = ["boiler", "dome"], needs = [["dome"], ["boiler"]], stock = ["copper"]
Output: []

The drawer holds only copper, and neither card lists copper, so neither card's list is met while the drawer stands as it is.

Example 3

Input: builds = ["smokebox", "buffer"], needs = [["steel", "rivet"], ["steel"]], stock = ["steel"]
Output: ["buffer"]

The second card needs only steel, which is in the drawer. The first card also lists a rivet, a name that is neither in the drawer nor made by any card.

Example 4

Input: builds = ["lamp", "lens", "bulb"], needs = [["lens", "bulb"], ["glass"], ["filament", "lamp"]], stock = ["glass", "filament"]
Output: ["lens"]

The lens card lists only glass, which is in the drawer, so it runs and the lens joins the available names. No other card's list is covered by glass, filament and the lens.

Constraints

n == builds.length == needs.length
1 <= n <= 100
1 <= needs[i].length, stock.length <= 100
1 <= builds[i].length, needs[i][j].length, stock[k].length <= 10
builds[i], needs[i][j] and stock[k] consist only of lowercase English letters.
All the names in builds and stock combined are distinct.
No needs[i] contains a repeated name.

The values you return may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_all_recipes(builds: list[str], needs: list[list[str]], stock: list[str]) -> list[str]:

Java

public List<String> findAllRecipes(String[] builds, List<List<String>> needs, String[] stock)

The intended approach

Time O(T) where T is the total number of names across builds, needs and stock: each name is read once when the counts are built and each card is queued at most once.Space O(T): the waiting index holds one entry per missing name on a card, plus the count array, the queue and the returned list.

Give every card a count of how many of its listed names are missing from the drawer, and file each card under the missing names it is waiting on. Cards whose count is already zero go into a queue. Popping a card records the part it makes and decrements the count of every card filed under that part's name, pushing any card whose count reaches zero. The queue drains once nothing more can be unblocked, and the cards still holding a positive count are precisely the ones that can never run.

Pythonentry point: find_all_recipes

def find_all_recipes(builds, needs, stock):
    # Treat each card as a node that is blocked by however many of its listed
    # components are not in the drawer yet. Index the blocked cards by the name
    # they are waiting on, then release cards in waves: a card whose block count
    # falls to zero can be run, and running it makes its own part available, which
    # may unblock further cards. Cards left blocked forever are exactly those
    # caught in a loop or waiting on a name nobody makes.
    # O(T) time and O(T) space where T is the total size of the three arrays.
    available = set(stock)
    blocked = [0] * len(builds)
    waiting = {}
    for index, parts in enumerate(needs):
        for part in parts:
            if part not in available:
                blocked[index] += 1
                waiting.setdefault(part, []).append(index)
    queue = [i for i in range(len(builds)) if blocked[i] == 0]
    finished = []
    head = 0
    while head < len(queue):
        index = queue[head]
        head += 1
        name = builds[index]
        finished.append(name)
        for other in waiting.get(name, ()):
            blocked[other] -= 1
            if blocked[other] == 0:
                queue.append(other)
    return finished

The obvious version

Keep a set of available names and sweep the whole card book over and over, running any card whose names are all present and adding its part to the set. Stop when a full sweep changes nothing. Each sweep re-reads every card, so the cost is quadratic in the number of cards.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_all_recipes(builds, needs, stock):
    available = set(stock)
    made = [False] * len(builds)
    moved = True
    while moved:
        moved = False
        for index in range(len(builds)):
            if made[index]:
                continue
            if all(part in available for part in needs[index]):
                made[index] = True
                available.add(builds[index])
                moved = True
    return [builds[i] for i in range(len(builds)) if made[i]]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in