444. Sequence Reconstruction

 一刷 05/2022

Version #1 Topological Sort

Time O(#nums)

Space O(#nums^2)

class Solution {

    public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {

        Map<Integer, Set<Integer>> graph = new HashMap<>();

        Map<Integer, Integer> indegree = new HashMap<>();

        for (int num : nums) {

            graph.put(num, new HashSet<>());

            indegree.put(num, 0);

        }

        for (List<Integer> sequence : sequences) {

            Integer from = null, to = null;

            for (Integer n : sequence) {

                if (from == null) {

                    from = n;

                    continue;

                }

                to = n;

                Set<Integer> neighbors = graph.get(from);

                if (!neighbors.contains(to)) {

                    neighbors.add(to);

                    indegree.put(to, indegree.get(to) + 1);

                }

                from = n;

            }

        }

        // for (Map.Entry<Integer, Set<Integer>> entry : graph.entrySet()) {

        //     System.out.printf("key-%d, set-%s\n", entry.getKey(), entry.getValue());

        // }

        Queue<Integer> que = new ArrayDeque<>();

        for (Map.Entry<Integer,Integer> entry : indegree.entrySet()) {

            if (entry.getValue() == 0) {

                que.offer(entry.getKey());

            }

        }

        int index = 0;

        while (!que.isEmpty()) {

            if (que.size() > 1) {

                return false;

            }

            Integer curr = que.poll();

            // System.out.println(curr);

            if (curr != nums[index++]) {

                return false;

            }

            for (Integer neighbor : graph.get(curr)) {

                int id = indegree.get(neighbor);

                id -= 1;

                if (id == 0) {

                    que.offer(neighbor);

                }

                indegree.put(neighbor, id);

            }

        }

        return true;

    }

}