O(M+N) using old algorithm on virtual matrix
O(M+N) solution, where M and N are the lengths of the two arrays. Using an O(n) solution for finding the kth-smallest element in a sorted n×n matrix. Applied to
O(M+N) solution, where M and N are the lengths of the two arrays. Using an [O(n) solution for finding the kth-smallest element in a sorted n&times;n matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85170/O(n)-from-paper.-Yes-O(rows).). Applied to a virtual matrix I build. "Virtual" meaning I compute its elements on-the-fly, only the elements the algorithm needs to look at. Because building the whole matrix explicitly would take O(MN).\n\nFor example for the arrays `[-2,-1,0,1,2]` and `[-3,-1,2,4,5]` with `k=3`, I first figure out that there are ten negative products, so the kth-smallest product is negative. And thus I build the following virtual matrix of all negative products and find the 7-th smallest element (7 because k=3 and the four -\u221E elements):\n```\n[-\u221E, -\u221E, -10, -8, -4]\n[-\u221E, -\u221E,  -5, -4, -2]\n[-6, -2,   \u221E,  \u221E,  \u221E]\n[-3, -1,   \u221E,  \u221E,  \u221E]\n[ \u221E,  \u221E,   \u221E,  \u221E,  \u221E]\n```\nThe lower-left "quadrant" is the positive values from the first array multiplied with the negative values from the second array. The upper-right quadrant is negatives from first multiplied with positives from second.\n\nThe same arrays `[-2,-1,0,1,2]` and `[-3,-1,2,4,5]` but with `k=20` turns into finding the 9th-smallest element in the virtual matrix of *positive* products:\n```\n[-\u221E, -\u221E,  2,  4,  5]\n[-\u221E, -\u221E,  4,  8, 10]\n[ 1,  3,  \u221E,  \u221E,  \u221E]\n[ 2,  6,  \u221E,  \u221E,  \u221E]\n[ \u221E,  \u221E,  \u221E,  \u221E,  \u221E]\n```\nLower-left are (negatives of first)&times;(negatives of second).\nUpper-right are (positives of first)&times;(positives of second).\n\nThe solution code, the bottom half is the `kthSmallest` function from the old problem:\n\n```\nclass Solution:\n    def kthSmallestProduct(self, A, B, k):\n        \n        # Analyze negatives, positives, zeros\n        negA = [a for a in A if a < 0]\n        posA = [a for a in A if a > 0]\n        negB = [b for b in B if b < 0]\n        posB = [b for b in B if b > 0]\n        nA, pA, nB, pB = map(len, (negA, posA, negB, posB))\n        negatives = nA * pB + pA * nB\n        positives = nA * nB + pA * pB\n        zeros = len(A) * len(B) - negatives - positives\n        \n        # Configure the matrix and adjust k.\n\t\t# A1 and A2 become the factors for the rows (top and bottom part)\n\t\t# B1 and B2 become the factors for the columns (left and right part)\n        if k <= negatives:\n            A1, A2 = negA, posA[::-1]\n            B1, B2 = negB, posB[::-1]\n        else:\n            k -= negatives\n            if k <= zeros:\n                return 0\n            k -= zeros\n            A1, A2 = posA, negA[::-1]\n            B1, B2 = negB[::-1], posB\n            \n        # Build the virtual matrix\n        a1, a2, b1, b2 = map(len, (A1, A2, B1, B2))\n        k += a1 * b1\n        m = len(A1 + A2)\n        n = len(B1 + B2)\n        class Row:\n            def __init__(self, i):\n                if i < a1:\n                    get = lambda j: -inf if j < b1 else A1[i] * B2[j-b1] if j < n else inf\n                elif i < m:\n                    get = lambda j: A2[i-a1] * B1[j] if j < b1 else inf\n                else:\n                    get = lambda j: inf\n                self.get = get\n            def __getitem__(self, j):\n                return self.get(j)\n        matrix = list(map(Row, range(max(m, n))))\n        \n        # Debugging/visualization: print the matrix\n        if 0:\n            print(k)\n            for i in range(len(matrix)):\n                print([matrix[i][j] for j in range(len(matrix))])\n                \n        # Let the matrix solution do the hard work\n        return self.kthSmallest(matrix, k)\n\n    def kthSmallest(self, matrix, k):\n\n        # The median-of-medians selection function.\n        def pick(a, k):\n            if k == 1:\n                return min(a)\n            groups = (a[i:i+5] for i in range(0, len(a), 5))\n            medians = [sorted(group)[len(group) // 2] for group in groups]\n            pivot = pick(medians, len(medians) // 2 + 1)\n            smaller = [x for x in a if x < pivot]\n            if k <= len(smaller):\n                return pick(smaller, k)\n            k -= len(smaller) + a.count(pivot)\n            return pivot if k < 1 else pick([x for x in a if x > pivot], k)\n\n        # Find the k1-th and k2th smallest entries in the submatrix.\n        def biselect(index, k1, k2):\n\n            # Provide the submatrix.\n            n = len(index)\n            def A(i, j):\n                return matrix[index[i]][index[j]]\n            \n            # Base case.\n            if n <= 2:\n                nums = sorted(A(i, j) for i in range(n) for j in range(n))\n                return nums[k1-1], nums[k2-1]\n\n            # Solve the subproblem.\n            index_ = index[::2] + index[n-1+n%2:]\n            k1_ = (k1 + 2*n) // 4 + 1 if n % 2 else n + 1 + (k1 + 3) // 4\n            k2_ = (k2 + 3) // 4\n            a, b = biselect(index_, k1_, k2_)\n\n            # Prepare ra_less, rb_more and L with saddleback search variants.\n            ra_less = rb_more = 0\n            L = []\n            jb = n   # jb is the first where A(i, jb) is larger than b.\n            ja = n   # ja is the first where A(i, ja) is larger than or equal to a.\n            for i in range(n):\n                while jb and A(i, jb - 1) > b:\n                    jb -= 1\n                while ja and A(i, ja - 1) >= a:\n                    ja -= 1\n                ra_less += ja\n                rb_more += n - jb\n                L.extend(A(i, j) for j in range(jb, ja))\n                \n            # Compute and return x and y.\n            x = a if ra_less <= k1 - 1 else \\\n                b if k1 + rb_more - n*n <= 0 else \\\n                pick(L, k1 + rb_more - n*n)\n            y = a if ra_less <= k2 - 1 else \\\n                b if k2 + rb_more - n*n <= 0 else \\\n                pick(L, k2 + rb_more - n*n)\n            return x, y\n\n        # Set up and run the search.\n        n = len(matrix)\n        start = max(k - n*n + n-1, 0)\n        k -= n*n - (n - start)**2\n        return biselect(list(range(start, min(n, start+k))), k, k)[0]\n```
[]