class Solution {
    TreeNode successor;
    TreeNode lastVisited;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root, p);
        return successor;
    }
    
    private void dfs(TreeNode node, TreeNode target) {
        if (node == null)
            return;
        dfs(node.left, target);
        if (successor != null)
            return;
        if (lastVisited == target) {
            successor = node;
            return;
        }
        lastVisited = node;
        dfs(node.right, target);
    }
    
}

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> allocator = new PriorityQueue<>(intervals.length, (a, b) -> Integer.compare(a, b));
        allocator.add(intervals[0][1]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= allocator.peek()) {
                allocator.poll();
            }
            allocator.offer(intervals[i][1]);
        }
        return allocator.size();
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = 0, col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (target == matrix[row][col]) {
                return true;
            } else if (target < matrix[row][col]) {
                col -= 1;
            } else {
                row += 1;
            }
        }
        return false;
    }
}

class Solution {
    public int calculate(String s) {

        if (s == null || s.isEmpty())
            return 0;
        int len = s.length();
        Stack<Integer> stack = new Stack<Integer>();
        int currentNumber = 0;
        char operation = '+';
        for (int i = 0; i < len; i++) {
            char currentChar = s.charAt(i);
            if (Character.isDigit(currentChar)) {
                currentNumber = (currentNumber * 10) + (currentChar - '0');
            }
            if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == len - 1) {
                if (operation == '-') {
                    stack.push(-currentNumber);
                } else if (operation == '+') {
                    stack.push(currentNumber);
                } else if (operation == '*') {
                    stack.push(stack.pop() * currentNumber);
                } else if (operation == '/') {
                    stack.push(stack.pop() / currentNumber);
                }
                operation = currentChar;
                currentNumber = 0;
            }
        }
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        return result;
    }
}

class Solution {
    public int maximalSquare(char[][] matrix) {
        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        int ans = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        return ans * ans;
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSelect(nums, 0, nums.length - 1, k);
        return nums[k - 1];
    }

    private int quickSelect(int[] nums, int low, int up, int k) {
        int pivot = low, left = low + 1, right = up;
        while (left <= right) {
            if (nums[left] < nums[pivot] && nums[right] > nums[pivot]) {
                swap(nums, left, right);
                left += 1;
                right -= 1;
                continue;
            }
            if (nums[left] >= nums[pivot]) {
                left += 1;
            }
            if (nums[right] <= nums[pivot]) {
                right -= 1;
            }
        }
        swap(nums, pivot, right);
        if (right == k - 1) {
            return right;
        } else if (right < k - 1) {
            return quickSelect(nums, right + 1, up, k);
        } else {
            return quickSelect(nums, low, right - 1, k);
        }
    }

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

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> visited = new HashSet<>();
        visited.add(n);
        while (n != 1) {
            n = convert(n);
            if (visited.contains(n))
                return false;
            visited.add(n);
        }
        return true;
    }

    private int convert(int n) {
        int ans = 0;
        while (n != 0) {
            int current = n % 10;
            ans += current * current;
            n /= 10;
        }
        return ans;
    }
}

import java.util.*;

class Solution {
    private class MyComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            String mergedOne = a + b;
            String mergedTwo = b + a;
            return mergedTwo.compareTo(mergedOne);
        }
    }

    public String largestNumber(int[] nums) {
        String[] numStrings = new String[nums.length];
        for (int i = 0; i < numStrings.length; i++) {
            numStrings[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(numStrings, new MyComparator());

        if (numStrings[0].equals("0")) {
            return "0";
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < numStrings.length; i++) {
            ans.append(numStrings[i]);
        }
        return ans.toString();
    }
}

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

        // Two strings are identical
        if (ptrOne == s.length() && ptrTwo == t.length()) {
            return false;
        }

        if (s.length() < t.length()) {
            return s.substring(ptrOne).equals(t.substring(ptrTwo + 1));
        } else if (s.length() > t.length()) {
            return s.substring(ptrOne + 1).equals(t.substring(ptrTwo));
        } else {
            return s.substring(ptrOne + 1).equals(t.substring(ptrTwo + 1));
        }
    }
}

class Solution {
    public int findMin(int[] nums) {
        if (nums[nums.length - 1] >= nums[0])
            return nums[0];
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[0]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}