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


  • 0
    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;
                        graph.get(s[i]).add(s[i + 1]);
                        inDegree[s[i + 1]]++;
                    }
                }
            }
            
            // bfs
            Queue<Integer> q = new ArrayDeque();
            for (int i = 1; i < inDegree.length; i++) {
                if (inDegree[i] == 0) q.add(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;
        }
    }
    

Log in to reply
 

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