Java Solution using BFS Topological Sort


  • 40
    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);
                        }
    
                        if(map.get(seq[i]).add(seq[i + 1])) {
                            indegree.put(seq[i + 1], indegree.get(seq[i + 1]) + 1);
                        }
                    }
                }
            }
    
            Queue<Integer> queue = new LinkedList<>();
            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();
        }
    }
    

  • 0
    W

    A nice solution!


  • 10
    L

    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>());
                        graph.get(prev).add(next);
                    }
                }
            }
            // topological sort
            Queue<Integer> queue = new LinkedList<>();
            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
        }
    }
    

  • 1
    P

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


  • 14

    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) {
                    graph.get(seq[i - 1]).add(seq[i]);
                    indegree.put(seq[i], indegree.get(seq[i]) + 1);
                }
            }
        }
        if (org.length != indegree.size()) {
            return false;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for (Map.Entry<Integer, Integer> entry : indegree.entrySet()) {
            if (entry.getValue() == 0) {
                q.add(entry.getKey());
            }
        }
        
        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) {
                    q.add(nb);
                }
            }
        }
        return index == org.length;
    }

  • 3
    S

    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++)
                if (map.get(seq[i - 1]).add(seq[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()) 
            if (indegree.get(key) == 0) q.add(key);
    		
        int cnt = 0;
        while (q.size() == 1) {
            for (int next : map.get(q.poll())) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) q.add(next);
            }
            cnt++;
        }
    		
        return cnt == indegree.size();
    }
    

  • 0
    A

    Some explanation would be helpful.


  • 0

    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?


  • 0

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


  • 3

    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]++; 
                        map.get(pre).add(cur);
                    }
                }
            }
            
            Queue<Integer> q = new LinkedList<>();
            for(int i = 0; i<degree.length; i++){
                if(degree[i]==0) q.add(i+1);
            }
            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]--; 
                    if(degree[ii-1]==0) q.add(ii); 
                }
            }
            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.


  • 1
    C

    @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);
               if (indegree.get(next) == 0) q.add(next);
            }
            cnt++;
        }
    

  • 1
    Z

    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;
        }
    };
    

  • 0
    L

    @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++) {
                graph.add(new ArrayList<>());
            }
            
            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)) {
                        graph.get(u).add(v);
                        if(indegree[v] == -1) indegree[v] = 0;
                        indegree[v]++;
                    }
                }
            }
            
            if(empty) return false;//for [1], [[], []]
            
            Queue<Integer> q = new LinkedList<>();
            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();
                
                for(int adj : graph.get(cur)) {
                    indegree[adj]--;
                    
                    if(indegree[adj] == 0) {
                        count++;
                        q.offer(adj);
                    }
                }
            }
            
            return count == n;
        }
    }
    

Log in to reply
 

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