aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--kth_smallest_product_sort_arr.c95
-rw-r--r--kth_smallest_product_sort_arr.py45
2 files changed, 140 insertions, 0 deletions
diff --git a/kth_smallest_product_sort_arr.c b/kth_smallest_product_sort_arr.c
new file mode 100644
index 0000000..8ab9c80
--- /dev/null
+++ b/kth_smallest_product_sort_arr.c
@@ -0,0 +1,95 @@
+// 2040. Kth Smallest Product of Two Sorted Arrays
+#include "leetcode.h"
+
+/*
+ * 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'
+ */
+
+long long kthSmallestProduct(int *nums1, int nums1Size, int *nums2,
+ int nums2Size, long long k) {
+ int n1 = 0, n2 = 0;
+ while (n1 < nums1Size && nums1[n1] < 0)
+ n1++;
+ while (n2 < nums2Size && nums2[n1] < 0)
+ n2++;
+ int z1 = 0, p1 = 0;
+ for (int i = n1; i < nums1Size; i++) {
+ if (!nums1[i])
+ z1++;
+ else
+ p1++;
+ }
+ int z2 = 0, p2 = 0;
+ for (int i = n2; i < nums2Size; i++) {
+ if (!nums2[i])
+ z2++;
+ else
+ p2++;
+ ;
+ }
+ int p1_beg = n1 + z1, p2_beg = n2 + z2;
+ long long start = -1e9, end = 1e9;
+ while (start <= end) {
+ long long mid = (start + end) / 2, total = 0;
+ if (mid >= 0) {
+ total += (long long)n1 * p2 + (long long)p1 * n2;
+ total += (long long)z1 * nums2Size + (long long)(nums1Size - z1) * z2;
+ int i = 0, j = n2 - 1;
+ while (i < n1 && j >= 0) {
+ if ((long long)nums1[i] * nums2[j] > mid)
+ i++;
+ else {
+ total += n1 - i;
+ j--;
+ }
+ }
+ i = p1_beg, j = nums2Size - 1;
+ while (i < nums1Size && j >= p2_beg) {
+ if ((long long)nums1[i] * nums2[j] > mid)
+ j--;
+ else {
+ total += j - p2_beg + 1;
+ i++;
+ }
+ }
+ } else {
+ int i = 0, j = p2_beg;
+ while (i < n1 && j < nums2Size) {
+ if ((long long)nums1[i] * nums2[j] > mid)
+ j++;
+ else {
+ total += nums2Size - j;
+ i++;
+ }
+ }
+ i = p1_beg, j = 0;
+ while (i < nums1Size && j < n2) {
+ if ((long long)nums1[i] * nums2[j] > mid)
+ i++;
+ else {
+ total += nums1Size - i;
+ j++;
+ }
+ }
+ }
+ if (total < k)
+ start = mid + 1;
+ else
+ end = mid - 1;
+ }
+ return start;
+}
+
+int main() {
+ int n11[] = {2, 5}, n21[] = {3, 4};
+ int n12[] = {-4, -2, 0, 3}, n22[] = {2, 4};
+ int n13[] = {-2, -1, 0, 1, 2}, n23[] = {-3, -1, 2, 4, 5};
+ printf("%lld\n", kthSmallestProduct(n11, ARRAY_SIZE(n11), n21,
+ ARRAY_SIZE(n21), 2)); // expect: 8
+ printf("%lld\n", kthSmallestProduct(n12, ARRAY_SIZE(n12), n22,
+ ARRAY_SIZE(n22), 6)); // expect: 0
+ printf("%lld\n", kthSmallestProduct(n13, ARRAY_SIZE(n13), n23,
+ ARRAY_SIZE(n23), 3)); // expect: -6
+}
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))