class Solution {
    private int maxWidth = 0;

    public int widthOfBinaryTree(TreeNode root) {
        helper(root, 0, 1, new ArrayList<>());
        return maxWidth;
    }

    private void helper(TreeNode node, int depth, int index, List<Integer> leftMostIndex) {
        if (node == null)
            return;
        if (depth == leftMostIndex.size()) {
            leftMostIndex.add(index);
        }
        int currWidth = index - leftMostIndex.get(depth) + 1;
        maxWidth = Math.max(currWidth, maxWidth);
        helper(node.left, depth + 1, index * 2, leftMostIndex);
        helper(node.right, depth + 1, index * 2 + 1, leftMostIndex);
    }
}

class Solution {
    private int target;

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> result = new ArrayList<>();
        if (x <= arr[0]) {
            for (int i = 0; i < k; i++) {
                result.add(arr[i]);
            }
            return result;
        }
        if (x >= arr[arr.length - 1]) {
            for (int i = arr.length - k; i < arr.length; i++) {
                result.add(arr[i]);
            }
            return result;
        }
        int left = binarySearch(arr, x), right = left + 1, count = 0;
        while (count != k) {
            if (left >= 0 && right < arr.length) {
                if (compare(arr, left, right, x) <= 0) {
                    result.add(arr[left]);
                    left -= 1;
                } else {
                    result.add(arr[right]);
                    right += 1;
                }
            } else if (left >= 0) {
                result.add(arr[left]);
                left -= 1;
            } else {
                result.add(arr[right]);
                right += 1;
            }
            count += 1;
        }
        Collections.sort(result);
        return result;
    }

    private int binarySearch(int[] arr, int x) {
        int left = 0, right = arr.length - 1, ans = -1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (arr[middle] == x) {
                return middle;
            } else if (arr[middle] < x) {
                ans = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return ans;
    }

    private int compare(int[] arr, int i, int j, int x) {
        if (Math.abs(arr[i] - x) != Math.abs(arr[j] - x)) {
            return Math.abs(arr[i] - x) - Math.abs(arr[j] - x);
        }
        return -1;
    }
}

class Solution {
    private int[] indexLimit;
    private Random rand;

    public Solution(int[] w) {
        indexLimit = new int[w.length];
        rand = new Random();
        int sum = 0;
        for (int i = 0; i < w.length; i++) {
            sum += w[i];
            indexLimit[i] = sum;
        }
    }

    public int pickIndex() {
        int selection = rand.nextInt(indexLimit[indexLimit.length - 1]) + 1;
        return binarySearch(indexLimit, selection);
    }

    private int binarySearch(int[] indexLimit, int selection) {
        int left = 0, right = indexLimit.length - 1, ans = indexLimit.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (indexLimit[mid] < selection) {
                left = mid + 1;
            } else {
                ans = mid;
                right = mid - 1;
            }
        }
        return ans;
    }
}

class Solution {
    private int count = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null)
            return 0;
        Map<Long, Integer> sumCount = new HashMap<>();
        dfs(sumCount, root, 0L, targetSum);
        return count;
    }

    private void dfs(Map<Long, Integer> sumCount, TreeNode node, long currSum, int target) {
        currSum += node.val;
        long remaining = currSum - target;
        if (remaining == 0) {
            count += 1;
        }
        if (sumCount.containsKey(remaining)) {
            count += sumCount.get(remaining);
        }
        sumCount.put(currSum, sumCount.getOrDefault(currSum, 0) + 1);
        if (node.left != null) {
            dfs(sumCount, node.left, currSum, target);
        }
        if (node.right != null) {
            dfs(sumCount, node.right, currSum, target);
        }
        sumCount.put(currSum, sumCount.get(currSum) - 1);
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int count = 0;
        int start = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            int currStart = intervals[i][0];
            int currEnd = intervals[i][1];
            if (currStart < end) {
                count += 1;
                if (currEnd < end) {
                    end = currEnd;
                    start = currStart;
                }
            } else {
                start = currStart;
                end = currEnd;
            }
        }
        return count;
    }
}

class Solution {
    public int characterReplacement(String s, int k) {
        int left = 0, right = 0, maxCount = 0, maxLength = 0;
        int[] count = new int[26];
        while (right < s.length()) {
            // Include a new char
            count[s.charAt(right) - 'A'] += 1;
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
            // If necessary, pop out a char
            // 什么时候pop, 什么时候push很重要
            if (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A'] -= 1;
                left += 1;
            }
            maxLength = Math.max(maxLength, right - left + 1);
            right += 1;
        }
        return maxLength;
    }
}

class Solution {
    public boolean isPerfectSquare(int num) {
        // limit is [1, 46340]
        int left = 1, right = 46340;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midSquare = mid * mid;
            if (midSquare < num) {
                left = mid + 1;
            } else if (midSquare > num) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

class Solution {
    static class NumCountPair {
        int num;
        int count;

        NumCountPair(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int num : nums) {
            numMap.put(num, numMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        for (Map.Entry<Integer, Integer> entry : numMap.entrySet()) {
            q.offer(entry);
            if (q.size() > k) {
                q.poll();
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = q.poll().getKey();
        }
        return ans;
    }
}

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1)
            return false;
        if (n == 1)
            return true;
        return n % 3 == 0 && isPowerOfThree(n / 3);
    }
}

class Solution {
    public int countComponents(int n, int[][] edges) {
        Map<Integer, Set<Integer>> nodeEntry = new HashMap<>();
        for (int[] edge : edges) {
            nodeEntry.putIfAbsent(edge[0], new HashSet<>());
            nodeEntry.get(edge[0]).add(edge[1]);
            nodeEntry.putIfAbsent(edge[1], new HashSet<>());
            nodeEntry.get(edge[1]).add(edge[0]);
        }
        Set<Integer> visited = new HashSet<>();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!visited.contains(i)) {
                if (nodeEntry.containsKey(i)) {
                    dfs(i, nodeEntry, visited);
                }
                ans += 1;
            }
        }
        return ans;
    }

    private void dfs(int node, Map<Integer, Set<Integer>> nodeEntry, Set<Integer> visited) {
        visited.add(node);
        Set<Integer> neighbors = nodeEntry.get(node);
        for (Integer neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, nodeEntry, visited);
            }
        }
    }
}