Kth Smallest Product of Two Sorted Arrays LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool check(long long midval, vector<int> &nums1, vector<int> &nums2, long long k) {
4
    long long cnt = 0;
5
    for (int i = 0; i < nums1.size(); i++) {
6
      long long val = nums1[i];
7

8
      // If val == 0, product of val and each element in nums2 will be 0. And if
9
      // midval>=0, then because all products are 0, all products will be
10
      // smaller or equal to midval. So we can add all products in the answer
11
      if (val == 0 and midval >= 0)
12
        cnt += nums2.size();
13

14
      else if (val > 0)
15
        cnt += findmaxIndex(nums2, val, midval);
16

17
      else if (val < 0)
18
        cnt += findminIndex(nums2, val, midval);
19
    }
20
    return cnt >= k;
21
  }
22

23
  int findmaxIndex(vector<int> &nums2, long long val, long long midval) {
24
    int l = 0, r = nums2.size() - 1, res = -1;
25
    while (l <= r) {
26
      long long mid = (l + r) / 2;
27
      if (val * nums2[mid] <= midval) {
28
        res = mid;
29
        l = mid + 1;
30
      } else
31
        r = mid - 1;
32
    }
33
    return res + 1;
34
  }
35

36
  int findminIndex(vector<int> &nums2, long long val, long long midval) {
37
    int l = 0, r = nums2.size() - 1, res = r + 1;
38
    while (l <= r) {
39
      long long mid = (l + r) / 2;
40
      if (val * nums2[mid] <= midval) {
41
        res = mid;
42
        r = mid - 1;
43
      } else
44
        l = mid + 1;
45
    }
46
    return nums2.size() - res;
47
  }
48

49
  long long kthSmallestProduct(vector<int> &nums1, vector<int> &nums2, long long k) {
50
    long long l = -1e10, r = 1e10, res = -1;
51
    while (l <= r) {
52
      long long mid = (l + r) / 2;
53
      // cout<<mid<<endl;
54
      if (check(mid, nums1, nums2, k)) {
55
        res = mid;
56
        r = mid - 1;
57
      } else
58
        l = mid + 1;
59
    }
60
    return res;
61
  }
62
};