# Beat 91% Concise Java solution and Beat 80% Topological solution using LinkedList()

• ``````public class Solution {
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
if (seqs.length == 0) return org.length == 0;
int n = org.length;
int[] index = new int[n + 1];
boolean[] pair = new boolean[n];
for (int i = 0; i < n; i++) {
index[org[i]] = i;
}
for (int[] s : seqs) {
for (int i = 0; i < s.length; i++) {
if (s[i] > n || s[i] <= 0) return false;
if (i > 0 && index[s[i - 1]] >= index[s[i]]) return false;
if (i > 0 && index[s[i - 1]] + 1 == index[s[i]]) pair[index[s[i - 1]]] = true;
}
}
for (int i = 0; i < n - 1; i++) {
if (!pair[i]) return false;
}
return true;
}
}
``````

This is my first tried solution, the tricky part is to decide when we should return false.

1. we need to constraint the numbers in seqs[][], `seqs[i][j] should be >= 1 && <= n`;
2. `if there are more than 1 next node in queue`, return false;
3. `if next node != org[idx++]`, return false; This is the core part.
4. `if idx != org.length`, return false; it could less than org.length, like the example 2: org: [1,2,3], seqs: [[1,2]]
``````public class Solution {
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
if (seqs.length == 0) return org.length == 0;
int n = org.length;
List<List<Integer>> graph = new ArrayList(n + 1);
int[] inDegree = new int[n + 1];

// initGraph
for (int i = 0; i <= n; i++) graph.add(new ArrayList());
for (int[] s : seqs) {
if (s.length == 1) {
if (s[0] <= 0 || s[0] > n) return false;
} else {
for (int i = 0; i < s.length - 1; i++) {
if (s[i] <= 0 || s[i] > n || s[i + 1] <= 0 || s[i + 1] > n) return false;
inDegree[s[i + 1]]++;
}
}
}

// bfs
Queue<Integer> q = new ArrayDeque();
for (int i = 1; i < inDegree.length; i++) {
if (q.size() > 1) return false;
}
int idx = 0;
while (!q.isEmpty()) {
if (q.size() > 1) return false;
int cur = q.poll();
if (idx >= org.length || cur != org[idx++]) return false;
for (int to : graph.get(cur)) {
inDegree[to]--;
if (inDegree[to] == 0) {
q.offer(to);
}
}
}
return idx == org.length;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.