class Solution {
    private StringBuilder ans;

    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        ans = new StringBuilder();
        helper(root);
        return ans.toString();
    }

    private void helper(TreeNode node) {
        if (node == null) {
            return;
        }
        ans.append(node.val);
        if (node.left == null && node.right == null) {
            return;
        }
        ans.append('(');
        helper(node.left);
        ans.append(')');
        if (node.right != null) {
            ans.append('(');
            helper(node.right);
            ans.append(')');
        }
    }
}

class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        Node senital = new Node();
        helper(senital, head);
        head.prev = null;
        return head;
    }

    private Node helper(Node prevNode, Node currNode) {
        if (currNode == null) {
            return prevNode;
        }
        prevNode.next = currNode;
        currNode.prev = prevNode;
        prevNode = currNode;
        Node nextNode = currNode.next;
        if (currNode.child != null) {
            prevNode = helper(prevNode, currNode.child);
            currNode.child = null;
        }
        return helper(prevNode, nextNode);
    }
}

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() > t.length()) {
            return false;
        }
        int ptrOne = 0, ptrTwo = 0;
        while (ptrOne < s.length() && ptrTwo < t.length()) {
            if (s.charAt(ptrOne) == t.charAt(ptrTwo)) {
                ptrOne += 1;
            }
            ptrTwo += 1;
        }
        return ptrOne == s.length();
    }
}

class Solution {
    public String removeDuplicateLetters(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        char[] sArray = s.toCharArray();
        int[] lastIdx = new int[26];
        for (int i = 0; i < sArray.length; i++) {
            char currChar = sArray[i];
            lastIdx[currChar - 'a'] = i;
        }
        boolean[] visited = new boolean[26];
        for (int i = 0; i < sArray.length; i++) {
            if (visited[sArray[i] - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && sArray[i] < stack.peek() && lastIdx[stack.peek() - 'a'] > i) {
                visited[stack.pop() - 'a'] = false;
            }
            stack.push(sArray[i]);
            visited[sArray[i] - 'a'] = true;
        }
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.append(stack.pollLast());
        }
        return ans.toString();
    }
}

class WordDistance {
    private Map<String, List<Integer>> stringIdx;

    public WordDistance(String[] wordsDict) {
        stringIdx = new HashMap<>();
        for (int i = 0; i < wordsDict.length; i++) {
            stringIdx.putIfAbsent(wordsDict[i], new ArrayList<>());
            stringIdx.get(wordsDict[i]).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> word1List = stringIdx.get(word1);
        List<Integer> word2List = stringIdx.get(word2);
        int ptrOne = 0, ptrTwo = 0, ans = Integer.MAX_VALUE;
        while (ptrOne < word1List.size() && ptrTwo < word2List.size()) {
            int currDiff = Math.abs(word1List.get(ptrOne) - word2List.get(ptrTwo));
            ans = Math.min(ans, currDiff);
            if (word1List.get(ptrOne) < word2List.get(ptrTwo)) {
                ptrOne += 1;
            } else {
                ptrTwo += 1;
            }
        }
        return ans;
    }
}

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        Map<Integer, Set<Integer>> nodeChildrenMap = new HashMap<>();
        for (int[] edge : edges) {
            nodeChildrenMap.putIfAbsent(edge[0], new HashSet<>());
            nodeChildrenMap.get(edge[0]).add(edge[1]);
            nodeChildrenMap.putIfAbsent(edge[1], new HashSet<>());
            nodeChildrenMap.get(edge[1]).add(edge[0]);
        }
        return dfs(source, destination, nodeChildrenMap, new HashSet<>());
    }

    private boolean dfs(int curr, int dest, Map<Integer, Set<Integer>> nodeChildrenMap, Set<Integer> visited) {
        if (curr == dest) {
            return true;
        }
        visited.add(curr);
        for (int child : nodeChildrenMap.get(curr)) {
            if (!visited.contains(child) && dfs(child, dest, nodeChildrenMap, visited)) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        boolean containsOne = helper(root);
        return containsOne ? root : null;
    }

    private boolean helper(TreeNode node) {
        if (node == null) {
            return true;
        }
        if (!helper(node.left)) {
            node.left = null;
        }
        if (!helper(node.right)) {
            node.right = null;
        }
        return node.left != null || node.right != null || node.val == 1;
    }
}

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        Map<Integer, Set<Integer>> nodeChildMap = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            nodeChildMap.putIfAbsent(i, new HashSet<>());
            Set<Integer> children = nodeChildMap.get(i);
            for (int child : graph[i]) {
                children.add(child);
            }
        }
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(ans, new ArrayDeque<>(), new HashSet<>(), nodeChildMap, 0, graph.length);
        return ans;
    }

    private void backtrack(List<List<Integer>> ans, Deque<Integer> currList, Set<Integer> visited,
            Map<Integer, Set<Integer>> nodeChildMap, int currNode, int n) {
        visited.add(currNode);
        currList.offerLast(currNode);
        if (currNode == n - 1) {
            ans.add(new ArrayList<>(currList));
        } else {
            for (int child : nodeChildMap.get(currNode)) {
                backtrack(ans, currList, visited, nodeChildMap, child, n);
            }
        }
        currList.pollLast(currList.size() - 1);
        visited.remove(currNode);
    }
}

class Solution {
    public int countPrimes(int n) {
        int[] numbers = new int[n];
        int upperBound = (int) Math.sqrt(n);
        for (int i = 2; i <= upperBound; i++) {
            if (numbers[i] == -1) {
                continue;
            }
            for (int j = i; i * j < n; j++) {
                numbers[i * j] = -1;
            }
        }
        int count = 0;
        for (int i = 2; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                count += 1;
            }
        }
        return count;
    }
}

class Solution {
    Map<Integer, ArrayList<Pair<Integer, Integer>>> columnTable = new HashMap();
    int minColumn = 0, maxColumn = 0;

    private void DFS(TreeNode node, Integer row, Integer column) {
        if (node == null)
            return;

        if (!columnTable.containsKey(column)) {
            this.columnTable.put(column, new ArrayList<Pair<Integer, Integer>>());
        }

        this.columnTable.get(column).add(new Pair<Integer, Integer>(row, node.val));
        this.minColumn = Math.min(minColumn, column);
        this.maxColumn = Math.max(maxColumn, column);
        // preorder DFS traversal
        this.DFS(node.left, row + 1, column - 1);
        this.DFS(node.right, row + 1, column + 1);
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> output = new ArrayList();
        if (root == null) {
            return output;
        }

        this.DFS(root, 0, 0);

        // Retrieve the resuts, by ordering by column and sorting by row
        for (int i = minColumn; i < maxColumn + 1; ++i) {
            Collections.sort(columnTable.get(i),
                    (p1, p2) -> p1.getKey() != p2.getKey() ? p1.getKey() - p2.getKey() : p1.getValue() - p2.getValue());
            List<Integer> sortedColumn = new ArrayList();
            for (Pair<Integer, Integer> p : columnTable.get(i)) {
                sortedColumn.add(p.getValue());
            }
            output.add(sortedColumn);
        }

        return output;
    }
}