0129MediumArrayStringDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryShortest PathBellman–Ford AlgorithmFloyd–Warshall Algorithm

Gear Train Ratios

Tracked in this browser only

Write code

Trains the technique from

LeetCode 399Evaluate Division

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 workshop is documenting a gear train. You are given meshes, where meshes[i] = [driver, driven] names two gears that mesh, together with ratios, where ratios[i] is how many turns driver makes for one single turn of driven.

Each entry of queries is a pair [top, bottom] asking how many turns top makes for one single turn of bottom. A gear that meshes with a chain of others turns in step with all of them, so a query can be settled whenever the two gears are linked through any run of meshes, in either direction.

Return one answer per query, in the order the queries are given, each rounded to 5 decimal places. Answer -1.0 when the query cannot be settled: either one of the two gears is absent from meshes, or both are present but no run of meshes links them. A gear named twice in one query turns exactly once per one of its own turns, so the answer is 1.0 when that gear appears in meshes and -1.0 when it does not.

Examples

Example 1

Input: meshes = [["crank", "spool"], ["spool", "drum"]], ratios = [3.0, 0.5], queries = [["crank", "drum"], ["drum", "crank"], ["crank", "crank"], ["hub", "hub"], ["crank", "hub"]]
Output: [1.5, 0.66667, 1.0, -1.0, -1.0]

The crank makes 3 turns per spool turn and the spool makes 0.5 turns per drum turn, so the crank makes 1.5 turns per drum turn and the drum makes 0.66667 turns per crank turn. The hub is never mentioned in the meshes, so both queries naming it are unsettled.

Example 2

Input: meshes = [["cam", "idler"]], ratios = [4.0], queries = [["idler", "cam"], ["cam", "idler"], ["idler", "idler"]]
Output: [0.25, 4.0, 1.0]

The recorded mesh reads forward, so reading it backward gives the idler 0.25 turns per cam turn.

Example 3

Input: meshes = [["a1", "b2"], ["c3", "d4"]], ratios = [2.0, 5.0], queries = [["a1", "d4"], ["a1", "b2"], ["d4", "c3"], ["b2", "z9"]]
Output: [-1.0, 2.0, 0.2, -1.0]

Two separate trains are documented. Gears in different trains are not linked, so that query is unsettled, and z9 is not documented at all.

Constraints

1 <= meshes.length <= 20
meshes[i].length == 2
1 <= meshes[i][0].length, meshes[i][1].length <= 5
meshes[i][0] != meshes[i][1]
ratios.length == meshes.length
0.0 < ratios[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= queries[i][0].length, queries[i][1].length <= 5
Gear names hold lowercase English letters and digits
The recorded meshes never contradict one another, so a linked pair of gears has one well defined ratio
Each answer is rounded to 5 decimal places

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 gear_ratios(meshes: list[list[str]], ratios: list[float], queries: list[list[str]]) -> list[float]:

Java

public double[] gearRatios(List<List<String>> meshes, double[] ratios, List<List<String>> queries)

The intended approach

Time O(q * (V + E)) for q queries over V gears and E meshesSpace O(V + E)

Treat gears as nodes and each mesh as a pair of directed links: the recorded ratio one way and its reciprocal the other way, since reading a mesh backwards divides instead of multiplying. Then a query is a walk from `top` to `bottom`, and the answer is the product of the link values along it. Depth-first search from `top`, carrying the running product and marking gears already reached, and report the sentinel when either gear is undocumented or the walk never arrives.

Pythonentry point: gear_ratios

def gear_ratios(meshes, ratios, queries):
    train = {}
    for (driver, driven), turns in zip(meshes, ratios):
        train.setdefault(driver, []).append((driven, turns))
        train.setdefault(driven, []).append((driver, 1.0 / turns))
    answers = []
    for top, bottom in queries:
        if top not in train or bottom not in train:
            answers.append(-1.0)
            continue
        if top == bottom:
            answers.append(1.0)
            continue
        reached = {top}
        stack = [(top, 1.0)]
        found = None
        while stack:
            here, carried = stack.pop()
            if here == bottom:
                found = carried
                break
            for nxt, turns in train[here]:
                if nxt not in reached:
                    reached.add(nxt)
                    stack.append((nxt, carried * turns))
        answers.append(-1.0 if found is None else round(found, 5))
    return answers

The obvious version

Fill an all-pairs table instead of walking per query: seed it with the recorded meshes and their reciprocals, then relax every pair through every possible middle gear, so a missing entry gets filled by chaining two known entries. Queries become a table lookup. O(V^3) and it never searches.

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_gear_ratios(meshes, ratios, queries):
    names = sorted({name for pair in meshes for name in pair})
    slot = {name: i for i, name in enumerate(names)}
    size = len(names)
    table = [[None] * size for _ in range(size)]
    for i in range(size):
        table[i][i] = 1.0
    for (driver, driven), turns in zip(meshes, ratios):
        table[slot[driver]][slot[driven]] = turns
        table[slot[driven]][slot[driver]] = 1.0 / turns
    for k in range(size):
        for i in range(size):
            for j in range(size):
                if table[i][j] is None and table[i][k] is not None and table[k][j] is not None:
                    table[i][j] = table[i][k] * table[k][j]
    answers = []
    for top, bottom in queries:
        if top in slot and bottom in slot and table[slot[top]][slot[bottom]] is not None:
            answers.append(round(table[slot[top]][slot[bottom]], 5))
        else:
            answers.append(-1.0)
    return answers

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
3 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