# Sequence Reconstruction

ID: 605; medium

## Solution 1 (Java)

``````public class Solution {
/**
* @param org: a permutation of the integers from 1 to n
* @param seqs: a list of sequences
* @return: true if it can be reconstructed only one or false
*/
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
Map<Integer, Set<Integer>> graph = buildGraph(seqs);
List<Integer> topoOrder = getTopoOrder(graph);
if (topoOrder == null || topoOrder.size() != org.length)
return false;
for (int i = 0; i < topoOrder.size(); i++) {
if (topoOrder.get(i) != org[i])
return false;
}
return true;
}

private Map<Integer, Set<Integer>> buildGraph(int[][] seqs) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int[] seq : seqs) {
for (int i = 0; i < seq.length; i++) {
graph.putIfAbsent(seq[i], new HashSet<>());
}
}
for (int[] seq : seqs) {
for (int i = 1; i < seq.length; i++) {
}
}
return graph;
}

private List<Integer> getTopoOrder(Map<Integer, Set<Integer>> graph) {
Map<Integer, Integer> inDegree = getInDegree(graph);
Queue<Integer> q = new ArrayDeque<>();
List<Integer> topoOrder = new ArrayList<>();
for (Integer n : inDegree.keySet()) {
if (inDegree.get(n) == 0) {
q.offer(n);
}
}

while (!q.isEmpty()) {
if (q.size() > 1) return null;
Integer curr = q.poll();
for (Integer neighbor : graph.get(curr)) {
inDegree.put(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) == 0) {
q.offer(neighbor);
}
}
}
}

private Map<Integer, Integer> getInDegree(Map<Integer, Set<Integer>> graph) {
Map<Integer, Integer> inDegree = new HashMap<>();
for (Integer n : graph.keySet()) {
inDegree.put(n, 0);
}
for (Integer n : graph.keySet()) {
for (Integer nei : graph.get(n)) {
inDegree.put(nei, inDegree.get(nei) + 1);
}
}
return inDegree;
}
}``````

Last updated