aboutsummaryrefslogtreecommitdiff
path: root/kth_smallest_product_sort_arr.py
diff options
context:
space:
mode:
Diffstat (limited to 'kth_smallest_product_sort_arr.py')
-rw-r--r--kth_smallest_product_sort_arr.py45
1 files changed, 45 insertions, 0 deletions
diff --git a/kth_smallest_product_sort_arr.py b/kth_smallest_product_sort_arr.py
new file mode 100644
index 0000000..459a00c
--- /dev/null
+++ b/kth_smallest_product_sort_arr.py
@@ -0,0 +1,45 @@
+# 2040. Kth Smallest Product of Two Sorted Arrays
+import bisect
+from math import ceil
+
+"""
+given two sorted 0-indexed integer arrays 'nums1' and 'nums2' as well as an
+integer 'k', return the k'th smallest product of 'nums1[i] nums2[i]' where
+'0 <= i < nums1.length' and '0 <= j < nums2.length'
+"""
+
+
+class Solution(object):
+ def kthSmallestProduct(self, nums1, nums2, k):
+ """
+ :type nums1: List[int]
+ :type nums2: List[int]
+ :type k: int
+ :rtype: int
+ """
+
+ def check(n):
+ total = 0
+ for i in nums1:
+ if i > 0:
+ total += bisect.bisect(nums2, n // i)
+ if i < 0:
+ total += len(nums2) - bisect.bisect_left(nums2, ceil(n / i))
+ if i == 0 and n >= 0:
+ total += len(nums2)
+
+ start, end = -(10**10) - 1, 10**10 + 1
+ while start + 1 < end:
+ mid = (start + end) // 2
+ if check(mid) >= k:
+ end = mid
+ else:
+ start = mid
+ return start + 1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.kthSmallestProduct(nums1=[2, 5], nums2=[3, 4], k=2))
+ print(obj.kthSmallestProduct(nums1=[-4, -2, 0, 3], nums2=[2, 4], k=6))
+ print(obj.kthSmallestProduct(nums1=[-2, -1, 0, 1, 2], nums2=[-3, -1, 2, 4, 5], k=3))