class Solution {
    public int treeDiameter(int[][] edges) {
        if (edges.length == 0) {
            return 0;
        }
        Map<Integer, Set<Integer>> nodeChildren = new HashMap<>();
        for (int[] edge : edges) {
            nodeChildren.putIfAbsent(edge[0], new HashSet<>());
            nodeChildren.get(edge[0]).add(edge[1]);
            nodeChildren.putIfAbsent(edge[1], new HashSet<>());
            nodeChildren.get(edge[1]).add(edge[0]);
        }
        Deque<Integer> freeNodes = new ArrayDeque<>();
        for (Map.Entry<Integer, Set<Integer>> entry : nodeChildren.entrySet()) {
            if (entry.getValue().size() == 1) {
                freeNodes.add(entry.getKey());
            }
        }
        int count = 0;
        int lastTimeRemaining = 0;
        while (!freeNodes.isEmpty()) {
            int size = freeNodes.size();
            for (int i = 0; i < size; i++) {
                int currNode = freeNodes.pollFirst();
                Set<Integer> children = nodeChildren.get(currNode);
                for (Integer child : children) {
                    nodeChildren.get(child).remove(currNode);
                    if (nodeChildren.get(child).size() == 1) {
                        freeNodes.offerLast(child);
                    }
                }
            }
            lastTimeRemaining = size;
            count += 1;
        }
        return lastTimeRemaining == 1 ? 2 * count - 2 : 2 * count - 1;
    }
}

/**
 * topological sort.
 * 
 * count数的是一共减了几圈. 我们需要统计最后一圈去掉了几个nodes. 如果去掉了两个, 那么最长的chain就是圈数 * 2, 如果最后只去掉了一个
 * 那就是(圈数 - 1) * 2 + 1.
 * 
 * 除了最后一圈, 每一圈一定是去掉2个极其以上的nodes的.
 * 
 * 时间复杂度: O(n)
 * 空间复杂度: O(n) 用了map以及queue.
 */

class Solution {
    private int ans = 0;

    public int treeDiameter(int[][] edges) {
        if (edges.length == 0) {
            return 0;
        }
        Map<Integer, Set<Integer>> nodeChildren = new HashMap<>();
        for (int[] edge : edges) {
            nodeChildren.putIfAbsent(edge[0], new HashSet<>());
            nodeChildren.get(edge[0]).add(edge[1]);
            nodeChildren.putIfAbsent(edge[1], new HashSet<>());
            nodeChildren.get(edge[1]).add(edge[0]);
        }
        getHeight(edges[0][0], -1, nodeChildren);
        return ans;
    }

    private int getHeight(int node, int parent, Map<Integer, Set<Integer>> nodeChildren) {
        int maxHeight = 0;
        for (int child : nodeChildren.get(node)) {
            if (child == parent) {
                continue;
            }
            int currHeight = getHeight(child, node, nodeChildren);
            ans = Math.max(ans, currHeight + maxHeight);
            maxHeight = Math.max(maxHeight, currHeight);
        }
        return maxHeight + 1;
    }
}

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                matrix[i][j] += matrix[i][j - 1];
            }
        }
        int ans = 0;
        Map<Integer, Integer> sumCount = new HashMap<>();
        // i determines the start row
        // j determines the width
        // k determines the height
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                sumCount.clear();
                int currSum = 0;
                for (int k = 0; k < m; k++) {
                    currSum += matrix[k][j] - (i > 0 ? matrix[k][i - 1] : 0);
                    if (currSum == target) {
                        ans += 1;
                    }
                    int counterPart = currSum - target;
                    ans += sumCount.getOrDefault(counterPart, 0);
                    sumCount.put(currSum, sumCount.getOrDefault(currSum, 0) + 1);
                }
            }
        }
        return ans;
    }
}

