Let's make this one less mysterious. For 786. K-th Smallest Prime Fraction, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue, binary search, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- TLE
- 53 / 62 test cases passed.
- heap
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are kthSmallestPrimeFraction.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O((n + K) * logn), with n = A.length
- Space: O(n)
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//53 / 62 test cases passed.
03//heap
04class Solution {
05public:
06 priority_queue<double, vector<double>> pq;
07
08 vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
09 priority_queue<vector<double>, vector<vector<double>>, greater<vector<double>>> pq;
10 int n = A.size();
11
12 for(int i = 0; i < n; i++){
13 pq.push({(double)A[i]/A[n-1], (double)i, n-1.0});
14 }
15
16 // cout << endl;
17
18 K--;
19 while(!pq.empty() && K--){
20 vector<double> cur = pq.top(); pq.pop();
21 double value = cur[0];
22 int nomIdx = cur[1], denomIdx = cur[2];
23 // cout << A[nomIdx] << "/" << A[denomIdx] << ":" << value << " ";
24
25 if(denomIdx != 0){
26 pq.push({(double)A[nomIdx]/A[denomIdx-1], (double)nomIdx, denomIdx-1.0});
27 }
28 }
29
30 return {A[(int)pq.top()[1]], A[(int)pq.top()[2]]};
31 }
32};
33
34//heap, mapped to "Kth Smallest Element in a Sorted Matrix"
35//https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115819/Summary-of-solutions-for-problems-%22reducible%22-to-LeetCode-378
36//TLE
37//53 / 62 test cases passed.
38//time: O((n + K) * logn), with n = A.length
39//space: O(n)
40class Solution {
41public:
42 vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
43 auto comp = [&A](vector<int>& a, vector<int>& b){
44 //first coord represents for nominator, accessing A
45 //second coord represents for denominator, accessing reversed A
46
47 // return A[a[0]]/A[A.size()-1-a[1]] > A[b[0]]/A[A.size()-1-b[1]];
48 return A[a[0]]*A[A.size()-1-b[1]] > A[b[0]]*A[A.size()-1-a[1]];
49 };
50
51 priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);
52 int n = A.size();
53
54 for(int i = 0; i < n; i++){
55 /*
56 For A = {1,2,3,5}, we build a matrix:
57 5 3 2 1
58 1 1/5 1/3 1/2 1/1
59 2 2/5 2/3 2/2 2/1
60 3 3/5 3/3 3/2 3/1
61 5 5/5 5/3 5/2 5/1
62
63 Which uses rows to represent nominator,
64 cols(in reverse order) to represent denominator,
65 so that every row is sorted, ascending
66 also every col is sorted, ascending
67
68 (coord for nominator, coord for denominator)
69 */
70 pq.push({i, 0});
71 }
72
73 vector<int> cur;
74 while(K-- > 0){
75 cur = pq.top(); pq.pop();
76 // cout << "pop: " << cur[0] << ", " << cur[1] << endl;
77 if(cur[1]+1 < n){
78 // cout << "push: " << cur[0] << ", " << cur[1]+1 << endl;
79 pq.push({cur[0], cur[1]+1});
80 }
81 }
82
83 //second coord is the index of reversed A!
84 return {A[cur[0]], A[A.size()-1-cur[1]]};
85 }
86};
87
88//binary search, can only be used when there is no duplicate elements
89//https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115819/Summary-of-solutions-for-problems-%22reducible%22-to-LeetCode-378
90//Runtime: 16 ms, faster than 77.92% of C++ online submissions for K-th Smallest Prime Fraction.
91//Memory Usage: 9.9 MB, less than 100.00% of C++ online submissions for K-th Smallest Prime Fraction.
92//time: O(n * log(MAX^2)), where MAX is the maximum element in A //?
93//space: O(1)
94class Solution {
95public:
96 vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
97 //the range of prime fraction
98 double left = 0, right = 1;
99 double mid;
100 //numerator and denominator of candidate answer
101 int numerator = 0, denominator = 1;
102 int n = A.size();
103
104 while(left < right){
105 mid = (left + right)/2.0;
106
107 //count of fractions <= mid
108 int count = 0;
109 numerator = 0; //make sure "A[n-1-j] * numerator" will be smaller than any number initially!
110 for(int i = 0, j = n -1; j >= 0 && i< n; i++){
111 // cout << i << ", " << j << ", " << (double)A[i]/A[n-1-j] << endl;
112 // while(j >= 0 && (double)A[i]/A[n-1-j] > mid) j--;
113 while(j >= 0 && A[i] > mid*A[n-1-j]) j--;
114 //now A[i]/A[j] <= mid
115 count += (j+1);
116 //if((double)A[i]/A[j] > (double)numerator/denominator){
117 if(j >= 0 && A[i]*denominator > A[n-1-j] * numerator){
118 numerator = A[i];
119 denominator = A[n-1-j];
120 }
121 // cout << numerator << "/" << denominator << endl;
122 }
123
124 // cout << "count: " << count << endl;
125
126 if(count == K){
127 return {numerator, denominator};
128 }else if(count < K){
129 left = mid;
130 }else if(count > K){
131 right = mid;
132 }
133 }
134
135 return {0, 0};
136 }
137};
138
139//Zigzag Search
140//https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115819/Summary-of-solutions-for-problems-%22reducible%22-to-LeetCode-378
141//Runtime: 472 ms, faster than 27.50% of C++ online submissions for K-th Smallest Prime Fraction.
142//Memory Usage: 9.9 MB, less than 100.00% of C++ online submissions for K-th Smallest Prime Fraction.
143//time: O(N^2), space: O(1)
144class Solution {
145public:
146 vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
147 int n = A.size();
148
149 int row = 0, col = n-1;
150 int count_lt, count_le;
151
152 /*
153 For A = {1,2,3,5}, we build a matrix:
154 5 3 2 1
155 1 1/5 1/3 1/2 1/1
156 2 2/5 2/3 2/2 2/1
157 3 3/5 3/3 3/2 3/1
158 5 5/5 5/3 5/2 5/1
159 */
160
161 while(row < n && col >= 0){
162 count_lt = 0; //number of elements < A[row]/A[n-1-col]
163 count_le = 0; //number of elements <= A[row]/A[n-1-col]
164 for(int i = 0, j1 = n-1, j2 = n-1; i < n; i++){
165 // while(j1 >= 0 && (double)A[i]/A[n-1-j1] > (double)A[row]/A[n-1-col]) j1--;
166 while(j1 >= 0 && A[i]*A[n-1-col] > A[row]*A[n-1-j1]) j1--;
167 count_le += (j1+1);
168
169 // //while(j2 >= 0 && (double)A[i]/A[n-1-j2] >= (double)A[row]/A[n-1-col]) j2--;
170 // while(j2 >= 0 && A[i]*A[n-1-col] >= A[row]*A[n-1-j2]) j2--;
171 // count_lt += (j2+1);
172 }
173
174 /*
175 in our case, the matrix doesn't contain duplicate elements,
176 so count_lt = count_le - 1 always holds,
177 we may drop the loop counting count_lt
178 */
179
180 count_lt = count_le-1;
181
182 if(count_le < K){
183 row++;
184 }else if(count_lt >= K){
185 col--;
186 }else{
187 return {A[row], A[n-1-col]};
188 }
189 }
190
191 return {-1,-1};
192 }
193};Cost
Complexity
Time
O((n + K) * logn), with n = A.length
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n)
Auxiliary state plus the answer structure where the problem requires one.