Is this order valid · DSA Mastery

Scenario

You work on a bank app's account-opening flow. There are n checklist steps, numbered 0 to n - 1, and some must happen before others: the identity check comes before the first deposit.

A clerk recorded the order in which they did the steps. An auditor wants a quick check: did the clerk do every step exactly once, and did every rule hold? The clerk's record may be wrong in other ways too, such as a step done twice or a step missing.

Your task

Write is_valid_order(n, rules, order).

n is the number of steps.
rules[i] = [before, after] means step before must happen earlier than step after.
order is the list of steps in the order the clerk did them.
Return True when order contains every step from 0 to n - 1 exactly once and every rule holds. Return False otherwise.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 4, rules = [[0, 1], [0, 2], [1, 3], [2, 3]], order = [0, 2, 1, 3]
Output: true

Write down where each step happens: step 0 at place 0, step 2 at place 1, step 1 at place 2, step 3 at place 3. Then check each rule.

Rule	Place of before	Place of after	Holds?
[0, 1]	0	2	yes
[0, 2]	0	1	yes
[1, 3]	2	3	yes
[2, 3]	1	3	yes

Every rule points forward, so the answer is true. Steps 1 and 2 could swap places and the order would still be valid.

Example 2#

text2 lines

Input:  n = 4, rules = [[0, 1], [0, 2], [1, 3], [2, 3]], order = [1, 0, 2, 3]
Output: false

Step 1 happens at place 0 and step 0 at place 1. The rule [0, 1] needs step 0 earlier, so it is broken.

Example 3#

text2 lines

Input:  n = 4, rules = [], order = [0, 1, 2]
Output: false

The clerk's record has only 3 of the 4 steps. Step 3 is missing, so the order is not complete, whatever the rules say.

Constraints

1 ≤ n ≤ 100,000
0 ≤ len(rules) ≤ 200,000, and every row is [before, after] with 0 ≤ before, after < n and before ≠ after
0 ≤ len(order) ≤ 100,000, and each entry is between 0 and 99,999, so it can be outside 0 to n - 1

What does n ≤ 100000 tell you?

There can be 100,000 steps and 200,000 rules. Looking up the place of a step by searching the order costs up to n each, so checking m rules is m × n: 20 billion steps. Write each step's place into a list once. Then each rule needs two lookups of one step each, and the whole check is n + m.

Scenario

You work on a bank app's account-opening flow. There are n checklist steps, numbered 0 to n - 1, and some must happen before others: the identity check comes before the first deposit.

Your task

Write is_valid_order(n, rules, order).

n is the number of steps.
rules[i] = [before, after] means step before must happen earlier than step after.
order is the list of steps in the order the clerk did them.
Return True when order contains every step from 0 to n - 1 exactly once and every rule holds. Return False otherwise.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 4, rules = [[0, 1], [0, 2], [1, 3], [2, 3]], order = [0, 2, 1, 3]
Output: true

Write down where each step happens: step 0 at place 0, step 2 at place 1, step 1 at place 2, step 3 at place 3. Then check each rule.

Rule	Place of before	Place of after	Holds?
[0, 1]	0	2	yes
[0, 2]	0	1	yes
[1, 3]	2	3	yes
[2, 3]	1	3	yes

Every rule points forward, so the answer is true. Steps 1 and 2 could swap places and the order would still be valid.

Example 2#

text2 lines

Input:  n = 4, rules = [[0, 1], [0, 2], [1, 3], [2, 3]], order = [1, 0, 2, 3]
Output: false

Step 1 happens at place 0 and step 0 at place 1. The rule [0, 1] needs step 0 earlier, so it is broken.

Example 3#

text2 lines

Input:  n = 4, rules = [], order = [0, 1, 2]
Output: false

The clerk's record has only 3 of the 4 steps. Step 3 is missing, so the order is not complete, whatever the rules say.

Constraints

1 ≤ n ≤ 100,000
0 ≤ len(rules) ≤ 200,000, and every row is [before, after] with 0 ≤ before, after < n and before ≠ after
0 ≤ len(order) ≤ 100,000, and each entry is between 0 and 99,999, so it can be outside 0 to n - 1

What does n ≤ 100000 tell you?