algoadvance

Leetcode 786. K

Problem Statement

Given two integer arrays arr and brr. arr represents a sorted array of unique integers, and brr represents a brand new array which is the multiplier of the same size as arr. For example, if arr = [1, 2, 3] and brr = [5, 10, 15], each index in brr is a result of multiplying the arr element at the same index by some integer.

Your task is to find and return the k-th smallest fraction arr[i] / brr[j] formed by any element from arr divided by any element from brr.

Constraints:

Clarifying Questions

Before we begin the implementation, let’s clarify some things:

  1. Are both arrays arr and brr guaranteed to be non-empty?
  2. Do both arrays contain positive integers only?
  3. Is it certain that all such fractions will be distinct?
  4. The input constraints mention 1 <= k <= arr.length * brr.length, can we assume there will be no issues with accessing the k-th element?

These are critical to confirm the assumptions and constraints for our solution.

Strategy

  1. Heap Approach:
    • Use a min-heap to store the fractions in conjunction with indices from both arrays.
    • Extract elements from the heap until you reach the k-th smallest element.
  2. Binary Search Approach:
    • Utilize binary search to narrow down the potential k-th smallest fraction.
    • Count how many fractions are less than a given middle value to guide the binary search.

Due to the potential large size of the product arr.length * brr.length, a heap-based solution can help manage the problem efficiently.

Code

Here is the C++ code using a min-heap strategy:

#include <queue>
#include <vector>
#include <tuple>

using namespace std;

vector<int> kthSmallestPrimeFraction(vector<int>& arr, vector<int>& brr, int k) {
    // Min-heap to store {value, i, j} tuples, where value = arr[i] / brr[j]
    auto compare = [&arr, &brr](tuple<double, int, int>& a, tuple<double, int, int>& b) {
        return get<0>(a) > get<0>(b);
    };
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, decltype(compare)> minHeap(compare);
    
    // Initialize the min-heap with the first element in every row
    for (int i = 0; i < arr.size(); ++i) {
        minHeap.push({(double)arr[i] / brr[0], i, 0});
    }
    
    // Extract k-1 elements from the heap
    tuple<double, int, int> frac;
    for (int count = 0; count < k - 1; ++count) {
        frac = minHeap.top();
        minHeap.pop();
        int i = get<1>(frac);
        int j = get<2>(frac);
        if (j + 1 < brr.size()) {
            minHeap.push({(double)arr[i] / brr[j + 1], i, j + 1});
        }
    }
    
    // The k-th smallest fraction
    frac = minHeap.top();
    return {arr[get<1>(frac)], brr[get<2>(frac)]};
}

Time Complexity

This solution efficiently handles the problem using a priority queue (min-heap) to ensure we can fetch the k-th smallest fraction accurately.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI