2040. Kth Smallest Product of Two Sorted Arrays

About this solution

Kth Smallest Product of Two Sorted Arrays is a unknown-difficulty LeetCode problem covering the Array, Binary Search, Sorting patterns. The Java solution below uses an idiomatic approach that is clean, readable, and directly submittable on LeetCode. Study the logic carefully — recognising the underlying pattern is the key skill that transfers to similar problems in interviews.

Key Techniques

Array

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Binary Search

Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"

Sorting

Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.

2040.java

Java

import java.util.*;

class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        List<Integer> A1 = new ArrayList<>();
        List<Integer> A2 = new ArrayList<>();
        List<Integer> B1 = new ArrayList<>();
        List<Integer> B2 = new ArrayList<>();

        seperate(nums1, A1, A2);
        seperate(nums2, B1, B2);

        final long negCount = A1.size() * B2.size() + A2.size() * B1.size();
        int sign = 1;

        if (k > negCount)
            k -= negCount; // Find the (k - negCount)-th positive.
        else {
            k = negCount - k + 1; // Find the (negCount - k + 1)-th abs(negative).
            sign = -1;
            List<Integer> temp = B1;
            B1 = B2;
            B2 = temp;
        }

        long l = 0;
        long r = (long) 1e10;

        while (l < r) {
            final long m = (l + r) / 2;
            if (numProductNoGreaterThan(A1, B1, m) + numProductNoGreaterThan(A2, B2, m) >= k)
                r = m;
            else
                l = m + 1;
        }

        return sign * l;
    }

    private void seperate(int[] arr, List<Integer> A1, List<Integer> A2) {
        for (final int a : arr) {
            if (a < 0)
                A1.add(-a);
            else
                A2.add(a);
        }

        Collections.reverse(A1); // Reverse to sort ascending
    }

    private long numProductNoGreaterThan(List<Integer> A, List<Integer> B, long m) {
        long count = 0;
        int j = B.size() - 1;
        // For each a, find the first index j s.t. a * B[j] <= m
        // So numProductNoGreaterThan m for this row will be j + 1
        for (final long a : A) {
            while (j >= 0 && a * B.get(j) > m)
                --j;
            count += j + 1;
        }
        
        return count;
    }
}

Was this solution helpful?