684. Only One Order
A film festival must screen n shorts labelled 1 to n. The array nums is a proposed running order, a permutation of these labels. Each list in sequences is a requirement from a sponsor: the shorts in that list (each label between 1 and n) must be screened in the listed relative order, although other shorts may be shown in between. A list that names the same label twice can never be satisfied.
Return true if nums satisfies every requirement and no other permutation of the labels does; return false if it breaks a requirement or if some different permutation also satisfies all of them.
Target time linear in n plus the total length of all the lists.
Example 1
- Input:
- nums = [2,4,1,3], sequences = [[2,4],[4,1],[1,3]]
- Output:
- true
- Explanation:
The pairs 2-4, 4-1 and 1-3 chain all four labels together, so the order 2, 4, 1, 3 is forced.
Example 2
- Input:
- nums = [2,1,3], sequences = [[1,3],[2,3]]
- Output:
- false
- Explanation:
Labels 1 and 2 are not ordered relative to each other, so 1, 2, 3 would also work and the order is not unique.
Example 3
- Input:
- nums = [1,2], sequences = [[2,1]]
- Output:
- false
- Explanation:
The sponsor wants 2 before 1, which the proposed order breaks.
Constraints
1 ≤ n ≤ 100000
nums is a permutation of 1..n
1 ≤ sequences.length ≤ 100000; 1 ≤ sequences[i].length ≤ n; the total length of all sequences is at most 200000
1 ≤ sequences[i][j] ≤ n; a label may repeat inside a list
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + L)
- Space
- O(n + L)