Binary search with detailed explanation
Note: credit goes to lee215 for the inverse/reverse trick\n\n### Step 1. k\'th smallest product for lists with only positive numbers\n\nImagine that there are o
***Note: credit goes to lee215 for the inverse/reverse trick***\n\n### Step 1. k\'th smallest product for lists with only positive numbers\n\nImagine that there are only positive numbers, and we want to find the k\'th smallest number.\n\nConsider the two lists `a=[1,2,3]` and `b=[1,5,8]`. Their products form a matrix:\n\n| - | 1 | 2 | 3 |\n| --- | --- | --- | --- |\n| __1__ | 1 | 2 | 3 |\n| __5__ | 5 | 10 | 15 |\n| __8__ | 8 | 18 | 24 |\n\nAssuming that we guess a number `x`, then it\'s possible to quickly determine how many numbers are smaller than `x`. Just iterate row by row, moving a right pointer left until the condition is satisfied and count the number of elements before the pointer:\n\n```go\nfunc count(a, b []int, val int) int {\n\tvar count int\n\tj := len(b) - 1\n\tfor i := range a {\n\t\tfor j >= 0 && a[i]*b[j] > val {\n\t\t\tj--\n\t\t}\n\t\tcount += j + 1\n\t}\n\treturn count\n}\n```\n\nWith this approach, it\'s easy to find the k\'th positive number using binary search:\n\n```go\nvar lo, hi int = 0, 1e10\nfor lo < hi {\n\tmid := (lo + hi) / 2\n\tres := count(a, b, mid)\n\tif res >= int(k) {\n\t\thi = mid\n\t} else {\n\t\tlo = mid + 1\n\t}\n}\nreturn lo\n```\n\n### Step 2. Mixed numbers\n\nSo far so good. The problem is with the negative numbers. When the lists contain negative numbers, then their products form a kind of criss-cross pattern. Positive numbers are the result of combining numbers diagonally across in the matrix, and negative numbers are the result of combining numbers vertically:\n\n```\n \\ | - | + |\n - | + | - |\n + | - | + |\n```\n\nIn order to search numbers, input lists are split into two halves:\n\n```bash\na = [ -5, -2, -1, 0, 1, 2 ]\n    |----[a1]---|---[a2]--]\n\nb = [ -8, -5, -2, 3, 5 ]\n    |----[b1]---|-[b2]-|\n```\n\nThe first thing to note is that the number of positive / negative numbers can be counted by multiplying the lengths of each section:\n\n```go\nnegCount := len(a1)*len(b2) + len(b1)*len(a2)\n```\n\nKnowing how many numbers exist, if a request is made for `k <= negCount`, then that product must be in one of the negative quadrants, and vice versa for `k > negCount`. This tells us which sections to combine when searching for an answer.\n\nHowever, simply multiplying elements in order from different segments yield different signs and orderings:\n\n| first | second | sign | order |\n| --- | --- | --- | --- |\n| a1 | b1 | + | desc |\n| a1 | b2 | - | no order |\n| a2 | b1 | - | no order |\n| a2 | b2 | + | asc |\n\nThe first trick here is to reverse negative portions, which results in ordered outputs:\n\n| first | second | sign | order |\n| --- | --- | --- | --- |\n| rev(a1) | rev(b1) | + | asc |\n| rev(a1) | b2 | - | desc |\n| a2 | rev(b1) | - | desc |\n| a2 | b2 | + | asc |\n\nAt this point it would be possible to write two different binary search functions, one for searching from the right, and one from the left. But there is one final trick to make the code cleaner. \n\nBy inverting negative values (making them positive), it\'s possible to search in the same way for negative and positive numbers. However, the k\'th result will no longer be the k\'th smallest, but rather the k\'th largest number:\n\n| first | second | sign | order |\n| --- | --- | --- | --- |\n| inv(rev(a1)) | inv(rev(b1)) | + | asc |\n| inv(rev(a1)) | b2 | + | desc |\n| a2 | inv(rev(b1)) | + | desc |\n| a2 | b2 | + | asc |\n\n### Final solution:\n\n```go\nfunc kthSmallestProduct(nums1 []int, nums2 []int, k int64) int64 {\n\taSplit := sort.SearchInts(nums1, 0)\n\tbSplit := sort.SearchInts(nums2, 0)\n\ta1, a2 := rev(inv(nums1[:aSplit])), nums1[aSplit:]\n\tb1, b2 := rev(inv(nums2[:bSplit])), nums2[bSplit:]\n\n\tnegCount := len(a1)*len(b2) + len(b1)*len(a2)\n\n\tsign := 1\n\tif int(k) > negCount {\n\t\tk -= int64(negCount) // => kth smallest number from non-negative part\n\t} else {\n\t\tk = int64(negCount) - k + 1 // => kth largest number after transform\n\t\tb1, b2 = b2, b1             // swap to fix combination\n\t\tsign = -1\n\t}\n\n\tvar lo, hi int = 0, 1e10\n\tfor lo < hi {\n\t\tmid := (lo + hi) / 2\n\t\tif rcount(a1, b1, mid) + count(a2, b2, mid) >= int(k) {\n\t\t\thi = mid\n\t\t} else {\n\t\t\tlo = mid + 1\n\t\t}\n\t}\n\treturn int64(sign * lo)\n}\n\nfunc count(a, b []int, val int) int {\n\tvar count int\n\tj := len(b) - 1\n\tfor i := range a {\n\t\tfor j >= 0 && a[i]*b[j] > val {\n\t\t\tj--\n\t\t}\n\t\tcount += j + 1\n\t}\n\treturn count\n}\n\nfunc inv(a []int) []int {\n\tfor i := range a {\n\t\ta[i] = -a[i]\n\t}\n\treturn a\n}\n\nfunc rev(a []int) []int {\n\tfor l, r := 0, len(a)-1; l < r; l, r = l+1, r-1 {\n\t\ta[l], a[r] = a[r], a[l]\n\t}\n\treturn a\n}\n\n```
['Go']