aboutsummaryrefslogtreecommitdiff
path: root/kth_smallest_product_sort_arr.c
blob: 8ab9c80bba8665a47042b246f2d529fb620ba16d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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
}