0659MediumArrayDepth-First SearchGraph TheoryTopological SortDirected Acyclic Graph

Steadiest Hand in the Workshop

Tracked in this browser only

Trains the technique from

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 has n members labelled 0 to n - 1. Every member has a different steadiness score; patience[i] is the score of member i, and a smaller score means a steadier hand.

You are also given pairs. Each pairs[i] = [a, b] is a note from the foreman saying member a has strictly more workshop experience than member b. Experience carries through the notes: if a has more than b and b has more than c, then a has more than c. The notes never contradict each other.

For every member x, consider the members who have at least as much experience as x, which always includes x. Exactly one of them has the smallest steadiness score. Return the list answer where answer[x] is that member's label.

Examples

Example 1

Input: pairs = [[0, 1], [1, 2]], patience = [0, 2, 1]
Output: [0, 0, 0]

Member 0 has more experience than member 1, who has more than member 2, so member 0 also has more than member 2. Member 0's score of 0 is the smallest in the workshop, and member 0 counts for all three members, so every entry is 0.

Example 2

Input: pairs = [[0, 2], [1, 2], [2, 3]], patience = [3, 1, 0, 2]
Output: [0, 1, 2, 2]

Members 0 and 1 have no notes above them, so each keeps their own label. Member 2's score of 0 beats members 0 and 1, so entry 2 is member 2. Member 3 is under members 2, 0 and 1, and member 2's score of 0 is the smallest of the four, so entry 3 is member 2 as well.

Example 3

Input: pairs = [], patience = [2, 0, 1]
Output: [0, 1, 2]

With no notes at all, nobody is known to have more experience than anyone else, so each member is the only candidate for their own entry.

Constraints

1 <= patience.length <= 500
patience holds each integer from 0 to patience.length - 1 exactly once.
0 <= pairs.length <= patience.length * (patience.length - 1) / 2
pairs[i].length == 2
0 <= pairs[i][0], pairs[i][1] < patience.length
pairs[i][0] != pairs[i][1]
No two notes record the same ordered pair, and the notes are consistent.

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 steadiest_peer(pairs: list[list[int]], patience: list[int]) -> list[int]:

Java

public int[] steadiestPeer(int[][] pairs, int[] patience)

The intended approach

Time O(n + e) where e is the number of notes: each member and note is handled once.Space O(n + e) for the adjacency lists, the counts and the answers.

Treat each note as an edge from the more experienced member to the less experienced one; consistency makes the result acyclic. A member's answer is the steadiest of their own score and the answers already settled for the members immediately above them, so process the members in an order where nobody is handled before all of their direct superiors. Count how many notes point at each member, start with the members no note points at, and each time a member is settled push their answer down to the members below and release those whose count has run out.

Pythonentry point: steadiest_peer

def steadiest_peer(pairs, patience):
    # Edges run from the more experienced member to the less experienced one, so a
    # member's answer is settled once every direct superior has been settled. Walk
    # the members in that order with a queue driven by in-degrees, pushing each
    # settled answer down to the members immediately below.
    # O(n + e) time, O(n + e) space.
    n = len(patience)
    below = [[] for _ in range(n)]
    waiting = [0] * n
    for pair in pairs:
        a, b = pair[0], pair[1]
        below[a].append(b)
        waiting[b] += 1
    best = list(range(n))
    ready = [i for i in range(n) if waiting[i] == 0]
    head = 0
    while head < len(ready):
        x = ready[head]
        head += 1
        for y in below[x]:
            if patience[best[x]] < patience[best[y]]:
                best[y] = best[x]
            waiting[y] -= 1
            if waiting[y] == 0:
                ready.append(y)
    return best

The obvious version

Build the full boolean table of who has more experience than whom by starting from the notes and closing it under chaining with three nested loops over the members. Then for each member scan the whole table row and keep the smallest steadiness score found, the member themselves included.

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_steadiest_peer(pairs, patience):
    n = len(patience)
    above = [[False] * n for _ in range(n)]
    for pair in pairs:
        above[pair[1]][pair[0]] = True
    for k in range(n):
        for i in range(n):
            if above[i][k]:
                row_k = above[k]
                row_i = above[i]
                for j in range(n):
                    if row_k[j]:
                        row_i[j] = True
    answer = []
    for x in range(n):
        pick = x
        for y in range(n):
            if above[x][y] and patience[y] < patience[pick]:
                pick = y
        answer.append(pick)
    return answer

How this problem was checked

Reference solution executed against 10 test cases — 10 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