This post is a quick summary of all common solutions applicable to problems similar to [*378. Kth Smallest Element in a Sorted Matrix*](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/), where we are given an `n x n` matrix with each of the rows and columns sorted in ascending order, and need to find the `kth` smallest element in the matrix. \n\nFor your reference, the following is a list of LeetCode problems that can be transformed into problems equivalent to finding the *"Kth Smallest Element in a Sorted Matrix"* and thus can be solved effectively using the algorithms developed here:\n\n1. [373. Find K Pairs with Smallest Sums](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/)\n2. [378. Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/)\n3. [668. Kth Smallest Number in Multiplication Table](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/)\n4. [719. Find K-th Smallest Pair Distance](https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/)\n5. [786. K-th Smallest Prime Fraction](https://leetcode.com/problems/k-th-smallest-prime-fraction/description/)\n\nThis list may not be complete and you\'re welcome to add more examples. Also if you\'re only interested in solutions to this problem (i.e., `786. K-th Smallest Prime Fraction`), you may go directly to the last section (section `VIII`) where I have listed a couple of solutions as demonstrations to algorithms that will be derived shortly.\n\n---\n\n**`I -- Sorting-based solution`**\n\nThis is the most straightforward solution, where we put all the elements in the matrix into an array and sort it in ascending order, then the `kth` smallest element in the matrix will be the one at index `k-1` of the array. Here is a quick demonstration of this algorithm:\n\n
\n\n```\npublic int kthSmallest(int[][] matrix, int k) {\n int n = matrix.length, i = 0;\n \n int[] nums = new int[n * n];\n \n for (int[] row : matrix) {\n for (int ele : row) {\n nums[i++] = ele;\n }\n }\n \n Arrays.sort(nums);\n \n return nums[k - 1];\n}\n```\n\n
\n\nTime complexity: `O(n^2 * log(n^2))`\nSpace complexity: `O(n^2)`\n\nAs expected, this naive solution is not very performant in terms of time (due to sorting) and space (due to the extra array) complexities, so let\'s see how we may improve it and derive more efficient algorithms.\n\n---\n\n**`II -- PriorityQueue-based solution`**\n\nOne observation here is that we don\'t need to keep track of all the `n^2` elements since only the `kth` smallest element is required. We may maintain a `PriorityQueue` with size `k` to track only the `k` smallest elements in the matrix. At the end, the `kth` smallest element in the matrix will be the largest one in the `PriorityQueue`. Here is an implementation of this idea:\n\n
\n\n```\npublic int kthSmallest(int[][] matrix, int k) {\n PriorityQueue pq = new PriorityQueue<>(Collections.reverseOrder());\n \n for (int[] row : matrix) {\n for (int ele : row) {\n pq.offer(ele);\n \n if (pq.size() > k) {\n pq.poll();\n }\n }\n }\n \n return pq.peek();\n}\n```\n\n
\n\nTime complexity: `O(n^2 * logk)`\nSpace complexity: `O(k)`\n\nThough in the worst case (`k = n^2`), the time and space complexities of this solution are the same as those of the naive solution above, we are still able to achieve slight performance gains for average cases where `k` is generally smaller compared to `n^2`.\n\n---\n\n**`III -- PriorityQueue-based solution with optimization`**\n\nUp to this point, you may notice that the above two solutions actually apply to arbitrary matrices -- they will find the `kth` smallest element in the matrix whether or not its rows or columns are sorted. What happens if we take advantage of the sorted properties of the matrix?\n\nWell, I have yet to mention another straightforward way for finding the `kth` smallest element in the matrix: if we keep removing the smallest element from the matrix for `k-1` times, then after removing, the smallest element now in the matrix will be the `kth` smallest element we are looking for. \n\nIf the elements in the matrix are in random order, we have no better ways for finding and removing the smallest elements in the matrix other than adding all elements to a `PriorityQueue`. This will yield a time (and space) complexity no better, if not worse, than that of the naive solution. However, with the rows (or columns) of the matrix sorted, we don\'t have to add all elements to the `PriorityQueue` at once. Instead, we can create a pool of candidate elements as long as we can ensure that it contains the smallest element of the matrix (even after removing). \n\nAssume the rows are sorted in ascending order, which implies initially the smallest element of the matrix must be within the first column, therefore the pool can be initialized with elements from the first column. Now as we are extracting and removing smallest elements from the pool, we need to supplement more candiate elements. The key observation here is that for each extracted element, it suffices to add to the pool only the element immediately following it in the same row, without violating the property that the pool always contains the smallest element of the matrix (even after removing). The following is a solution based on this idea:\n\n
\n\n```\npublic int kthSmallest(int[][] matrix, int k) {\n PriorityQueue pq = new PriorityQueue<>(new Comparator() {\n public int compare(int[] a, int[] b) { // (a[0], a[1]) and (b[0], b[1]) are positions in the matrix\n return Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]);\n }\n });\n \n int n = matrix.length;\n \n for (int i = 0; i < n; i++) {\n pq.offer(new int[] {i, 0}); // initialize the pool with elements from the first column\n }\n \n while (--k > 0) { // remove the smallest elements from the matrix (k-1) times\n int[] p = pq.poll();\n \n if (++p[1] < n) {\n pq.offer(p); // add the next element in the same row if it exists\n }\n }\n \n return matrix[pq.peek()[0]][pq.peek()[1]];\n}\n```\n\n
\n\nTime complexity: `O(max(n, k) * logn)`\nSpace complexity: `O(n)`\n\nNote that by making use of the sorted properties of the matrix, we were able to cut down the space complexity to `O(n)` and achieve a slightly better time complexity compared to that of the naive solution (though the worst case is the same).\n\n---\n\n**`IV -- BinarySearch-based solution`**\n\nThe binary search solution is essentially a special case of the more general "trial and error" algorithm described in my other [post](https://leetcode.com/problems/find-k-th-smallest-pair-distance/discuss/109082/Approach-the-problem-using-the-%22trial-and-error%22-algorithm), where I have summarized the algorithm\'s key ideas and demonstrated them for `LeetCode 719`. I would recommend you read at least the beginning part to get familiar with the terminologies that will be used here.\n\n
\n\n**The candidate solution**: in this case, the cadidate solution is simply an integer.\n\n**The search space**: in this case, the search space is given by `[MIN, MAX]`, where `MIN` and `MAX` are the minimum and maximum elements in the matrix, respectively. \n\n**The traverse method**: in this case, we can do a binary search since the search space is sorted naturally in ascending order (this also accounts for the name "BinarySearch-based solution").\n\n**The verification algorithm**: in this case, the verification algorithm is implemented by comparing the count of elements in the matrix **less than or equal to** the candidate solution, denoted as `cnt`, with the rank `k`: if `cnt < k`, we throw away the left half of the search space; otherwise we discard the right half.\n\n
\n\nNote that the verification algorithm is based on the following two observations:\n\n1. There will be **at least** `k` elements in the matrix that are *less than or equal to* the `kth` smallest element.\n\n2. If there are **at least** `k` elements in the matrix that are *less than or equal* to a candidate solution, then the actual `kth` smallest element in the matrix *cannot be greater than* this candiate solution.\n\nAlso the counting of elements no greater than a candidate solution can be done in linear time by employing the classic two-pointer techinique which takes advantage of the sorted properties of the matrix. The following is the solution for this algorithm:\n\n
\n\n```\npublic int kthSmallest(int[][] matrix, int k) {\n int n = matrix.length;\n \n int l = matrix[0][0]; // minimum element in the matrix\n int r = matrix[n - 1][n - 1]; // maximum element in the matrix\n \n for (int cnt = 0; l < r; cnt = 0) { // this is the binary search loop\n int m = l + (r - l) / 2;\n \n for(int i = 0, j = n - 1; i < n; i++) {\n while (j >= 0 && matrix[i][j] > m) j--; // the pointer j will only go in one direction\n cnt += (j + 1);\n }\n \n if (cnt < k) {\n l = m + 1; // cnt less than k, so throw away left half\n } else {\n r = m; // otherwise discard right half\n }\n }\n \n return l;\n}\n```\n\n
\n\nTime complexity: `O(n * log(MAX - MIN))`\nSpace complexity: `O(1)`\n\nThe binary search solution is much more efficient compared to those derived in previous sections. We use only constant space and the time complexity is almost linear for any practical integer matrices (for which `MIN` and `MAX` are within the `32-bit` integer range).\n\n---\n\n**`V -- ZigzagSearch-based solution`**\n\nThe zigzag search solution is another special version of the more general "trial and error" algorithm, where now the search space is formed only by integers contained in the input matrix itself, rather than continous integers in the range `[MIN, MAX]`. We can summarize the following properties of this solution:\n\n
\n\n**The candidate solution**: in this case, the cadidate solution is also an integer, but it must be an element of the input matrix.\n\n**The search space**: in this case, the search space is given by the input matrix itself.\n\n**The traverse method**: in this case, we cannot do a binary search since there is no total ordering of the candidate solutions. However, we do have partial orderings where each row and column of the matrix are sorted in ascending order. This enables us to do a zigzag search where we start from the upper-right corner of the matrix and proceed to either the next row or previous column depending on the result of the verification algorithm (we can also start from the bottom-left corner and proceed to either the previous row or next column).\n\n**The verification algorithm**: in this case, the verification algorithm is implemented by comparing two counts, denoted as `cnt_lt` and `cnt_le` respectively, with the rank `k`: if `cnt_le < k`, we proceed to the next row; else if `cnt_lt >= k`, we proceed to the previous column; otherwise we\'ve found the `kth` smallest element in the matrix so return it. Here `cnt_lt` denotes the number of elements in the matrix **less than** the candidate solution, while `cnt_le` denotes the number of elements in the matrix **less than or equal to** the candidate solution (the reason we need two counts is that there may be duplicates in the input matrix).\n\n
\n\nNote that the verification algorithm is based on the following two observations:\n\n1. There will be **at most** `k - 1` elements in the matrix that are *less than* the `kth` smallest element.\n\n2. There will be **at least** `k` elements in the matrix that are *less than or equal to* the `kth` smallest element.\n\nAnd again the counting can be done in linear time using the classic two-pointer techinique. The following is the code for this algorithm:\n\n
\n\n```\npublic int kthSmallest(int[][] matrix, int k) {\n int n = matrix.length;\n \n int row = 0; // we start from the upper-right corner\n int col = n - 1; \n \n for (int cnt_le = 0, cnt_lt = 0; true; cnt_le = 0, cnt_lt = 0) {\n for (int i = 0, j = n - 1, p = n - 1; i < n; i++) {\n while (j >= 0 && matrix[i][j] > matrix[row][col]) j--; // pointer j for counting cnt_le\n cnt_le += (j + 1);\n \n while (p >= 0 && matrix[i][p] >= matrix[row][col]) p--; // pointer p for counting cnt_lt\n cnt_lt += (p + 1);\n }\n \n if (cnt_le < k) { // candidate solution too small so increase it\n row++; \n } else if (cnt_lt >= k) { // candidate solution too large so decrease it\n col--;\n } else { // candidate solution equal to the kth smallest element so return\n return matrix[row][col];\n }\n }\n}\n```\n\n
\n\nTime complexity: `O(n^2)`\nSpace complexity: `O(1)`\n\nThe zigzag search solution is less efficient compared to the binary search solution, but still achieves significant performance gains compared to the other three solutions.\n\n---\n\n**`VI -- BiSelect solution`**\n\nThis is the most advanced algorithm for this type of problems that achieves linear time complexity. The main theory is based on the ideas proposed in [*this paper*](http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf). Here is an implementation in Java, which is very lengthy. I would refer you to this awesome [post](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85170/on-from-paper-yes-orows) by [*stefanpochmann*](https://discuss.leetcode.com/user/stefanpochmann) for a shorter and concise version in Python, and this [post](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85201/c-on-time-on-space-solution-with-detail-intuitive-explanation) by [zhiqing_xiao](https://leetcode.com/zhiqing_xiao/) for more explanations (and a solution in C++). This BiSelect-algorithm is good to know but may not be suitable for an interview, so you may opt to skip it and continue.\n\n
\n\n```\npublic int kthSmallest(int[][] matrix, int k) {\n int n = matrix.length;\n\t\t\n int[] index = new int[n];\n\t \n for (int i = 0; i < n; i++) {\n index[i] = i;\n }\n \n int[] L = new int[12 * n];\n \n return biselect(matrix, index, k, k, L)[0];\n}\n\nprivate int[] biselect(int[][] matrix, int[] index, int k1, int k2, int[] L) {\n int n = index.length;\n \n if (n <= 2) {\n int[] nums = new int[n * n];\n \n for (int i = 0, k = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n nums[k++] = matrix[index[i]][index[j]];\n }\n }\n \n Arrays.sort(nums);\n \n return new int[] {nums[k1 - 1], nums[k2 - 1]};\n }\n \n int[] index_ = new int[(n + 1) / 2 + (n - 1) % 2];\n int k1_ = 0;\n int k2_ = (k2 + 3) / 4;\n \n for (int i = 0, k = 0; i < n; i += 2) {\n index_[k++] = index[i];\n }\n \n if (n % 2 == 0) {\n index_[index_.length - 1] = index[n - 1];\n k1_ = (k1 + 3) / 4 + n + 1;\n } else {\n k1_ = (k1 + 2 * n) / 4 + 1;\n }\n \n int[] pair = biselect(matrix, index_, k1_, k2_, L);\n int a = pair[0], b = pair[1];\n int ra_less = 0, rb_more = 0;\n \n int Len = 0;\n \n for (int i = 0, ja = n, jb = n; i < n; i++) {\n while (ja > 0 && matrix[index[i]][index[ja - 1]] >= a) ja--;\n ra_less += ja;\n \n while (jb > 0 && matrix[index[i]][index[jb - 1]] > b) jb--;\n rb_more += n - jb;\n \n for (int j = jb; j < ja; j++) {\n L[Len++] = matrix[index[i]][index[j]];\n }\n }\n \n int x = 0, y = 0;\n \n if (ra_less <= k1 - 1) {\n x = a;\n } else if (k1 + rb_more - n * n <= 0) {\n x = b;\n } else {\n x = L[pick(L, 0, Len, k1 + rb_more - n * n)];\n }\n \n if (ra_less <= k2 - 1) {\n y = a;\n } else if (k2 + rb_more - n * n <= 0) {\n y = b;\n } else {\n y = L[pick(L, 0, Len, k2 + rb_more - n * n)];\n }\n \n return new int[] {x, y};\n}\n\t\nprivate int pick(int[] nums, int l, int r, int k) {\n int[] pos = partition(nums, l, r, medianOfMedians(nums, l, r));\n \n int p = pos[0], q = pos[1];\n \n if (q - l < k) {\n return pick(nums, q, r, k - (q - l));\n } else if (k <= p - l) {\n return pick(nums, l, p, k);\n } else {\n return p;\n }\n}\n \nprivate int[] partition(int[] nums, int l, int r, int pos) {\n int pivot = nums[pos];\n swap(nums, pos, r - 1);\n \n int p = l, q = r - 1;\n \n for (int i = l; i < q;) {\n if (nums[i] < pivot) {\n swap(nums, p++, i++);\n } else if (nums[i] > pivot) {\n swap(nums, i, --q);\n } else {\n i++;\n }\n }\n \n swap(nums, q++, r - 1);\n \n return new int[] {p, q};\n}\n \nprivate int medianOfMedians(int[] nums, int l, int r) {\n if (r - l <= 5) return medianOfFive(nums, l, r);\n \n int rr = l;\n \n for (int i = l; i < r; i += 5) {\n swap(nums, rr++, medianOfFive(nums, i, Math.min(i + 5, r)));\n }\n \n return pick(nums, l, rr, (rr - l + 1) / 2);\n}\n \nprivate int medianOfFive(int[] nums, int l, int r) {\n Arrays.sort(nums, l, r);\n return l + (r - l - 1) / 2;\n}\n \nprivate void swap(int[] nums, int i, int j) {\n int t = nums[i];\n nums[i] = nums[j];\n nums[j] = t;\n}\n```\n\n
\n\nTime complexity: `O(n)`\nSpace complexity: `O(n)`\n\n---\n\n**`VII -- Transform other problems into "Kth Smallest Element in a Sorted Matrix"`**\n\nFor problems other than the "Kth Smallest Element in a Sorted Matrix", to apply the algorithms developed above, we need to rephrase and transform them into one that is equivalent to finding the `Kth Smallest Element in a Sorted Matrix`. Whether we can do so depends on the nature of the problems, but at least this is true for those listed at the beginning of the post.\n\nNow the key to the transformation process is to build the sorted matrix in terms of the problem input. On the one hand, we need to relate each matrix element `matrix[i][j]` to the problem input. On the other hand, we need to arrange these elements so that each row and column of the matrix are sorted in ascending order. Again, these details will depend on the nature of the problems. But as far as this post is concerned, I will assume the input are two arrays sorted in ascending order, denoted as `a` and `b` respectively, and the matrix elements can be computed using arithmetic operations of the two array elements.\n\n1. Addition: `matrix[i][j] = a[i\'] + b[j\']`\n2. Subtraction: `matrix[i][j] = a[i\'] - b[j\']`\n3. Multiplication: `matrix[i][j] = a[i\'] * b[j\']`\n4. Division: `matrix[i][j] = a[i\'] / b[j\']`\n\nNote that the index mappings `i --> i\'` and `j --> j\'` are not necessarily identity mappings, but rather they will be chosen to ensure that the rows and columns in the matrix are sorted in ascending order. For simplicity, we name two type of mappings here which are *identity mapping* (where `i\' = i` and `j\' = j`) and *"negative" mapping* (where `i\' = na - 1 - i` and `j\' = nb - 1 - j`, with `na`, `nb` being the lengths of the two arrays).\n\n
\n\nNext I will reformulate LeetCode problems `378`, `668`, `719` and `786` as examples to show how the transformation is done:\n\n1. [373. Find K Pairs with Smallest Sums](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/): In this case, the two input arrays are `nums1` and `nums2`, so `a` will refer to `nums1` and `b` to `nums2`. And we have `matrix[i][j] = nums1[i] + nums2[j]`, where identity mappings are chosen for both the row and column indices. Note that for this problem we are required to find all the `K` pairs with the smallest sums, so the optimized PriorityQueue solution would be the best to try.\n\n
\n\n2. [668. Kth Smallest Number in Multiplication Table](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/): In this case, only the lengths of the two arrays are given as input, but it\'s trival to get the array elements (`a[i] = i + 1`, `b[j] = j + 1`). And we have `matrix[i][j] = a[i] * b[j]`, where again identity mappings are chosen for both the row and column indices. The `Kth` smallest element in the multiplication table will be the same as the `Kth` smallest element in the matrix.\n\n
\n\n3. [719. Find K-th Smallest Pair Distance](https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/): In this case there is only one array `nums` as input, so both `a` and `b` will refer to `nums`. After sorting `nums` in ascending order, we have `matrix[i][j] = nums[i] - nums[n - 1 - j]`, where `n = nums.length`. Note that the mapping for column index is chosen to be "negative" in order to make sure the columns are sorted in ascending order. Also note that our matrix will contain all pair distances (including negative ones) while the original problem asks for the `Kth` smallest pair distance out of absolute pair distances (there are `n(n-1)/2` such pairs). So we need to shift the rank up to `K\' = K + n(n+1)/2`. The `Kth` smallest pair distance then will be the `K\'th` smallest element in the matrix.\n\n
\n\n4. [786. K-th Smallest Prime Fraction](https://leetcode.com/problems/k-th-smallest-prime-fraction/description/): In this case again there is only one array `A` as input, so both `a` and `b` will refer to `A`. We have `matrix[i][j] = nums[i] / nums[n - 1 - j]`, where `n = A.length` and `/` is floating point division (not integer division). Again the mapping for column index is chosen to be "negative" to ensure the columns are sorted in ascending order. The `Kth` smallest prime fraction then will be the `Kth` smallest element in the matrix.\n\n
\n\nNote that there may be other properties of the matrix that are specific to a particular problem, such as whether the matrix contains duplicates or not, whether the matrix elements are integers or not, etc. These extra properties may help optimize the algorithms developed earlier.\n\n---\n\n**`VIII -- Solutions for this problem (786. K-th Smallest Prime Fraction)`**\n\nIn this section, I will list three solutions for this problem, where the first one is an example of the optimized PriorityQueue-based solution, the second is an example of the BinarySearch-based solution, and the last one is an example of the ZigzagSearch-based solution.\n\n
\n\n**SOLUTION ONE** -- Using PriorityQueue with optimization\n\n* Time complexity: `O((n + K) * logn)`, with `n = A.length`\n* Space complexity: `O(n)`\n\n```\npublic int[] kthSmallestPrimeFraction(int[] A, int K) {\n int n = A.length;\n \n PriorityQueue pq = new PriorityQueue<>(new Comparator() {\n public int compare(int[] a, int[] b) {\n return Integer.compare(A[a[0]] * A[n - 1 - b[1]], A[n - 1 - a[1]] * A[b[0]]);\n }\n });\n \n for (int i = 0; i < n; i++) {\n pq.offer(new int[] {i, 0});\n }\n \n while (--K > 0) {\n int[] p = pq.poll();\n \n if (++p[1] < n) {\n pq.offer(p);\n }\n }\n \n return new int[] {A[pq.peek()[0]], A[n - 1 - pq.peek()[1]]};\n}\n```\n\nRemarks:\n\n1. When accessing the input array using column index `j` of the matrix, we need to perform the "negative" mapping to get the correct index into the array: `j\' = n - 1 - j`.\n\n2. When comparing two fractions, instead of doing floating-point divisions, we convert them into integer multiplications: `p/q < x/y <==> p * y < x * q`. This optimization is also used in the following two solutions.\n\n
\n\n**SOLUTION TWO** -- Using BinarySearch\n\n* Time complexity: `O(n * log(MAX^2))`, where `MAX` is the maximum element in `A`\n* Space complexity: `O(1)`\n\n```\npublic int[] kthSmallestPrimeFraction(int[] A, int K) {\n double l = 0, r = 1;\n int p = 0, q = 1;\n \n for (int n = A.length, cnt = 0; true; cnt = 0, p = 0) {\n double m = (l + r) / 2;\n \n for (int i = 0, j = n - 1; i < n; i++) {\n while (j >= 0 && A[i] > m * A[n - 1 - j]) j--;\n cnt += (j + 1);\n \n if (j >= 0 && p * A[n - 1 - j] < q * A[i]) {\n p = A[i];\n q = A[n - 1 - j];\n }\n }\n \n if (cnt < K) {\n l = m;\n } else if (cnt > K) {\n r = m;\n } else {\n return new int[] {p, q};\n }\n }\n}\n```\n\nRemarks:\n\n1. The `kth` smallest fraction is known to be in the range `[0, 1]`, so we initialize the search space with this range (i.e., `l = 0` and `r = 1`).\n\n2. We need the pair `(p, q)` to record the maximum fraction in the matrix that is no greater than each candidate solution. This is necessary because on the one hand, the candidate solution itself cannot tell us what the numerator and denominator of the fraction are (remember the candidate solution is just a floating-point number); on the other hand, even if we can get the numerator and denominator of the candidate solution, these values may not be contained in the input array (remember all the fractions must be formed by pair of integers from the input array). This is different from the case when the matrix elements are integers, where at the end of the binary search, the candidate solution must be equal to the `kth` smallest element in the matrix.\n\n3. The above solution only works when there are no duplicate fractions in the matrix (which is indeed the case for prime fractions). Otherwise, we need two counts, `cnt_le` and `cnt_lt`, to account for duplicates, similar to what we did in the ZigzagSearch solution below.\n\n4. The time complexity is computed as follows: the binary search loop will terminate when the count of elements no greater than a candidate solution reaches `K`. This is guaranteed to happen when the size of the search range `[l, r]` becomes smaller than the smallest absolute distance between any pair of fractions in the matrix, which is `>= 1/MAX^2`. Since each iteration will reduce the search range by half, the binary search loop will terminate after at most `log(MAX^2)` steps. Each iteration is done in linear time, therefore the total time complexity is `O(n * log(MAX^2))`, which is equivalent to `O(n * log(MAX))`.\n\n
\n\n**SOLUTION THREE** -- Using ZigzagSearch\n\n* Time complexity: `O(n^2)`\n* Space complexity: `O(1)`\n\n```\npublic int[] kthSmallestPrimeFraction(int[] A, int K) {\n int n = A.length;\n \n int row = 0; \n int col = n - 1;\n \n for (int cnt_le = 0, cnt_lt = 0; true; cnt_le = 0, cnt_lt = 0) {\n for (int i = 0, j = n - 1, p = n - 1; i < n; i++) {\n while (j >= 0 && A[i] * A[n - 1 - col] > A[n - 1 - j] * A[row]) j--;\n cnt_le += (j + 1);\n \n while (p >= 0 && A[i] * A[n - 1 - col] >= A[n - 1 - p] * A[row]) p--;\n cnt_lt += (p + 1);\n }\n \n if (cnt_le < K) {\n row++;\n } else if (cnt_lt >= K) {\n col--;\n } else {\n return new int[] {A[row], A[n - 1 - col]};\n }\n }\n}\n```\n\nRemarks:\n\n1. We no longer need to keep track of the largest fraction in the matrix that is no greater than each candidate solution, because now all the candidate solutions are formed by integer pairs from the input array itself.\n\n2. The above solution can be further optimized due to the fact that there are no duplicates in the fraction matrix. This implies we always have `cnt_lt = cnt_le - 1`, therefore the loop for conuting `cnt_lt` can be dropped. You may refer to [lixx2100\'s comment](https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115486/Java-AC-O(max(nk)-*-logn)-Short-Easy-PriorityQueue/116025) for more information.\n\n---\n\n\nHope you enjoy these solutions and happy coding!

K-th Smallest Prime Fraction

Problem Description

Problem Description

Answer Panel