# Java Solution using BFS Topological Sort

• ``````public class Solution {
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
Map<Integer, Set<Integer>> map = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();

for(int[] seq: seqs) {
if(seq.length == 1) {
if(!map.containsKey(seq[0])) {
map.put(seq[0], new HashSet<>());
indegree.put(seq[0], 0);
}
} else {
for(int i = 0; i < seq.length - 1; i++) {
if(!map.containsKey(seq[i])) {
map.put(seq[i], new HashSet<>());
indegree.put(seq[i], 0);
}

if(!map.containsKey(seq[i + 1])) {
map.put(seq[i + 1], new HashSet<>());
indegree.put(seq[i + 1], 0);
}

indegree.put(seq[i + 1], indegree.get(seq[i + 1]) + 1);
}
}
}
}

for(Map.Entry<Integer, Integer> entry: indegree.entrySet()) {
if(entry.getValue() == 0) queue.offer(entry.getKey());
}

int index = 0;
while(!queue.isEmpty()) {
int size = queue.size();
if(size > 1) return false;
int curr = queue.poll();
if(index == org.length || curr != org[index++]) return false;
for(int next: map.get(curr)) {
indegree.put(next, indegree.get(next) - 1);
if(indegree.get(next) == 0) queue.offer(next);
}
}
return index == org.length && index == map.size();
}
}
``````

• A nice solution!

• Refract the original post's code. Add some comments. Hope can help:) Also, thanks for sharing this idea.

``````public class Solution {
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
Map<Integer, Integer> indegree = new HashMap<>();
Map<Integer, List<Integer>> graph = new HashMap<>();
// set up graph
for (int[] seq: seqs) {
if (seq.length == 1) {
if (!indegree.containsKey(seq[0]))    indegree.put(seq[0], 0);
if (!graph.containsKey(seq[0]))   graph.put(seq[0], new ArrayList<Integer>());
} else {
for (int i = 0; i < seq.length-1; i++) {
int prev = seq[i];
int next = seq[i+1];
// indegree-related
if (!indegree.containsKey(prev))    indegree.put(prev, 0);
if (!indegree.containsKey(next))    indegree.put(next, 0);
indegree.put(next, indegree.get(next)+1);
// edge-related
if (!graph.containsKey(prev))   graph.put(prev, new ArrayList<Integer>());
if (!graph.containsKey(next))   graph.put(next, new ArrayList<Integer>());
}
}
}
// topological sort
for (int node: indegree.keySet()) {
if (indegree.get(node) == 0)    queue.offer(node);
}
int index = 0;
while (!queue.isEmpty()) {
int size = queue.size();
if (size > 1)   return false; // when size > 1, it means that there multiple ways of polling elements
int poll = queue.poll();
// index shouldnot arrive to the end of array yet
// check whether index==org.length to avoid the invalid getting element of org[index]
// uniqueness of sequence, we need to compare with org's corresponding element
if (index == org.length || poll != org[index])  return false;
index++;
for (int nb: graph.get(poll)) {
int nb_indegree = indegree.get(nb) - 1;
indegree.put(nb, nb_indegree);
if (nb_indegree == 0)   queue.offer(nb);
}
}
return index == org.length && index == indegree.size(); // check cycle
}
}
``````

• thanks for the solution. i am wondering why we can not use dfs to do topological sort to solve this problem?

• Could be shorter and faster:

``````public boolean sequenceReconstruction(int[] org, int[][] seqs) {
Map<Integer, List<Integer>> graph = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();
for (int[] seq : seqs) {
for (int i = 0; i < seq.length; i++) {
graph.putIfAbsent(seq[i], new ArrayList<Integer>());
indegree.putIfAbsent(seq[i], 0);
if (i > 0) {
indegree.put(seq[i], indegree.get(seq[i]) + 1);
}
}
}
if (org.length != indegree.size()) {
return false;
}

for (Map.Entry<Integer, Integer> entry : indegree.entrySet()) {
if (entry.getValue() == 0) {
}
}

int index = 0;
while (!q.isEmpty()) {
if (q.size() > 1) {
return false;
}
int curr = q.poll();
if (org[index++] != curr) {
return false;
}
for (int nb : graph.get(curr)) {
indegree.put(nb, indegree.get(nb) - 1);
if (indegree.get(nb) == 0) {
}
}
}
return index == org.length;
}``````

• Even shorter by optimizing the last part:

``````public boolean sequenceReconstruction(int[] org, int[][] seqs) {
Map<Integer, Set<Integer>> map = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();
for (int[] seq : seqs) {
for (int i : seq) {
map.putIfAbsent(i, new HashSet<>());
indegree.putIfAbsent(i, 0);
}
}

for (int[] seq : seqs) {
if (seq.length == 1) continue;
for (int i = 1; i < seq.length; i++)
indegree.put(seq[i], indegree.get(seq[i]) + 1);
}

if (org.length != indegree.size()) return false;

Queue<Integer> q = new ArrayDeque<>();
for (int key : indegree.keySet())

int cnt = 0;
while (q.size() == 1) {
for (int next : map.get(q.poll())) {
indegree.put(next, indegree.get(next) - 1);
}
cnt++;
}

return cnt == indegree.size();
}
``````

