Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/444.html
444. Sequence Reconstruction
Level
Medium
Description
Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.
Example 1:
Input:
org: [1,2,3], seqs: [[1,2],[1,3]]
Output:
false
Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.
Example 2:
Input:
org: [1,2,3], seqs: [[1,2]]
Output:
false
Explanation:
The reconstructed sequence can only be [1,2].
Example 3:
Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
Output:
true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
Example 4:
Input:
org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]
Output:
true
Solution
If only one sequence can be reconstructed from seqs, then seqs must contain all adjacent subsequences of length 2 in org. It is possible that seqs contains a subsequence that has length greater than 2 and the elements in the subsequence are all adjacent in org. Besides, seqs must contain all the numbers in org but can’t contain any number that is not in org.
Use a map to store each number and its corresponding index in org. Use an array of type boolean to store whether each adjacent subsequence is contained in seqs. Use a set to store the numbers in seqs.
Loop over org to fill in the map. For each sequence in seqs, first check all the numbers in the sequence. If a number is greater than org.length, then the number can’t be in org, so return false. Otherwise, add the number to the set. Then check each pair of adjacent numbers. If two adjacet numbers’ indices in org are adjacent and the former number’s index is less than the latter number’s index, then set the element at the former number’s index in the boolean array to true. If the former number’s index is greater than or equal to the latter number’s index, then there is a conflict, so return false.
After the loop, check the set’s size. If the set’s size is less than org.length, then return false. Then check all the elements in the boolean array. If there is a false, then return false. Otherwise, return true.
-
class Solution { public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) { if (seqs == null) return org == null; if (seqs.size() == 0) return org.length == 0; Map<Integer, Integer> numIndexMap = new HashMap<Integer, Integer>(); int length = org.length; for (int i = 0; i < length; i++) numIndexMap.put(org[i], i); boolean[] adjacentSequences = new boolean[length - 1]; Set<Integer> set = new HashSet<Integer>(); for (List<Integer> sequence : seqs) { for (int num : sequence) { if (num > length) return false; else set.add(num); } int size = sequence.size(); for (int i = 1; i < size; i++) { int num1 = sequence.get(i - 1), num2 = sequence.get(i); int index1 = numIndexMap.getOrDefault(num1, -1); int index2 = numIndexMap.getOrDefault(num2, -1); if (index1 < 0 || index2 < 0 || index1 >= index2) return false; if (index2 - index1 == 1) adjacentSequences[index1] = true; } } if (set.size() < length) return false; for (boolean adjacentSequence : adjacentSequences) { if (!adjacentSequence) return false; } return true; } } -
class Solution: def sequenceReconstruction( self, nums: List[int], sequences: List[List[int]] ) -> bool: g = defaultdict(list) indeg = [0] * len(nums) for seq in sequences: for a, b in pairwise(seq): g[a - 1].append(b - 1) indeg[b - 1] += 1 q = deque(i for i, v in enumerate(indeg) if v == 0) while q: if len(q) > 1: return False i = q.popleft() for j in g[i]: indeg[j] -= 1 if indeg[j] == 0: q.append(j) return True ############ import collections class Solution(object): def sequenceReconstruction(self, org, seqs): """ :type org: List[int] :type seqs: List[List[int]] :rtype: bool """ n = len(org) graph = collections.defaultdict(list) visited = {} incomings = collections.defaultdict(int) nodes = set() for seq in seqs: nodes |= set(seq) if len(seq) > 0: incomings[seq[0]] += 0 for i in range(0, len(seq) - 1): start, end = seq[i], seq[i + 1] graph[start].append(end) incomings[end] += 1 count = 0 for node in incomings: if incomings[node] == 0: count += 1 if count == 2: return False order = [] visited = collections.defaultdict(int) queue = [q for q in incomings if incomings[q] == 0] while len(queue) == 1: top = queue.pop() order.append(top) for nbr in graph[top]: incomings[nbr] -= 1 if incomings[nbr] == 0: queue.append(nbr) if len(queue) > 1: return False if order == org and len(order) == len(nodes): return True return False -
class Solution { public: bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) { int n = nums.size(); vector<vector<int>> g(n); vector<int> indeg(n); for (auto& seq : sequences) { for (int i = 1; i < seq.size(); ++i) { int a = seq[i - 1] - 1, b = seq[i] - 1; g[a].push_back(b); ++indeg[b]; } } queue<int> q; for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i); while (!q.empty()) { if (q.size() > 1) return false; int i = q.front(); q.pop(); for (int j : g[i]) if (--indeg[j] == 0) q.push(j); } return true; } }; -
func sequenceReconstruction(nums []int, sequences [][]int) bool { n := len(nums) g := make([][]int, n) indeg := make([]int, n) for _, seq := range sequences { for i := 1; i < len(seq); i++ { a, b := seq[i-1]-1, seq[i]-1 g[a] = append(g[a], b) indeg[b]++ } } q := []int{} for i, v := range indeg { if v == 0 { q = append(q, i) } } for len(q) > 0 { if len(q) > 1 { return false } i := q[0] q = q[1:] for _, j := range g[i] { indeg[j]-- if indeg[j] == 0 { q = append(q, j) } } } return true }