I like to read this solution as a small machine: keep the useful information, throw away the noise. For 719. Find K-th Smallest Pair Distance, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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
- 16 / 19 test cases passed.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findSmallerDistances, smallestDistancePair, multiplicity, prefix.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- 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.
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) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//16 / 19 test cases passed.
03class Solution {
04public:
05 priority_queue<int, vector<int>> pq;
06
07 int findSmallerDistances(vector<int>& nums, int& target){
08 pq = priority_queue<int, vector<int>>(); //clear
09 int n = nums.size();
10
11 for(int i = 0; i < n; i++){
12 for(int j = i+1; j < n; j++){
13 if(nums[j] - nums[i] <= target){
14 pq.push(nums[j] - nums[i]);
15 }
16 }
17 }
18
19 return pq.size();
20 };
21
22 int smallestDistancePair(vector<int>& nums, int k) {
23 int left = 0;
24 int right = *max_element(nums.begin(), nums.end()) - *min_element(nums.begin(), nums.end());
25
26 sort(nums.begin(), nums.end());
27
28 int mid, val;
29
30 while(left <= right){
31 mid = left + (right - left)/2;
32
33 // cout << left << ", " << mid << ", " << right << ": ";
34
35 int smallerCount = findSmallerDistances(nums, mid);
36
37 // cout << val << endl;
38
39 if(smallerCount == k){
40 return pq.top();
41 }else if(smallerCount < k){
42 left = mid+1;
43 }else if(smallerCount > k){
44 right = mid-1;
45 while(pq.size() > k){
46 pq.pop();
47 }
48 return pq.top();
49 }
50 }
51
52 while(pq.size() > k){
53 pq.pop();
54 }
55
56 return pq.top();
57 }
58};
59
60//Approach #1: Heap [Time Limit Exceeded]
61//TLE
62//16 / 19 test cases passed.
63//time: push: O(NlogN) + pop: O(klogN) -> O((N+k)logN)
64//space: O(N)
65class Solution {
66public:
67 int smallestDistancePair(vector<int>& nums, int k) {
68 sort(nums.begin(), nums.end());
69
70 auto comp = [&nums](const vector<int>& a, const vector<int>& b){
71 //use > because we want the smaller to be popped earlier
72 return nums[a[1]] - nums[a[0]] > nums[b[1]] - nums[b[0]];
73 };
74 priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);
75
76 int n = nums.size();
77 for(int i = 0; i+1 < n; i++){
78 pq.push(vector<int>{i, i+1});
79 // cout << i << ", " << i+1 << endl;
80 }
81
82 vector<int> cur;
83 k--;
84 //pop first k-1 pairs
85 while(k-- > 0){
86 cur = pq.top(); pq.pop();
87 // cout << cur[0] << ", " << cur[1] << endl;
88 if(cur[1]+1 < n){
89 pq.push({cur[0], cur[1]+1});
90 }
91 }
92 //the kth pair
93 cur = pq.top();
94 // cout << "final: " << cur[0] << ", " << cur[1] << endl;
95
96 return nums[cur[1]] - nums[cur[0]];
97 }
98};
99
100//not understand
101//Approach #2: Binary Search + Prefix Sum [Accepted]
102//Runtime: 56 ms, faster than 22.59% of C++ online submissions for Find K-th Smallest Pair Distance.
103//Memory Usage: 36.9 MB, less than 8.33% of C++ online submissions for Find K-th Smallest Pair Distance.
104//time: sort: O(NlogN) + set "prefix": O(W) + binary search: O(logW * N), W = nums[n-1] - nums[0]
105//space: O(W+N)
106class Solution {
107public:
108 int smallestDistancePair(vector<int>& nums, int k) {
109 sort(nums.begin(), nums.end());
110 int n = nums.size();
111 int width = 2 * nums[n-1];
112
113 vector<int> multiplicity(n);
114 //multiplicity[i]: before nums[i], there are how many element equal to nums[i]
115 // cout << "multiplicity: " << endl;
116 for(int i = 1; i < n; i++){
117 if(nums[i] == nums[i-1]){
118 multiplicity[i] = 1 + multiplicity[i-1];
119 }
120 // cout << multiplicity[i] << " ";
121 }
122 // cout << endl;
123
124 //prefix[i]: how many numbers in nums <= i
125 vector<int> prefix(width);
126 // cout << "prefix: " << endl;
127 int l = 0;
128 for(int i = 0; i < width; i++){
129 while(l < n && nums[l] == i) l++;
130 prefix[i] = l;
131 // cout << prefix[i] << " ";
132 }
133 // cout << endl;
134
135 int left = 0;
136 int right = nums[n-1] - nums[0];
137 int mid;
138 int count;
139
140 while(left <= right){
141 mid = left + (right-left)/2;
142 // cout << "left: " << left << ", mid: " << mid << ", right: " << right << endl;
143 //count[i]: the count of j (j>i) s.t. nums[j] - nums[i] <= mid
144 count = 0;
145 for(int i = 0; i < n; i++){
146 //multiplicity[i] = count[i] - multiplicity[i]?
147 count += prefix[nums[i]+mid] - prefix[nums[i]] + multiplicity[i];
148 // cout << "prefix[" << nums[i]+mid << "]: " << prefix[nums[i]+mid] << ", prefix[" << nums[i] << "]: " << prefix[nums[i]] << ", multiplicity[" << i << "]: " << multiplicity[i] << ", add: " << prefix[nums[i]+mid] - prefix[nums[i]] + multiplicity[i] << ", count: " << count << endl;
149 }
150
151 if(count >= k) right = mid-1;
152 else left = mid+1;
153 }
154
155 return left;
156 }
157};
158
159//Approach #3: Binary Search + Sliding Window [Accepted]
160//Runtime: 20 ms, faster than 77.27% of C++ online submissions for Find K-th Smallest Pair Distance.
161//Memory Usage: 10 MB, less than 8.33% of C++ online submissions for Find K-th Smallest Pair Distance.
162//time: sort: O(NlogN) + binary search: O(logW * N), W = nums[n-1] - nums[0]
163//space: O(1)
164class Solution {
165public:
166 int smallestDistancePair(vector<int>& nums, int k) {
167 sort(nums.begin(), nums.end());
168 int n = nums.size();
169
170 int left = 0;
171 int right = nums[n-1] - nums[0];
172 int mid;
173 int count;
174
175 while(left <= right){
176 mid = left + (right-left)/2;
177 // cout << "left: " << left << ", mid: " << mid << ", right: " << right << endl;
178 count = 0;
179 int slow = 0;
180 for(int fast = 0; fast < n; fast++){
181 //notice that "slow" pointer increases monotonically for increasing "fast" pointer!
182 while(nums[fast] - nums[slow] > mid) slow++;
183 count += (fast-slow);
184 // cout << "[" << slow << ", " << fast << "], count: " << count << endl;
185 }
186
187 if(count >= k) right = mid-1;
188 else left = mid+1;
189 }
190
191 return left;
192 }
193};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.