# From simple to deluxe, evolution of abstraction and c++ solutions

• Simple solution, nested binary searches:

``````int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int l, r;
for (l = 0, r = nums.back() - nums.front(); l < r;) {
int m = l + (r - l) / 2, s = 0;
for (int i = 0; i < nums.size(); i++) {
int l2, r2, t = nums[i] + m;
for (l2 = i, r2 = nums.size(); l2 < r2;) {
int m2 = l2 + (r2 - l2) / 2;
if (nums[m2] <= t)
l2 = m2 + 1;
else
r2 = m2;
}
s += l2 - i - 1;
}
if (s < k)
l = m + 1;
else
r = m;
}
return l;
}
``````

Reinvent the binary_search stl function:

``````template<class Compare>
int binary_search(int first, int last, Compare cmp) {
while (first < last) {
int mid = first + (last - first) / 2;
if (cmp(mid))
first = mid + 1;
else
last = mid;
}
return first;
}

int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return binary_search(0, nums.back() - nums.front(), [&](int m) {
int s = 0;
for (int i = 0; i < nums.size(); i++)
s += binary_search(i, nums.size(), [&](int m2) {
return nums[m2] <= nums[i] + m;
}) - i - 1;
return s < k;
});
}
``````

One step further:

``````template<class Compare>
int binary_search(int first, int last, Compare cmp) {
while (first < last) {
int mid = first + (last - first) / 2;
if (cmp(mid))
first = mid + 1;
else
last = mid;
}
return first;
}

template<class Data, class T>
int lower_bound(Data &data, int first, int last, T val) {
return binary_search(first, last, [&](int mid) {
return data[mid] < val;
});
}

template<class Data, class T>
int upper_bound(Data &data, int first, int last, T val) {
return binary_search(first, last, [&](int mid) {
return !(val < data[mid]);
});
}

int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return binary_search(0, nums.back() - nums.front(), [&](int m) {
int s = 0;
for (int i = 0; i < nums.size(); i++)
s += upper_bound(nums, i, nums.size(), nums[i] + m) - i - 1;
return s < k;
});
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.