• Some explanation would be helpful.

• I saw other questions about `Topological sort`, some using `LinkedList` while others using `hashmap`. How to choose the data structure between these two?

Is there any important difference between these two structures to build a graph?

• @yavinci Can you handle this case:
[1]
[]
Expected: false

• Obviously, they made some changes to this question, adding some annoying corners cases...
Had to make some adjustment to make it pass. AC code below using Topological sort.

``````public class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
Map<Integer, Set<Integer>> map = new HashMap<>();
int[] degree = new int[org.length];

// for(int i = 1; i<=org.length; i++) map.put(i, new HashSet<>());
//cannot init map with org, has to do with seqs, to avoid case like [1], [], expected: false

for(List<Integer> list: seqs){
if(list.size()==1) map.computeIfAbsent(list.get(0), k->new HashSet<Integer>()); //dont forget
for(int i = 1; i<list.size(); i++){
int pre = list.get(i-1);
int cur = list.get(i);
map.computeIfAbsent(pre, k->new HashSet<Integer>());
map.computeIfAbsent(cur, k->new HashSet<Integer>());
if(pre>org.length || cur>org.length || pre<1 || cur<1) return false;
//dont forget. or degree array can "ArrayIndexOutOfBoundsException"

if(!map.get(pre).contains(cur)){
degree[cur-1]++;
}
}
}

for(int i = 0; i<degree.length; i++){
}
int index = 0;
while(!q.isEmpty()){
if(q.size()>1) return false; //check with org
int cur = q.poll();
if(org[index++] != cur) return false; //check with org
if(!map.containsKey(cur)) continue; //don't forget
for(int ii: map.get(cur)){
degree[ii-1]--;
}
}
return index == org.length && index==map.size();//has to check with map size
}
}
``````

Last thought... this question worth a Difficulty: Hard, considering those annoying corner cases.

• @shone you forget to think about the order in original sequence in the following part of your code

``````    while (q.size() == 1) {
for (int next : map.get(q.poll())) {
indegree.put(next, indegree.get(next) - 1);
}
cnt++;
}
``````

• Thank you for the great solution! Here is my C++ code.

``````class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
/* BFS topological sort */
int n = org.size();
vector<unordered_set<int>> edges(n+1, unordered_set<int>());
vector<int> degrees(n+1, 0);
/* to handle test case [1] [[ ], [ ]] */
bool empty = true;
for (vector<int> seq:seqs) {
if (seq.empty()) continue;
empty = false;
if (seq[0] < 1 || seq[0] > n) return false;
for (int i = 1; i < seq.size(); i++) {
if (seq[i] < 1 || seq[i] > n) return false;
if (edges[seq[i-1]].count(seq[i]) == 0) {
edges[seq[i-1]].insert(seq[i]);
degrees[seq[i]]++;
}
}
}
if (empty) return false;
queue<int> myq;
for (int i = 1; i <= n; i++) {
if (degrees[i] == 0) myq.push(i);
}
// In order to get a unique sequence, myq.size is always 1, also the order is the same as org
int idx = 0;
while (!myq.empty()) {
if (myq.size() > 1) return false;
int k = myq.front();
myq.pop();
if (k != org[idx++]) return false;
for (int i:edges[k]) {
if (--degrees[i] == 0) myq.push(i);
}
}
return idx == n;
}
};
``````

• @zestypanda good idea, your idea in java

``````public class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
int n = org.length;
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[n + 1];

for(int i = 0; i < n + 1; i++) {
}

boolean empty = true;

for(List<Integer> seq : seqs) {
if(seq.size() == 0) continue;
else {
empty = false;
}

if(seq.get(0) < 1 || seq.get(0) > n) {
return false;
}

for(int i = 1; i < seq.size(); i++) {
int u = seq.get(i - 1), v = seq.get(i);
if(u < 1 || u > n || v < 1 || v > n) {
return false;
}

if(!graph.get(u).contains(v)) {
if(indegree[v] == -1) indegree[v] = 0;
indegree[v]++;
}
}
}

if(empty) return false;//for [1], [[], []]

int count = 0;

for(int i = 1; i <= n; i++) {
if(indegree[i] == 0) {
count++;
q.offer(i);
}
}

while(!q.isEmpty()) {
if(q.size() != 1) {
return false;
}

int cur = q.poll();

count++;
}
}
}

return count == n;
}
}
``````

• putIfAbsent

Thank you for your solution, however I just found out this line has problem which will cause following case failed.
[1,2,3]
[[1,2],[1,3],[2,3]]
the fix is :
if(!indegree.containsKey(seq[i])
indegree.putIfAbsent(seq[i], 0);

• Can anyone please explain what these two conditions check for?

if(index == org.length || curr != org[index++]) return false;

return index == org.length && index == map.size();

Thanks

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