0843MediumArrayGraph TheoryTopological SortDirected Acyclic Graph

Is the Running Order Forced

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 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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n + S) for n acts and total fragment length S.Space O(n) for the positions and the pinned marks.

Record where each act sits in the master order. Every fragment must run strictly forward through those positions, and must not name an act the master order lacks, or the master order does not agree with it at all. For the master order to be the only one that agrees, each neighbouring pair of acts in it must be forced to stay in that order, and only a fragment that names those two acts one after the other forces it. So mark each neighbouring pair a fragment pins, and require that every one of them is pinned.

Pythonentry point: only_one_running_order

def only_one_running_order(nums, sequences):
    n = len(nums)
    place = {value: i for i, value in enumerate(nums)}
    # every listed fragment must run forward through nums, and consecutive
    # entries of nums must be pinned by some fragment or the order is not unique
    pinned = [False] * max(n - 1, 1)
    for fragment in sequences:
        for i in range(len(fragment)):
            if fragment[i] not in place:
                return False
            if i == 0:
                continue
            a = place[fragment[i - 1]]
            b = place[fragment[i]]
            if b <= a:
                return False
            if b == a + 1:
                pinned[a] = True
    for i in range(n - 1):
        if not pinned[i]:
            return False
    return True

The obvious version

Enumerate every ordering of the acts, keep those that agree with all the fragments, and report whether exactly one survives and it is the master order. Factorial, but it reads the definition of uniqueness off literally.

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_only_one_running_order(nums, sequences):
    import itertools
    n = len(nums)
    values = sorted(nums)

    def holds(order):
        spot = {value: i for i, value in enumerate(order)}
        for fragment in sequences:
            for i in range(1, len(fragment)):
                if fragment[i - 1] not in spot or fragment[i] not in spot:
                    return False
                if spot[fragment[i - 1]] >= spot[fragment[i]]:
                    return False
        for fragment in sequences:
            for value in fragment:
                if value not in spot:
                    return False
        return True

    hits = 0
    for order in itertools.permutations(values):
        if holds(list(order)):
            hits += 1
            if hits > 1:
                return False
    return hits == 1 and holds(nums)

How this problem was checked

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