class Solution {
    private final int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public int numDistinctIslands(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Set<String> paths = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    StringBuilder sb = new StringBuilder();
                    getPath(grid, i, j, sb);
                    paths.add(sb.toString());
                }
            }
        }
        return paths.size();

    }

    private void getPath(int[][] grid, int row, int col, StringBuilder sb) {
        grid[row][col] = 0;
        for (int i = 0; i < DIRECTIONS.length; i++) {
            int newRow = row + DIRECTIONS[i][0];
            int newCol = col + DIRECTIONS[i][1];
            if (!isOutOfBound(grid.length, grid[0].length, newRow, newCol) && grid[newRow][newCol] == 1) {
                sb.append(i);
                getPath(grid, newRow, newCol, sb);
            }
        }
        sb.append('0');
    }

    private boolean isOutOfBound(int m, int n, int row, int col) {
        return row < 0 || row >= m || col < 0 || col >= n;
    }
}

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> sumPairCount = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                sumPairCount.put(nums1[i] + nums2[j], sumPairCount.getOrDefault(nums1[i] + nums2[j], 0) + 1);
            }
        }
        int ans = 0;
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                ans += sumPairCount.getOrDefault(-(nums3[i] + nums4[j]), 0);
            }
        }
        return ans;
    }
}

class Solution {
    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxSum(root);
        return max;
    }

    private int maxSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftTreeMaxSum = Math.max(maxSum(node.left), 0);
        int rightTreeMaxSum = Math.max(maxSum(node.right), 0);
        max = Math.max(max, node.val + leftTreeMaxSum + rightTreeMaxSum);
        return Math.max(leftTreeMaxSum + node.val, rightTreeMaxSum + node.val);
    }
}

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode ptr = head;
        for (int i = 0; i < k - 1; i++) {
            ptr = ptr.next;
        }
        ListNode kthNode = ptr;
        ListNode lastKthNode = head;
        while (ptr.next != null) {
            ptr = ptr.next;
            lastKthNode = lastKthNode.next;
        }
        int temp = kthNode.val;
        kthNode.val = lastKthNode.val;
        lastKthNode.val = temp;
        return head;
    }
}

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
        int count = 0, max = properties[0][1];
        for (int i = 1; i < properties.length; i++) {
            if (properties[i][1] < max) {
                count += 1;
            }
            max = Math.max(max, properties[i][1]);
        }
        return count;
    }
}

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        List<Integer> tails = new ArrayList<>();
        for (int[] envelop : envelopes) {
            int targetIdx = binarySearch(tails, envelop[1]);
            if (targetIdx + 1 == tails.size()) {
                tails.add(envelop[1]);
            } else {
                tails.set(targetIdx + 1, envelop[1]);
            }
        }
        return tails.size();
    }

    private int binarySearch(List<Integer> tails, int target) {
        int left = 0, right = tails.size() - 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (tails.get(mid) < target) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

class Solution {
    private int ans = 0;

    public int diameter(Node root) {
        helper(root);
        return ans;
    }

    public int helper(Node node) {
        if (node == null) {
            return 0;
        }
        int maxSubTreeHeight = 0, secondMaxSubTreeHeight = 0;
        for (Node child : node.children) {
            int currSubTreeHeight = helper(child);
            if (currSubTreeHeight > maxSubTreeHeight) {
                secondMaxSubTreeHeight = maxSubTreeHeight;
                maxSubTreeHeight = currSubTreeHeight;
            } else if (currSubTreeHeight > secondMaxSubTreeHeight) {
                secondMaxSubTreeHeight = currSubTreeHeight;
            }
        }
        ans = Math.max(ans, maxSubTreeHeight + secondMaxSubTreeHeight);
        return maxSubTreeHeight + 1;
    }
}

class Solution {
    private int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public void wallsAndGates(int[][] rooms) {
        Deque<int[]> posQ = new ArrayDeque<>();
        for (int row = 0; row < rooms.length; row++) {
            for (int col = 0; col < rooms[0].length; col++) {
                if (rooms[row][col] == 0) {
                    posQ.offerLast(new int[] { row, col });
                }
            }
        }
        int steps = 0;
        while (!posQ.isEmpty()) {
            int size = posQ.size();
            for (int i = 0; i < size; i++) {
                int[] currPos = posQ.pollFirst();
                for (int[] direction : DIRECTIONS) {
                    int newRow = currPos[0] + direction[0];
                    int newCol = currPos[1] + direction[1];
                    if (!isOutOfBound(rooms, newRow, newCol) && rooms[newRow][newCol] == Integer.MAX_VALUE) {
                        rooms[newRow][newCol] = steps + 1;
                        posQ.offerLast(new int[] { newRow, newCol });
                    }
                }
            }
            steps += 1;
        }
    }

    private boolean isOutOfBound(int[][] rooms, int row, int col) {
        return row < 0 || row >= rooms.length || col < 0 || col >= rooms[0].length;
    }
}