Show problems as
Classic problem #444MediumArrayGraph TheoryTopological SortDirected Acyclic Graph

Sequence Reconstruction

Real-world version: Is the Running Order Forced
Tracked in this browser only
Read Sequence Reconstruction on LeetCode(opens in a new tab)

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

Learn the pattern firstDirected Acyclic Graph (DAG) Traversal · Graphs, animated step by step

A festival keeps a master running order nums, which lists every act exactly once. Act numbers run from 1 to n, where n is the length of nums.

sequences holds fragments recovered from old posters. A running order agrees with a fragment when every act the fragment names appears in the running order and the fragment's acts appear in that same relative order, though not necessarily next to each other.

Return true when nums is the only running order of the acts 1 through n that agrees with every fragment, and false otherwise.

Examples

Example 1

Input
nums = [1, 2, 3], sequences = [[1, 2], [1, 3]]
Output
false

The running order [1, 3, 2] also agrees with both fragments, since 1 comes before 2 in it and 1 comes before 3, so [1, 2, 3] is not the only one.

Example 2

Input
nums = [1, 2, 3], sequences = [[1, 2], [1, 3], [2, 3]]
Output
true

Together the fragments put 1 before 2, 1 before 3 and 2 before 3, and [1, 2, 3] is the only running order of the three acts that does all of that.

Example 3

Input
nums = [1, 2], sequences = [[2, 1]]
Output
false

The fragment puts act 2 before act 1, which the running order [1, 2] contradicts, so [1, 2] does not agree with the fragment at all.

Constraints

  • 1 <= nums.length <= 10^4
  • nums lists each of the integers from 1 to nums.length exactly once
  • 1 <= sequences.length <= 10^4
  • 1 <= sequences[i].length <= 10^4
  • 1 <= sequences[i][j] <= 10^4

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 only_one_running_order(nums: list[int], sequences: list[list[int]]) -> bool:
Java
public boolean onlyOneRunningOrder(int[] nums, List<List<Integer>> sequences)

More on the same topics