[LeetCode] Kth Smallest Product of Two Sorted Arrays

Problem: Given two sorted 0-indexed integer arrays nums1 and nums2 as well as an integer k, return the kth (1-based) smallest product of nums1[i] * nums2[j] where 0 <= i < nums1.length and 0 <= j < nums2.length.

Example:

Input: nums1 = [2,5], nums2 = [3,4], k = 2
Output: 8
Explanation: The 2 smallest products are:
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
The 2nd smallest product is 8.

Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
Output: 0
Explanation: The 6 smallest products are:
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
The 6th smallest product is 0.

Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
Output: -6
Explanation: The 3 smallest products are:
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
The 3rd smallest product is -6.

Constraints:

• 1 <= nums1.length, nums2.length <= 5 * 10^4
• -10^5 <= nums1[i], nums2[j] <= 10^5
• 1 <= k <= nums1.length * nums2.length
• nums1 and nums2 are sorted.

Approach: One obvious approach would be to store all the products of these two arrays in a different array and then get the kth smallest element in that array. The time complexity is not an issue here as per me as it will be m*n only but the problem is space as you can see the lengths could be 5 * 10^4 for an array so the additional array which we will take to store all the products will be of size 25 * 10^18 which is just too much. Let's try find some other approach.

We can use binary search here. How? What is our sorted array? The sorted array are the numbers in between -10^10 to 10^10. How? Look at the constraint #2, the smallest number can be -10^5 and largest number can be 10^5 so the lowest product could be -10^10 and largest product could be 10^10.

So now we got low and high, obviously we are able to calculate the mid. Once we get the mid, we have to see whether the number of products of nums1 and nums2 which are less than or equal to mid are more than or equal to k or not. If yes, then we know that we need to find a lesser number so high will become mid - 1. Otherwise we need a greater number so we make low as mid + 1. 

Implementation in C#:

    public long KthSmallestProduct(int[] nums1,

        int[] nums2,

        long k)

{

int length1 = nums1.Length;

int length2 = nums2.Length;

List<long> pos1 = new List<long>();

List<long> neg1 = new List<long>();

List<long> pos2 = new List<long>();

List<long> neg2 = new List<long>();

this.GetNegPosNums(nums1, pos1, neg1);

this.GetNegPosNums(nums2, pos2, neg2);

long result = 0;

long low = (long)-1e10, high = (long)1e10;

while (low <= high)

{

long mid = low + (high - low ) / 2;

if (this.Check(mid, pos1, neg1, pos2, neg2, k))

{

result = mid;

high = mid - 1;

}

else

{

low = mid + 1;

}

}

return result;

}

private bool Check(long value,

List<long> pos1,

List<long> neg1,

List<long> pos2,

List<long> neg2,

long k)

{

long count = 0;

// 1 - negative, 2 - negative

int first = 0, second = neg2.Count - 1;

if (neg1.Count > 0 && neg2.Count > 0)

{

while (first < neg1.Count)

{

while (second >= 0 &&

                    neg1[first] * neg2[second] <= value)

{

--second;

}

count += (neg2.Count - 1 - second);

++first;

}

}

// 1 - negative, 2 - positive

first = neg1.Count - 1;

second = pos2.Count - 1;

if (neg1.Count > 0 && pos2.Count > 0)

{

while (first >= 0)

{

while (second >= 0 &&

                    neg1[first] * pos2[second] <= value)

{

--second;

}

count += (pos2.Count - 1 - second);

--first;

}

}

// 1 - positive, 2 - negative

first = pos1.Count - 1;

second = neg2.Count - 1;

if (pos1.Count > 0 && neg2.Count > 0)

{

while (second >= 0)

{

while (first >= 0 &&

                    pos1[first] * neg2[second] <= value)

{

--first;

}

count += (pos1.Count - 1 - first);

--second;

}

}

// 1 - positive, 2 - positive

first = 0;

second = pos2.Count - 1;

if (pos1.Count > 0 && pos2.Count > 0)

{

while (first < pos1.Count)

{

while (second >= 0 &&

                    pos1[first] * pos2[second] > value)

{

--second;

}

count += (second + 1);

++first;

}

}

return count >= k;

}

private void GetNegPosNums(int[] nums,

        List<long> pos,

        List<long> neg)

{

foreach (int num in nums)

{

if (num < 0)

{

neg.Add(num);

}

else

{

pos.Add(num);

}

}

}

Complexity: O((m + n) * 2 ^ (range)) where range is 10^10 - (-10^10).