Binary Search with Visualization for Different Regions | Java, 79ms, 100%
Intuition\nIt\'s basically the same idea as "". Just that we should separate the matrix into four regions, as the order in each region is different and we shoul
# Intuition\nIt\'s basically the same idea as "". Just that we should separate the matrix into four regions, as the order in each region is different and we should traverse the matrix from different starting position and in different direction. A general rule to remember is that "**starting from the max value of a column and walk along ascending direction to the next column**".\n\nA visualization of the four regions are: \n![5C144E9C-88C2-4B8E-BE1E-DBA5633F0D84.jpeg](https://assets.leetcode.com/users/images/12fce226-b138-4903-bb69-a24e10db9f8c_1678606895.7290757.jpeg)\n\n#### Triky Points to Notice\n1. `k` could exceed the integer limit. So the return type of the count function should be `long`.\n2. The product could also exceed the integer limit. Cast to `long` before computing the product.\n\n# Code\n```\nclass Solution {\n    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {\n        if (nums1.length == 1 && nums2.length == 1)\n            return nums1[0] * nums2[0];\n\n        long[] extremes = {(long) nums1[0] * nums2[0],\n                (long) nums1[0] * nums2[nums2.length - 1],\n                (long) nums1[nums1.length - 1] * nums2[0],\n                (long) nums1[nums1.length - 1] * nums2[nums2.length - 1]};\n        Arrays.sort(extremes);\n        int firstNonNegative1 = binarySearch(nums1, 0);\n        int firstNonNegative2 = binarySearch(nums2, 0);\n        long low = extremes[0];\n        long high = extremes[3];\n        //System.out.println("Indices: " \n        //        + String.join(",", String.valueOf(firstNonNegative1), String.valueOf(firstNonNegative2)));\n        //System.out.println("Boundary: "\n        //        + String.join(",", String.valueOf(low), String.valueOf(high)));\n        while(low < high) {\n            long mid = low + (high - low) / 2;\n            if (countLessThan(nums1, nums2, firstNonNegative1, firstNonNegative2, mid) < k) {\n                low = mid + 1;\n            } else {\n                high = mid;\n            }\n        }\n        return high;\n    }\n\n    /**\n        m: index of first element >= 0 in nums1.\n        n: index of first element >= 0 in nums2.\n     */\n    private long countLessThan(int[] nums1, int[] nums2, int m, int n, long target) {\n        long count = 0;\n        // First Region:\n        int row = 0;\n        int col = n - 1;\n        while(row < m && col >= 0) {\n            while(row < m && ((long) nums1[row]) * nums2[col] > target) {\n                row++;\n            }\n            count += m - row;\n            col--;\n        }\n\n        // Second Region:\n        row = m;\n        col = 0;\n        while(row < nums1.length && col < n) {\n            while(row < nums1.length && ((long) nums1[row]) * nums2[col] > target) {\n                row++;\n            }\n            count += nums1.length - row;\n            col++;\n        }\n\n        // Third Region:\n        row = m - 1;\n        col = nums2.length - 1;\n        while(row >= 0 && col >= n) {\n            while(row >= 0 && ((long) nums1[row]) * nums2[col] > target) {\n                row--;\n            }\n            count += row - 0 + 1;\n            col--;\n        }\n\n        // Fourth Region:\n        row = nums1.length - 1;\n        col = n;\n        while(row >= m && col < nums2.length) {\n            while(row >= m && ((long) nums1[row]) * nums2[col] > target) {\n                row--;\n            }\n            count += row - m + 1;\n            col++;\n        }\n        return count;\n    }\n\n    // Find the leftmost element that >= than target.\n    private int binarySearch(int[] nums, int target) {\n        int left = 0;\n        int right = nums.length;\n        while(left < right) {\n            int mid = (left + right) / 2;\n            if (nums[mid] >= target) {\n                right = mid;\n            } else {\n                left = mid + 1;\n            }\n        }\n        return right;\n    }\n}\n```
['Java']