class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n <= 2) {
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                result.add(i);
            }
            return result;
        }
        // Record each node's neighbors.
        Map<Integer, Set<Integer>> nodeNeighbors = new HashMap<>();
        for (int[] edge : edges) {
            int nodeOne = edge[0], nodeTwo = edge[1];
            if (!nodeNeighbors.containsKey(nodeOne)) {
                nodeNeighbors.put(nodeOne, new HashSet<>());
            }
            nodeNeighbors.get(nodeOne).add(nodeTwo);

            if (!nodeNeighbors.containsKey(nodeTwo)) {
                nodeNeighbors.put(nodeTwo, new HashSet<>());
            }
            nodeNeighbors.get(nodeTwo).add(nodeOne);
        }

        // Find leaf nodes.
        Queue<Integer> nodeQueue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (nodeNeighbors.get(i).size() == 1)
                nodeQueue.offer(i);
        }

        int remainingNodes = n;
        while (remainingNodes > 2) {
            int length = nodeQueue.size();
            for (int i = 0; i < length; i++) {
                int currNode = nodeQueue.poll();
                int neighbor = nodeNeighbors.get(currNode).iterator().next();
                nodeNeighbors.get(neighbor).remove(currNode);
                if (nodeNeighbors.get(neighbor).size() == 1)
                    nodeQueue.add(neighbor);
                remainingNodes -= 1;
                nodeNeighbors.remove(currNode);
            }
        }
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Set<Integer>> entry : nodeNeighbors.entrySet()) {
            result.add(entry.getKey());
        }
        return result;
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int longest = 0;
        for (int length : dp) {
            longest = Math.max(longest, length);
        }
        return longest;
    }
}

class Solution {
    public int findDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[Math.abs(nums[i])] < 0) {
                return Math.abs(nums[i]);
            }
            nums[Math.abs(nums[i])] *= -1;
        }
        return -1;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int pos = 0, count = 0;
        while (pos < nums.length - count) {
            if (nums[pos] == 0) {
                for (int i = pos; i < nums.length - 1 - count; i++) {
                    swap(nums, i, i + 1);
                }
                count += 1;
            } else {
                pos += 1;
            }
        }
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

class Solution {
    public int missingNumber(int[] nums) {
        int ans = nums.length;
        for (int i = 0; i < nums.length; i++) {
            ans ^= i;
            ans ^= nums[i];
        }
        return ans;
    }
}

class Solution {
    private int count = 0;

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1)
            return false;
        if (edges.length == 0)
            return true;
        Map<Integer, List<Integer>> nodeMap = new HashMap<>();
        boolean[] visited = new boolean[n];
        for (int[] edge : edges) {
            nodeMap.putIfAbsent(edge[0], new ArrayList<>());
            nodeMap.get(edge[0]).add(edge[1]);
            nodeMap.putIfAbsent(edge[1], new ArrayList<>());
            nodeMap.get(edge[1]).add(edge[0]);
        }
        return helper(nodeMap, visited, edges[0][0], edges[0][0]) && count == n;
    }

    private boolean helper(Map<Integer, List<Integer>> nodeMap, boolean[] visited, int currNode, int prevNode) {
        if (visited[currNode])
            return false;
        visited[currNode] = true;
        count += 1;
        for (Integer node : nodeMap.get(currNode)) {
            if (node != prevNode && !helper(nodeMap, visited, node, currNode))
                return false;
        }
        return true;
    }
}

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1])
                return false;
        }
        return true;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null;
        ListNode curr = slow;

        // Reverse the right half list.
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // Two pointers. One from the left, the other from the right.
        ListNode left = head;
        ListNode right = prev;
        while (right != null) {
            if (left.val != right.val)
                return false;
            left = left.next;
            right = right.next;
        }
        return true;
    }
}

class WordDictionary {
    static class TrieNode {
        boolean isWord;
        Map<Character, TrieNode> map;

        TrieNode() {
            map = new HashMap<>();
        }
    }

    TrieNode trie;

    public WordDictionary() {
        trie = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode currNode = trie;
        for (int i = 0; i < word.length(); i++) {
            char currChar = word.charAt(i);
            if (!currNode.map.containsKey(currChar)) {
                currNode.map.put(currChar, new TrieNode());
            }
            currNode = currNode.map.get(currChar);
        }
        currNode.isWord = true;
    }

    public boolean search(String word) {
        return searchFrom(word, 0, trie);
    }

    public boolean searchFrom(String word, int k, TrieNode node) {
        // All the chars before word.length() are found.
        // Therefore we need to check at this point, if there is word
        // that contains all the chars before has been inserted before.
        if (k == word.length())
            return node.isWord;
        char currChar = word.charAt(k);
        if (word.charAt(k) == '.') {
            for (TrieNode child : node.map.values()) {
                if (searchFrom(word, k + 1, child))
                    return true;
            }
        } else {
            return node.map.containsKey(currChar) && searchFrom(word, k + 1, node.map.get(currChar));
        }
        return false;
    }
}

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> courseDependentMap = new HashMap<>();
        Map<Integer, Integer> preCount = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        int pos = 0;
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            preCount.put(i, 0);
        }
        for (int[] prerequisite : prerequisites) {
            courseDependentMap.putIfAbsent(prerequisite[1], new ArrayList<>());
            courseDependentMap.get(prerequisite[1]).add(prerequisite[0]);
            preCount.put(prerequisite[0], preCount.get(prerequisite[0]) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : preCount.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        while (!queue.isEmpty()) {
            int currCourse = queue.poll();
            result[pos] = currCourse;
            pos += 1;
            if (courseDependentMap.containsKey(currCourse)) {
                for (Integer dependent : courseDependentMap.get(currCourse)) {
                    preCount.put(dependent, preCount.get(dependent) - 1);
                    if (preCount.get(dependent) == 0) {
                        queue.offer(dependent);
                    }
                }
                courseDependentMap.remove(currCourse);
            }
        }
        return courseDependentMap.isEmpty() ? result : new int[0];
    }
}