class Solution {
    private Map<Integer, Set<Integer>> rowMap;
    private Map<Integer, Set<Integer>> colMap;
    private Map<Integer, Set<Integer>> blockMap;

    public void solveSudoku(char[][] board) {
        rowMap = new HashMap<>();
        colMap = new HashMap<>();
        blockMap = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            rowMap.put(i, new HashSet<>());
            colMap.put(i, new HashSet<>());
            blockMap.put(i, new HashSet<>());
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    updateMaps(i, j, Character.getNumericValue(board[i][j]), true);
                }
            }
        }
        helper(board, 0, 0);
    }

    private boolean helper(char[][] board, int row, int col) {
        if (col == 9) {
            row += 1;
            if (row == 9) {
                return true;
            }
            col = 0;
        }
        if (board[row][col] != '.') {
            return helper(board, row, col + 1);
        } else {
            for (int i = 1; i <= 9; i++) {
                if (isValid(row, col, i)) {
                    board[row][col] = (char) (i + '0');
                    updateMaps(row, col, i, true);
                    if (helper(board, row, col + 1)) {
                        return true;
                    }
                    updateMaps(row, col, Character.getNumericValue(board[row][col]), false);
                }
            }
            board[row][col] = '.';
            // updateMaps(row, col, Character.getNumericValue(board[row][col]), false);
            return false;
        }
    }

    private void updateMaps(int row, int col, int num, boolean isAdd) {
        int blockNum = (row / 3) * 3 + col / 3;
        if (isAdd) {
            rowMap.get(row).add(num);
            colMap.get(col).add(num);
            blockMap.get(blockNum).add(num);
        } else {
            rowMap.get(row).remove(num);
            colMap.get(col).remove(num);
            blockMap.get(blockNum).remove(num);
        }
    }

    private boolean isValid(int row, int col, int num) {
        int blockNum = (row / 3) * 3 + col / 3;
        return !rowMap.get(row).contains(num) && !colMap.get(col).contains(num)
                && !blockMap.get(blockNum).contains(num);
    }
}

class Solution {
    public int divide(int dividend, int divisor) {
        boolean positive = (dividend > 0) == (divisor > 0) ? true : false;
        long dividendLong = Math.abs((long) dividend), divisorLong = Math.abs((long) divisor), ans = 0;
        while (dividendLong >= divisorLong) {
            long currDivisor = divisorLong;
            long currQuoient = 1;
            while (dividendLong >= currDivisor) {
                ans += currQuoient;
                dividendLong -= currDivisor;
                currDivisor <<= 1;
                currQuoient <<= 1;
            }
        }
        ans = positive ? ans : -ans;
        return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;

    }
}

class Solution {
    private Set<Integer> rowsWithQueen = new HashSet<>();
    private Set<Integer> colsWithQueen = new HashSet<>();
    private Set<Integer> diagWithQueen = new HashSet<>();
    private Set<Integer> antiWithQueen = new HashSet<>();
    private List<List<String>> ans = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backtrack(board, 0);
        return ans;
    }

    private void backtrack(char[][] board, int row) {
        if (row == board.length) {
            ans.add(createBoard(board));
            return;
        }
        for (int i = 0; i < board.length; i++) {
            if (isValidPosition(row, i)) {
                addQueen(row, i);
                board[row][i] = 'Q';
                backtrack(board, row + 1);
                board[row][i] = '.';
                removeQueen(row, i);
            }
        }
    }

    private boolean isValidPosition(int row, int col) {
        return !rowsWithQueen.contains(row) && !colsWithQueen.contains(col) && !diagWithQueen.contains(row - col)
                && !antiWithQueen.contains(row + col);
    }

    private void addQueen(int row, int col) {
        rowsWithQueen.add(row);
        colsWithQueen.add(col);
        diagWithQueen.add(row - col);
        antiWithQueen.add(row + col);
    }

    private void removeQueen(int row, int col) {
        rowsWithQueen.remove(row);
        colsWithQueen.remove(col);
        diagWithQueen.remove(row - col);
        antiWithQueen.remove(row + col);
    }

    private List<String> createBoard(char[][] board) {
        List<String> newBoard = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            String currRow = new String(board[i]);
            newBoard.add(currRow);
        }
        return newBoard;
    }
}

class Solution {
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
    Set<TreeNode> visited = new HashSet<>();
    TreeNode startNode, endNode;

    public String getDirections(TreeNode root, int startValue, int destValue) {
        recordParents(root, new TreeNode(0), startValue, destValue);
        StringBuilder ans = new StringBuilder();
        findPath(startNode, ans);
        return ans.toString();
    }

    private void recordParents(TreeNode node, TreeNode parent, int startValue, int endValue) {
        if (node == null) {
            return;
        }
        if (node.val == startValue) {
            startNode = node;
        } else if (node.val == endValue) {
            endNode = node;
        }
        parentMap.put(node, parent);
        recordParents(node.left, node, startValue, endValue);
        recordParents(node.right, node, startValue, endValue);
    }

    private boolean findPath(TreeNode node, StringBuilder sb) {
        if (node == null || visited.contains(node)) {
            return false;
        }
        // Found the end node
        if (node == endNode) {
            return true;
        }

        visited.add(node);
        // Find left
        sb.append('L');
        boolean foundEndNode = findPath(node.left, sb);
        if (foundEndNode) {
            return true;
        }
        sb.deleteCharAt(sb.length() - 1);

        // Find right
        sb.append('R');
        foundEndNode = findPath(node.right, sb);
        if (foundEndNode) {
            return true;
        }
        sb.deleteCharAt(sb.length() - 1);

        // Find parent
        sb.append('U');
        foundEndNode = findPath(parentMap.get(node), sb);
        if (foundEndNode) {
            return true;
        } else {
            sb.deleteCharAt(sb.length() - 1);
            visited.remove(node);
            return false;
        }

    }

}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] ans = new int[nums.length];
        for (int pos = ans.length - 1; pos >= 0; pos--) {
            ans[pos] = Math.abs(nums[left]) >= Math.abs(nums[right]) ? nums[left] * nums[left++]
                    : nums[right]
                            * nums[right--];
        }
        return ans;
    }
}

