Show problems as
Classic problem #851MediumArrayDepth-First SearchGraph TheoryTopological SortDirected Acyclic Graph

Loud and Rich

Real-world version: Steadiest Hand in the Workshop
Tracked in this browser only
Read Loud and Rich on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def steadiest_peer(pairs: list[list[int]], patience: list[int]) -> list[int]:
Java
public int[] steadiestPeer(int[][] pairs, int[] patience)

More on the same topics