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

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        long[] sumArray = new long[nums.length];
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            sumArray[i] = sum;
        }
        Deque<Integer> monoq = new LinkedList<>();
        int ans = nums.length + 1;
        for (int i = 0; i < sumArray.length; i++) {
            while (!monoq.isEmpty() && sumArray[monoq.peekLast()] >= sumArray[i]) {
                monoq.pollLast();
            }
            while (!monoq.isEmpty() && sumArray[i] - sumArray[monoq.peekFirst()] >= k) {
                ans = Math.min(ans, i - monoq.pollFirst());
            }
            ans = sumArray[i] >= k ? Math.min(ans, i + 1) : ans;
            monoq.offer(i);
        }
        return ans == nums.length + 1 ? -1 : ans;
    }
}

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }
        // Store for a given stop, which route(s) contain such stop
        // This means from this stop, all the stops in the routes that contain such stop
        // can be arrived by taking one bus
        Map<Integer, List<Integer>> stopRoutesMap = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                stopRoutesMap.putIfAbsent(stop, new ArrayList<>());
                stopRoutesMap.get(stop).add(i);
            }
        }
        Queue<Integer> stopQueue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        boolean[] visitedRoutes = new boolean[routes.length];
        int busNum = 0;
        stopQueue.offer(source);
        visited.add(source);
        while (!stopQueue.isEmpty()) {
            // Currently the queue contains all the stops that we can arrive with busNum
            // buses
            int size = stopQueue.size();
            for (int i = 0; i < size; i++) {
                int currStop = stopQueue.poll();
                List<Integer> routesInvolved = stopRoutesMap.get(currStop);
                for (Integer routeNum : routesInvolved) {
                    if (visitedRoutes[routeNum]) {
                        continue;
                    }
                    int[] stopOfCurrRoute = routes[routeNum];
                    for (int stop : stopOfCurrRoute) {
                        if (visited.add(stop)) {
                            if (stop == target) {
                                return busNum + 1;
                            } else {
                                stopQueue.offer(stop);
                            }
                        }
                    }
                    visitedRoutes[routeNum] = true;
                }
            }
            // Right now, the queue contains all the stops that need busNum + 1 buses to
            // arrive
            // so we update busNum now
            busNum += 1;
        }
        return -1;
    }
}

class Solution {
    private static class HeapNode {
        int row;
        int col;
        int num;

        HeapNode(int _row, int _col, int _num) {
            row = _row;
            col = _col;
            num = _num;
        }
    }

    public int kthSmallest(int[][] matrix, int k) {
        int initialHeapSize = Math.min(matrix.length, k);
        PriorityQueue<HeapNode> minHeap = new PriorityQueue<>((a, b) -> a.num - b.num);
        for (int i = 0; i < initialHeapSize; i++) {
            minHeap.offer(new HeapNode(i, 0, matrix[i][0]));
        }
        int count = 0;
        while (count < k - 1) {
            HeapNode currNode = minHeap.poll();
            int currRow = currNode.row, currCol = currNode.col;
            if (currCol + 1 < matrix[0].length) {
                minHeap.offer(new HeapNode(currRow, currCol + 1, matrix[currRow][currCol + 1]));
            }
            count += 1;
        }
        return minHeap.peek().num;
    }
}

class Solution {
    public boolean increasingTriplet(int[] nums) {
        Stack<Integer> monoStack = new Stack<>();
        boolean[] hasSmaller = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            while (!monoStack.isEmpty() && nums[monoStack.peek()] >= nums[i]) {
                monoStack.pop();
            }
            if (!monoStack.isEmpty()) {
                hasSmaller[i] = true;
            }
            monoStack.push(i);
        }
        int currSecondSmallest = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > currSecondSmallest) {
                return true;
            }
            if (hasSmaller[i] && nums[i] < currSecondSmallest) {
                currSecondSmallest = nums[i];
            }
        }
        return false;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                int targetIdx = nums[i] - 1;
                swap(nums, i, targetIdx);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

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

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1)
            return head;
        ListNode currHead = head, nextHead = head;
        ListNode prevTail = new ListNode(0), dummy = prevTail;
        while (currHead != null) {
            int count = 0;
            while (count < k && nextHead != null) {
                nextHead = nextHead.next;
                count += 1;
            }
            if (nextHead == null && count < k) {
                prevTail.next = currHead;
                break;
            }
            ListNode newHead = reverse(currHead, k);
            prevTail.next = newHead;
            prevTail = currHead;
            currHead = nextHead;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head, int k) {
        ListNode prev = null, curr = head;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0 && nums2.length == 0) {
            return 0.0;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        for (int i = 0; i < nums1.length; i++) {
            addNum(nums1[i], minHeap, maxHeap);
        }
        for (int i = 0; i < nums2.length; i++) {
            addNum(nums2[i], minHeap, maxHeap);
        }
        return minHeap.size() == maxHeap.size() ? (minHeap.peek() + maxHeap.peek()) * 0.5 : (double) minHeap.peek();
    }

    private void addNum(int num, PriorityQueue<Integer> minHeap, PriorityQueue<Integer> maxHeap) {
        minHeap.offer(num);
        maxHeap.offer(minHeap.poll());
        if (maxHeap.size() > minHeap.size()) {
            minHeap.offer(maxHeap.poll());
        }
    }
}

// 给我一个array以及一个范围, 我能把这个范围里面的数字都给从小到大sort好. 这是quicksort.
class Solution {
    public static int[] quickSort(int[] array) {
        helper(array, 0, array.length - 1);
        return array;
    }

    private static void helper(int[] array, int start, int end) {
        if (start >= end)
            return;
        int pivot = start, left = start + 1, right = end;
        while (left <= right) {
            if (array[left] > array[pivot] && array[right] < array[pivot]) {
                swap(array, left, right);
                left += 1;
                right -= 1;
                continue;
            }
            if (array[left] <= array[pivot]) {
                left += 1;
            }
            if (array[right] >= array[pivot]) {
                right -= 1;
            }
        }
        swap(array, pivot, right);
        boolean isLeftShorter = (right - start) < (end - right);
        if (isLeftShorter) {
            helper(array, start, right - 1);
            helper(array, right + 1, end);
        } else {
            helper(array, right + 1, end);
            helper(array, start, right - 1);
        }
    }

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

// 给我一个array以及一个范围以及一个k, 我能告诉你这个第k小的数字是多少.
class Solution {
    public static int quickselect(int[] array, int k) {
        // Write your code here.
        return helper(array, 0, array.length - 1, k);
    }

    public static int helper(int[] array, int start, int end, int k) {
        // Should never be reached unless k is greater than array.length
        if (start > end)
            return -1;
        int pivot = start, left = start + 1, right = end;
        while (left <= right) {
            if (array[left] > array[pivot] && array[right] < array[pivot]) {
                swap(array, left, right);
                left += 1;
                right -= 1;
                continue;
            }
            if (array[left] <= array[pivot]) {
                left += 1;
            }
            if (array[right] >= array[pivot]) {
                right -= 1;
            }
        }
        swap(array, pivot, right);
        if (right == k - 1)
            return array[right];
        else if (right < k - 1)
            return helper(array, right + 1, end, k);
        else
            return helper(array, start, right - 1, k);
    }

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