class Solution {
    public boolean backspaceCompare(String s, String t) {
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '#' && s1.length() > 0) {
                s1.deleteCharAt(s1.length() - 1);
            } else if (s.charAt(i) != '#') {
                s1.append(s.charAt(i));
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == '#' && s2.length() > 0) {
                s2.deleteCharAt(s2.length() - 1);
            } else if (t.charAt(i) != '#') {
                s2.append(t.charAt(i));
            }
        }
        return s1.toString().equals(s2.toString());
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        if (temperatures.length == 1)
            return new int[1];
        int[] ans = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                ans[index] = i - index;
            }
            stack.push(i);
        }
        return ans;
    }
}

/**
 * 不推荐创建一个Node class然后里面装email和children. 因为需要让同一个邮箱不重复创建node.
 * 比如遇到一个node是邮箱A, 我们创建一个node, 我们之后如果再次遇到相同的邮箱, 如何避免重复创建
 * 一个node呢? 需要一个map存email和node的映射. 那还不如存emai到该email children的映射. 一个
 * entry就表示一个node.
 */
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        if (accounts == null || accounts.size() == 0)
            return new ArrayList<>();
        Map<String, Set<String>> emailNeighbors = new HashMap<>();
        Map<String, String> emailNamePairs = new HashMap<>();
        Set<String> emails = new HashSet<>();
        List<List<String>> result = new ArrayList<>();
        for (List<String> account : accounts) {
            String name = account.get(0);
            emails.add(account.get(1));
            emailNamePairs.put(account.get(1), name);
            emailNeighbors.putIfAbsent(account.get(1), new HashSet<>());
            for (int i = 2; i < account.size(); i++) {
                emailNeighbors.putIfAbsent(account.get(i), new HashSet<>());
                emailNeighbors.get(account.get(i)).add(account.get(i - 1));
                emailNeighbors.get(account.get(i - 1)).add(account.get(i));
            }
        }

        Set<String> visited = new HashSet<>();
        for (String email : emails) {
            if (!visited.contains(email)) {
                List<String> list = new ArrayList<>();
                helper(email, list, emailNeighbors, visited);
                Collections.sort(list);
                list.add(0, emailNamePairs.get(email));
                result.add(list);
            }
        }
        return result;
    }

    private void helper(String email, List<String> result, Map<String, Set<String>> neighbors, Set<String> visited) {
        result.add(email);
        visited.add(email);
        Set<String> emailNeighbors = neighbors.get(email);
        for (String neighbor : emailNeighbors) {
            if (!visited.contains(neighbor)) {
                helper(neighbor, result, neighbors, visited);
            }
        }
    }
}

class Solution {
    static class Node {
        String word;
        int count;

        Node(String word, int count) {
            this.word = word;
            this.count = count;
        }
    }

    static class MyComparator implements Comparator<Node> {
        public int compare(Node nodeOne, Node nodeTwo) {
            int freqOne = nodeOne.count, freqTwo = nodeTwo.count;
            if (freqOne != freqTwo) {
                return freqTwo - freqOne;
            }
            return nodeOne.word.compareTo(nodeTwo.word);
        }

        public int compare(Node one, Node two) {
            return two.word.compareTo(one.word);
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Node> map = new HashMap<>();
        for (String word : words) {
            map.putIfAbsent(word, new Node(word, 0));
            map.get(word).count += 1;
        }

        Node[] nodeArray = new Node[map.size()];
        int pos = 0;
        for (Node node : map.values()) {
            nodeArray[pos] = node;
            pos += 1;
        }

        quickSelect(nodeArray, 0, nodeArray.length - 1, k);
        List<Node> candidates = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            candidates.add(nodeArray[i]);
        }
        Collections.sort(candidates, new MyComparator());
        List<String> ans = new ArrayList<>();
        for (Node node : candidates) {
            ans.add(node.word);
        }
        return ans;
    }

    public void quickSelect(Node[] nodeArray, int low, int up, int k) {
        int pivot = low, left = low + 1, right = up;
        MyComparator comparator = new MyComparator();
        while (left <= right) {
            if (comparator.compare(nodeArray[left], nodeArray[pivot]) > 0 &&
                    comparator.compare(nodeArray[right], nodeArray[pivot]) < 0) {
                swap(nodeArray, left, right);
                left += 1;
                right -= 1;
                continue;
            }
            if (comparator.compare(nodeArray[left], nodeArray[pivot]) <= 0) {
                left += 1;
            }
            if (comparator.compare(nodeArray[right], nodeArray[pivot]) >= 0) {
                right -= 1;
            }
        }
        swap(nodeArray, pivot, right);
        if (right == k - 1) {
            return;
        } else if (right < k - 1) {
            quickSelect(nodeArray, right + 1, up, k);
        } else {
            quickSelect(nodeArray, low, right - 1, k);
        }
    }

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

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] taskCount = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            taskCount[tasks[i] - 'A'] += 1;
        }
        Arrays.sort(taskCount);
        int gaps = (taskCount[taskCount.length - 1] - 1) * n;
        for (int i = taskCount.length - 2; i >= 0 && gaps > 0; i--) {
            gaps -= Math.min(taskCount[taskCount.length - 1] - 1, taskCount[i]);
        }
        return gaps <= 0 ? tasks.length : gaps + tasks.length;
    }
}