class Solution {
    public boolean validPalindrome(String s) {
        int len = s.length();
        if(len < 2) return true;

        int i = 0, j = len - 1;

        while(i < j) {
            if(s.charAt(i) != s.charAt(j)) {
                return isValid(s, i+1, j) || isValid(s, i, j - 1);
            }
            i++;
            j--;
        }

        return true;
    }

    public boolean isValid(String s, int start, int end) {
        while(start < end) {
            if(s.charAt(start++) != s.charAt(end--)){
                return false;
            }
        }
           
        return true;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int i =0, j = 0, max = 0;
        while(j < s.length()){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                max = Math.max(max, set.size());
            }else{
                set.remove(s.charAt(i++));
            }
            
        }
        return max;
    }
}

 public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        int[] cache = new int[256];
        for (int i = 0, j = 0; i < s.length(); i++) {
            j = (cache[s.charAt(i)] > 0) ? Math.max(j, cache[s.charAt(i)]) : j;
            cache[s.charAt(i)] = i + 1;
            result = Math.max(result, i - j + 1);
        }
        return result;
    }
}

class Solution {
   public ListNode reverseList(ListNode head) {
       ListNode pre = null;
       ListNode cur = head;
      
       while(cur != null) {
           ListNode next = cur.next;
           
           cur.next = pre;
           pre = cur;
           cur = next;
       }
       
       return pre;
   }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        if(l1 == null) return l2;
        else if(l2 == null) return l1;
        
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            
            curr = curr.next;
            
          
        }
        
        curr.next = (l1 == null) ? l2 : l1;
        return dummy.next;
    }
}

// 先进行优化，创建两个array
class Solution {
    public int trap(int[] arr) {
        if(arr == null || arr.length < 2) {
            return 0;
        }
        
        int N = arr.length;
        
        int[] leftMax  = new int[N];
        int[] rightMax  = new int[N];
        
        leftMax[0] = arr[0];
        rightMax[N-1] = arr[N-1];
        
        for(int i = 1; i < N; i++) {
           leftMax[i] = Math.max(leftMax[i-1], arr[i]);
        }
        
         for(int i = N-2; i >= 0; i--) {
           rightMax[i] = Math.max(leftMax[i+1], arr[i]);
        }
        
        int water = 0;
        for(int i = 1; i < N -1; i ++) {
            water += Math.max(Math.min(rightMax[i+ 1], leftMax[i-1]) - arr[i], 0);
        }
        
        return water;
    }
}

// 双指针
  int left = 0, right = arr.length - 1;
        int ans = 0;
        int leftMax = 0, rightMax = 0;
        while(left < right) {
            if(arr[left] < arr[right]){
                arr[left] >= leftMax ? leftMax = arr[left] : ans += (leftMax - arr[left]);
                ++ left;
            } else {
                arr[right] >= rightMax ? rightMax = arr[right]: ans += (rightMax - arr[right]);
                -- right;
            }
        }
        
        return ans;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> largeK = new PriorityQueue<Integer>(k + 1);

        for(int el : nums) {
            largeK.add(el);
            if (largeK.size() > k) {
                largeK.poll();
            }
        }

        return largeK.poll();
        }
}

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return findKth(a, 0, n-1, K);
    }

      public int findKth(int[] a, int low, int high, int k) {
        int part = partition(a, low, high);
        
        if(k == part - low + 1) return a[part];
        else if(k > part - low + 1) return findKth(a, part + 1, high, k - part + low -1);
        else return findKth(a, low, part -1, k);    
    }
                     
        
public int partition(int[] a, int left, int right) {
        int pivot = a[right];
        int low = left, high = right;
        while(low < high) {
            while(low<high && a[low] >= pivot) {
                low ++;
            }
            while(low<high && a[high] <= pivot) {
                high --;
            }
            int temp = a[low];
            a[low] = a[high];
            a[high] = temp;
        }
        int temp = a[low];
        a[low] = pivot;
        a[right] = temp;
        
        return low;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        if (n <= 1) return new ArrayList<>();
        
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>(); 
        
        for (int i = 0; i < n - 2; i++) {
             //为了保证不加入重复的 list,因为是有序的，所以如果和前一个元素相同，只需要继续后移就可以
            if (i==0 || (i > 0 && nums[i] != nums[i-1])) {
                int low = i + 1, high = n - 1, sum = 0 - nums[i];
                
                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                            res.add(Arrays.asList(nums[i], nums[low], nums[high]));
                            while (low < high && nums[low] == nums[low+1]) low++;
                            while (low < high && nums[high] == nums[high-1]) high --;
                            low ++;
                            high --;
                            
                        
                    } else if (nums[low] + nums[high] < sum) {
                        low ++;
                    } else {
                        high --;
                    }
                }
            }
        }
        
        
        return res;

    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

