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

    public boolean containsCycle(char[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] >= 97 && hasCycle(grid, i, j, -1, -1)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean hasCycle(char[][] grid, int row, int col, int prevRow, int prevCol) {
        char currChar = grid[row][col];
        grid[row][col] -= 32;
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (!isOutBound(grid, newRow, newCol) && (newRow != prevRow || newCol != prevCol) &&
                    Character.toLowerCase(grid[newRow][newCol]) == currChar) {
                if (grid[newRow][newCol] != currChar) {
                    return true;
                } else if (hasCycle(grid, newRow, newCol, row, col)) {
                    return true;
                }
            }
        }
        return false;
    }

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

class Solution {
    private int count;
    private int deepest;
    private int found;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        if (root == null) {
            return null;
        }
        helper(root, 0);
        return findSubTree(root, 0);
    }

    private void helper(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        if (depth > deepest) {
            deepest = depth;
            count = 1;
        } else if (depth == deepest) {
            count += 1;
        }
        helper(node.left, depth + 1);
        helper(node.right, depth + 1);
    }

    private TreeNode findSubTree(TreeNode node, int depth) {
        if (node == null) {
            return null;
        }
        int foundNodes = found;
        if (depth == deepest) {
            found += 1;
            if (found - foundNodes == count) {
                return node;
            } else {
                return null;
            }
        }
        TreeNode leftTree = findSubTree(node.left, depth + 1);
        if (leftTree != null) {
            return leftTree;
        }
        if (found - foundNodes == count) {
            return node;
        }
        TreeNode rightTree = findSubTree(node.right, depth + 1);
        if (rightTree != null) {
            return rightTree;
        }
        if (found - foundNodes == count) {
            return node;
        }
        return null;
    }
}

class Solution {
    private TreeNode startNode;

    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, TreeNode> nodeParent = new HashMap<>();
        startNode = root;
        buildParentMap(nodeParent, root.left, root, k);
        buildParentMap(nodeParent, root.right, root, k);
        Set<TreeNode> visited = new HashSet<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(startNode);
        while (!q.isEmpty()) {
            TreeNode currNode = q.poll();
            if (currNode.left == null && currNode.right == null) {
                return currNode.val;
            }
            visited.add(currNode);
            if (currNode.left != null && !visited.contains(currNode.left)) {
                q.offer(currNode.left);
            }
            if (currNode.right != null && !visited.contains(currNode.right)) {
                q.offer(currNode.right);
            }
            TreeNode currParent = nodeParent.get(currNode);
            if (currParent != null && !visited.contains(currParent)) {
                q.offer(currParent);
            }
        }
        return -1;
    }

    private void buildParentMap(Map<TreeNode, TreeNode> nodeParent, TreeNode node, TreeNode parent, int k) {
        if (node == null) {
            return;
        }
        nodeParent.put(node, parent);
        if (node.val == k) {
            startNode = node;
        }
        buildParentMap(nodeParent, node.left, node, k);
        buildParentMap(nodeParent, node.right, node, k);
    }
}

class Solution {
    public int findMinDifference(List<String> timePoints) {
        boolean[] minutes = new boolean[24 * 60];
        int minMinute = Integer.MAX_VALUE, maxMinute = Integer.MIN_VALUE;
        for (String timePoint : timePoints) {
            String[] hourMinute = timePoint.split(":");
            int hour = Integer.parseInt(hourMinute[0]);
            int minute = Integer.parseInt(hourMinute[1]);
            int pos = hour * 60 + minute;
            if (minutes[pos]) {
                return 0;
            }
            minutes[pos] = true;
            minMinute = Math.min(minMinute, pos);
            maxMinute = Math.max(maxMinute, pos);
        }
        int prev = minMinute, ans = Integer.MAX_VALUE;
        for (int i = minMinute + 1; i <= maxMinute; i++) {
            if (minutes[i]) {
                ans = Math.min(ans, i - prev);
                prev = i;
            }
        }
        ans = Math.min(ans, 24 * 60 - maxMinute + minMinute);
        return ans;
    }
}

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, ans, 0);
        return ans;
    }

    private void dfs(TreeNode node, List<Integer> ans, int level) {
        if (node == null) {
            return;
        }
        if (level == ans.size()) {
            ans.add(node.val);
        } else {
            ans.set(level, Math.max(node.val, ans.get(level)));
        }
        dfs(node.left, ans, level + 1);
        dfs(node.right, ans, level + 1);
    }
}

class Solution {
    private Node head, tail;

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        Node[] headTailPair = helper(root);
        headTailPair[0].left = headTailPair[1];
        headTailPair[1].right = headTailPair[0];
        return headTailPair[0];
    }

    private Node[] helper(Node node) {
        if (node == null) {
            return new Node[] { null, null };
        }
        Node[] leftTree = helper(node.left);
        Node[] rightTree = helper(node.right);
        Node[] ans = new Node[] { node, node };
        if (leftTree[1] != null) {
            node.left = leftTree[1];
            leftTree[1].right = node;
            ans[0] = leftTree[0];
        }
        if (rightTree[0] != null) {
            node.right = rightTree[0];
            rightTree[0].left = node;
            ans[1] = rightTree[1];
        }
        return ans;
    }
}

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Integer> visited = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Integer ceiling = visited.ceiling(nums[i]);
            if (ceiling != null && ceiling - nums[i] <= valueDiff)
                return true;

            Integer floor = visited.floor(nums[i]);
            if (floor != null && nums[i] - floor <= valueDiff)
                return true;

            visited.add(nums[i]);
            if (visited.size() > indexDiff) {
                visited.remove(nums[i - indexDiff]);
            }
        }
        return false;
    }
}

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> visited = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (visited.containsKey(nums[i]) && i - visited.get(nums[i]) <= k) {
                return true;
            } else {
                visited.put(nums[i], i);
            }
        }
        return false;
    }
}

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0, maxSoFar = 0;
        for (int i = 0; i < values.length; i++) {
            ans = Math.max(ans, values[i] + maxSoFar);
            maxSoFar = Math.max(maxSoFar, values[i]) - 1;
        }
        return ans;
    }
}

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> subset = new HashSet<>();
        for (int num : nums) {
            subset.add(num);
        }
        int ans = 0;
        ListNode ptr = head;
        while (ptr != null) {
            int count = 0;
            while (ptr != null && subset.contains(ptr.val)) {
                count += 1;
                ptr = ptr.next;
            }
            if (count >= 1) {
                ans += 1;
            } else {
                ptr = ptr.next;
            }
        }
        return ans;
    }
}