← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
Practice/Google/Leetcode 444. Sequence Reconstruction
CodingMust
You are given an array original representing a sequence of unique integers, and a list sequences where each element is a subsequence (a list of integers preserving relative order from some larger sequence).
Your task is to determine whether the given sequences can uniquely reconstruct the original sequence. In other words:
original is the only valid ordering of elements that respects all the ordering constraints from sequences?original must appear in at least one sequence in sequences.original must appear as consecutive elements in at least one sequence in sequences.Return true if sequences uniquely reconstructs original, otherwise return false.
original appears in at least one sequenceoriginal, there exists at least one sequence containing them consecutivelysequences do not allow for any alternative valid ordering besides originaltrue only if original is the unique topological ordering satisfying all constraintsoriginal are uniquesequences[i] are unique within that subsequenceExample 1:
Input: original = [1, 2, 3, 4], sequences = [[1, 2], [2, 3], [3, 4]] Output: true Explanation: The sequences establish that 1 must come before 2, 2 before 3, and 3 before 4. This uniquely determines the order [1, 2, 3, 4].
Example 2:
Input: original = [1, 2, 3], sequences = [[1, 2], [1, 3]] Output: false Explanation: We know 1 comes before 2, and 1 comes before 3, but we don't know the relative order of 2 and 3. Both [1, 2, 3] and [1, 3, 2] are valid, so the reconstruction is not unique.
Example 3:
Input: original = [1, 2, 3], sequences = [[1, 2], [2, 3], [3, 1]] Output: false Explanation: The sequences create a cycle (3→1 conflicts with 1→2→3), so they cannot reconstruct the original sequence.