Lintcode 605. Sequence Reconstruction

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^4. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Example

Example 1:

Input:org = [1,2,3], seqs = [[1,2],[1,3]]
Output: false
Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Example 2:

Input: org = [1,2,3], seqs = [[1,2]]
Output: false
Explanation:
The reconstructed sequence can only be [1,2].

Example 3:

Input: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Output: true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Example 4:

Input:org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Output:true

Code (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) {
        // write your code here
        if (org == null || org.length == 0) {
            if(seqs == null || seqs.length == 0) {
                return true;
            }
            
            for (int[] seq : seqs) {
                if (seq != null && seq.length != 0) {
                    return false;
                }
            }
            
            return true;
        }
        if (seqs == null || seqs.length == 0) {
            return false;
        }
        for (int[] seq : seqs) {
            if (seq.length == 0) {
                return false;
            }
        }
        
        int numNodes = org.length;
        
        // step 1: build graph
        //
        Map<Integer, Set<Integer>> graph  = new HashMap<>();
        boolean validGraph = buildGraph(numNodes, seqs, graph);
        if (!validGraph) {
            return false;
        }
        
        
        // step 2: topological sorting
        //
        int[] ans = new int[numNodes];
        boolean isValid = toplogicalSorting(graph, ans);
        if (!isValid) {
            return false;
        }
        
        for (int i = 0; i < numNodes; i++) {
            if (org[i] != ans[i]) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean buildGraph(int numNodes, int[][] seqs, Map<Integer, Set<Integer>> adjList) {
        // create nodes
        //
        for (int i = 1; i <= numNodes; i++) {
            adjList.put(i, new HashSet<>());
        }
        
        // create edges
        //
        for (int[] seq : seqs) {
            for (int j = 0; j < seq.length; j++) {
                if (seq[j] <= 0 || seq[j] > numNodes) {
                    return false;
                }
                if (j != seq.length - 1) {
                    adjList.get(seq[j]).add(seq[j + 1]);
                }
            }
        }
        
        return true;
    }
    
    private boolean toplogicalSorting(Map<Integer, Set<Integer>> adjList, int[] ans) {
        int index = 0;
        // step 1: create indegree Map
        //
        Map<Integer, Integer> indegreeMap = new HashMap<>();
        int numNodes = ans.length;
        for (int i = 1; i <= numNodes; i++) {
            indegreeMap.put(i, 0);
        }
        
        for (int node : adjList.keySet()) {
            for (int neighbor : adjList.get(node)) {
                int indegree = indegreeMap.get(neighbor);
                indegree += 1;
                indegreeMap.put(neighbor, indegree);
            }
        }
        
        // step 2: get all nodes with 0 indegree
        //
        Queue<Integer> queue = new LinkedList<>();
        for (int node : indegreeMap.keySet()) {
            if (indegreeMap.get(node) == 0) {
                queue.offer(node);
            }
            
            if (queue.size() > 1) {
                return false;
            }
        }
        
        // step 3: poll all nodes from the queue, remove the indegree by 1 for the neighbors
        //
        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            ans[index++] = curNode;
            
            for (int neighbor : adjList.get(curNode)) {
                int indegree = indegreeMap.get(neighbor) - 1;
                indegreeMap.put(neighbor, indegree);
                if (indegree == 0) {
                    queue.offer(neighbor);
                }
            }
            
            if (queue.size() > 1) {
                return false;
            }
        }
        
        return index == numNodes;
    }
}