Sequence Reconstruction - Lintcode

Check whether the original sequenceorgcan be uniquely reconstructed from the sequences inseq. 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 inseqs(i.e., a shortest sequence so that all sequences inseqsare subsequences of it). Determine whether there is only one sequence that can be reconstructed fromseqsand it is theorgsequence.

Example

Given org = [1,2,3], seqs = [[1,2],[1,3]]
Return 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.

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

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

Given org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Return true

Analysis

This is basically a directed graph with one valid path. First to calculate the incoming degrees of each node and its outgoing edges using seqs. The node with incoming degree equals to 0 is supposed to be the starting point. Each node reached using the outgoing edges will have its degree decremented by 1. * The starting node will navigate to the only node with its incoming degree becomes 0. Any violation from the constraints indicates that the seqs are able to build more than one path. Special case needs to be taken care such as ([], [[]]) and ([],[]) . Any circular dependency will make * condition failed. For each navigation, the comparasion should be made to org to check the correct sequence was formed. Finally, since the org sequence is permutation of the integer from 1 to n, counting the number of the navigation is a good indicator that the right number of the nodes in path was formed.

public boolean sequenceReconstruction(int[] org, int[][] seqs) {
    if (org.length == 0 && (seqs.length == 0 || seqs[0].length == 0)) {
        return true;
    }

    if (org.length == 0 || seqs.length == 0 || seqs[0].length == 0) {
        return false;
    }

    int max = Integer.MIN_VALUE;
    for (int i = 0; i < org.length; i++) {
        max = Math.max(max, org[i]);
    }

    int[] incomingDegrees = new int[max + 1];
    List[] edges = new ArrayList[max + 1];

    for (int i = 0; i < max + 1; i++) {
        edges[i] = new ArrayList<Integer>();
    }

    // initialize degrees and edges
    for (int i = 0; i < seqs.length; i++) {            
        if (org.length > 1 && seqs[i].length == 1){
            return false;
        }

        for (int j = 1; j < seqs[i].length; j++) {
            if (seqs[i][j] > max) {
                return false;
            }
            incomingDegrees[seqs[i][j]]++;
            edges[seqs[i][j - 1]].add(seqs[i][j]);
        }
    }

    Queue<Integer> queue = new LinkedList<Integer>();
    for (int i = 1; i < incomingDegrees.length; i++) {
        if (incomingDegrees[i] == 0) {
            queue.offer(i);
        }
    }

    int length = 0;
    while (queue.size() == 1) {
        int nodeIndex = queue.poll();

        for (int i = 0; i < edges[nodeIndex].size(); i++) {
            int lNodeIndex = (int) edges[nodeIndex].get(i);
            incomingDegrees[lNodeIndex]--;
            if (incomingDegrees[lNodeIndex] == 0) {
                queue.offer(lNodeIndex);                    
            }
        }

        length++;
    }

    return length == org.length;
}