K-th Order

Find K-th Smallest Pair Distance

Whenever you think of log squared → a sliding window is almost always possible.

kth smallest no in multiplication table

Median of 2 arrays sorted arrays

Idea is simple, you canonicalise and say ⇒ … amid … bmid … an … is the range

Then you can count elements that are for sure to left of bmid, and split based on that. Note that on the else part, only left of amid is known for sure.

class Solution {
  public:
    double findMedianSortedArrays(vector<int> &a, vector<int> &b) {
        int an = (int)a.size(), bn = (int)b.size();
 
        auto kth = [&](auto &&f, vector<int> &a, int al, int ar, vector<int> &b, int bl, int br,
                       int k) {
            if (al > ar)
                return b[bl + k - 1];
            if (bl > br)
                return a[al + k - 1];
 
            // canonicalisaton: ensure a mid <= b mid
            int a_mid = (al + ar) / 2, b_mid = (bl + br) / 2;
            if (a[a_mid] > b[b_mid]) {
                return f(f, b, bl, br, a, al, ar, k);
            }
 
            // when ... amid ... bmid ....
            // in merged array, elems left of bmid ( excl bmid )
            int left = a_mid - al + 1 + b_mid - bl;
            if (k <= left) {
                return f(f, a, al, ar, b, bl, b_mid - 1, k);
            } else {
                k -= (a_mid - al + 1); // left of amid
                return f(f, a, a_mid + 1, ar, b, bl, br, k);
            }
        };
 
        int i1 = (an + bn) / 2, i2 = (an + bn - 1) / 2;
 
        double ans = (double)kth(kth, a, 0, an - 1, b, 0, bn - 1, i1 + 1) +
                     kth(kth, a, 0, an - 1, b, 0, bn - 1, i2 + 1);
        ans /= 2;
        return ans;
    }
};

Median of K sorted arrays

Get range of numbers in union all arrays, basically max and min across all. Get total len. Left median index is (total len - 1)/2. Add + 1. This is cnt ⇐ median. Now binary search on condition : are there cnt elements ⇐ mid across all arrays