class Solution {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[edges.size()];

        for(int[] p : prerequisites) {
            edges.get(p[1]).add(p[0]);
        }

        for(int i = 0; i < edges.size() & valid; i++) {
            if(visited[i] == 0) {
                dfs(i);
            }
        }

        return valid;
    }

    public void dfs(int u) {
        visited[u] = 1;

        for(int v : edges.get(u)) {
            if(visited[v] == 0) {
                dfs(v);
                if(!valid) {
                    return;
                }
            } else if(visited[v] == 1) {
                valid = false;
                return;
            }
        }

        visited[u] = 2;
    }
}

// to do

class MyQueue {
    private Stack<Integer> a;// 输入栈
    private Stack<Integer> b;// 输出栈
    /** Initialize your data structure here. */
    public MyQueue() {
        a = new Stack<>();
        b = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        a.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(b.isEmpty()) {
            while(!a.isEmpty()) {
                b.push(a.pop());
            }
        }
        return b.pop();
    }
    
    /** Get the front element. */
    public int peek() {
         if(b.isEmpty()) {
            while(!a.isEmpty()) {
                b.push(a.pop());
            }
        }
        return b.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return a.isEmpty() && b.isEmpty();
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
//         if (root == null) 
//             return null;
        
        
//         TreeNode right = invertTree(root.right);
//         TreeNode left = invertTree(root.left);
        
//         root.left = right;
//         root.right = left;
        
//         return root;
        
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;
            if (current.left != null) queue.add(current.left);
            if (current.right != null) queue.add(current.right);
        }
        
        
        
        return root;
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int[] visited = new int[nums.length];

        backtrack(res, nums, visited, new ArrayList<>());

        return res;
    }

    public void backtrack(List<List<Integer>> res, int[] nums, int[] visited, ArrayList<Integer> temp) {

        if(temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(visited[i] == 1) continue;
            visited[i] = 1;
            temp.add(nums[i]);
            backtrack(res, nums, visited, temp);
            temp.remove(temp.size() - 1);
            visited[i] = 0;
        }
    }
}

class Solution {
    public List<List<Integer>> res=new ArrayList<>();
    // public List<List<Integer>> subsets(int[] nums) {
    //     List<Integer> temp = new ArrayList<>();
    //     dfs(nums, temp,  0);
    //     res.add(new ArrayList<>());
    //     return res;
    // }

    // public void dfs(int[] nums, List<Integer> temp, int len) {

    //     for(int i = len; i < nums.length; i++) {
    //         temp.add(nums[i]);
    //         res.add(new ArrayList<>(temp));
           
    //          dfs(nums, temp, i + 1);
    //          temp.remove(temp.size() - 1);
    //     }
    // }

    public List<List<Integer>> subsets(int[] nums) {
        res.add(new ArrayList<>());

        for(int num : nums) {
            for(int i = 0, j=res.size(); i < j; i ++) {
                List<Integer> list = new ArrayList(res.get(i));
                list.add(num);
                res.add(list);
            }
        }

        return res;
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode mid = findMid(head);
        ListNode rightNode = mid.next;
        mid.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightNode);

        return merge(left, right);

    }

    public ListNode findMid(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode fast = head.next, slow = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast= fast.next.next;
        }

        return slow;
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while(left != null && right != null) {
            if(left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }

        cur.next = left != null ? left : right;

        return dummy.next;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }

        return mergeKLists(lists, 0, lists.length - 1);

    }

    public ListNode mergeKLists(ListNode[] lists, int low, int high) {
        if(low >= high) return lists[low];

        int mid = low + ((high - low) >> 1);

        ListNode left = mergeKLists(lists, low, mid);
        ListNode right = mergeKLists(lists, mid + 1, high);

        return merge(left ,right);
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while(left != null && right != null) {
            if(left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }

            cur = cur.next;
        }
        cur.next = left != null ? left : right;

        return dummy.next;
    }
}

class Solution {
    public int maxAreaOfIsland(int[][] grid) {

        int max = 0;
        for(int i = 0; i < grid.length; ++ i) {
            for(int j = 0; j < grid[0].length; ++ j) {
                if(grid[i][j] == 1) {
                    max = Math.max(dfs(grid, i, j), max);
                }
            }
        }

        return max;
    }

    public int dfs(int[][] grid, int i, int j) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0;
        int count = 1;


        grid[i][j] = 0;
        count += dfs(grid, i + 1, j);
        count += dfs(grid, i -1, j);
        count += dfs(grid, i, j + 1);
        count += dfs(grid, i, j - 1);

        return count;
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int right = search(nums, target, true);
        int left = search(nums, target, false);

        return new int[] {left, right};
    }


    // find the rightmost index of the target if <right> is true
    public int search(int[] nums, int target, boolean right) {
        int low = 0;
        int high = nums.length - 1;
        int mid;
        int index = -1;

        while(low <= high) {
            mid = low + ((high - low) >> 1);
            if(nums[mid] < target || (right && nums[mid] == target)) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            if(nums[mid] == target) {
                index = mid;
            }
        }

        return index;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == q || root == p) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left != null && right != null) {
            return root;
        } else if(left != null) {
            return left;
        } else {
            return right;
        }
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return count(root, 0);
    }

    public int count(TreeNode root, int level) {
        if(root != null) {
            return Math.max(count(root.left, level + 1), count(root.right, level +1));
        } else {
            return level;
        }
    }
}

 public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(res, "", 0, 0, n);

        return res;
    }

    public void dfs(List<String> res, String str, int left, int right, int n) {

        if(left < right || left > n) return;

        if(left + right == 2*n) {
            res.add(str);
        }

        dfs(res, str + "(", left + 1, right, n);
        dfs(res, str + ")", left, right + 1, n);
    }
}

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        if(root == null) return res;
        // for bfs search 
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
                if(i == size - 1) {
                    res.add(node.val);
                }

            }
        }
        return res;
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int x = matrix[0].length, y = matrix.length;
        List<Integer> res = new ArrayList<>();

        int top = 0, left = 0, bottom = y - 1, right = x - 1;

        int total = 0;
        int index = 0;
        while(total < x*y) {
            for(int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
                total ++;
            }
            top ++;

            for(int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
                total ++;
            }
            right --;


            for(int i = right ; i >= left ;i --) {
                res.add(matrix[bottom][i]);  
                total ++;     
            }
            bottom --;

            for(int i = bottom; i >= top ; i --) {
                res.add(matrix[i][left]); 
                total ++;
            }  

            left ++;

        }   

        return res;                                  
    }
}

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return root;
        
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);

        root.left = right;
        root.right = left;

        return root;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;

        while(a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA: b.next;
        }

        return a;
    }
}

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

    public void dfs(List<List<Integer>> res, TreeNode root, int level) {
        if(root == null) return;

        if(res.size() == level) {
            res.add(new ArrayList<>());
        }

        if(level % 2 == 0) {
            res.get(level).add(root.val);
        } else {
            res.get(level).add(0, root.val);
        }

        dfs(res, root.left, level +1);
        dfs(res, root.right, level +1);
    }
}

    public int solution(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int max = 0, total = 0;
        for(int[] interval : intervals) {
            int count = map.getOrDefault(interval[0], 0);
            map.put(interval[0], count + 1);
            count = map.getOrDefault(interval[1], 0);
            map.put(interval[1], count - 1);
        }

        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            total += entry.getValue();
            max = Math.max(total, max);
        }

        return max;
    }

    public int solution2(int[][] intervals) {
      if(intervals.length == 0) return 0;
      int max = 1;
      Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
      PriorityQueue<Integer> q = new PriorityQueue<>();
      
      for(int[] interval : intervals) {
          while(interval[0] >= q.peek()) {
              q.poll();
          }
          q.offer(interval[1]);
          max = Math.max(q.size(), max);
      }
      
      return max;
      
    }

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        ArrayList<int[]> lists = new ArrayList<>();

        // lists.add(new int[] {intervals[0][0], intervals[0][1]});

        // for(int i = 1; i < intervals.length; ++ i) {
        //     if(intervals[i][0] > lists.get(lists.size() - 1)[1]) {
        //         lists.add(new int[] {intervals[i][0], intervals[i][1]});
        //     } else {
        //         lists.get(lists.size() - 1)[1] = Math.max(lists.get(lists.size() - 1)[1], intervals[i][1]);
        //     }
        // }
        int max;

        for(int i = 0; i < intervals.length;) {
            int j = i + 1;
            int t = intervals[i][1];

            while(j< intervals.length && t >= intervals[j][0]) {
                t = Math.max(t, intervals[j][1]);    
                j ++;
            }

            lists.add(new int[] {intervals[i][0], t});

            i = j;
        }

        return lists.toArray(new int[lists.size()][2]);

    }
}