Find the kth smallest number obtained by subtracting two element in sorted array

It is unclear to me how you intend to handle duplicate differences. Consider the array {1, 2, 3, 4}. Do you say that the differences are {1, 2, 3}? Or would you say that they are {1, 1, 1, 2, 2, 3}?

If the latter, then the following code will take average time O(n log(n)) and worst case time O(n log(n)^2). It is based on a binary search of the differences.

I am ahem not a C++ programmer.

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

template <typename my_type>
my_type kth_diff(my_type a[], int n, int k) {
    // {j, {m, n}} represents a[m] - a[j], a[m+1] - a[j], ..., a[n] - a[j]
    vector<pair<int, pair<int, int>>> diff_range;
    for (int i = 0; i+1 < n; i++) {
        diff_range.push_back({i, {i+1, n-1}});
    }

    while (0 < diff_range.size()) {
        int i = diff_range[0].first;
        int j = (diff_range[0].second.first + diff_range[0].second.second)/2;
        my_type pivot = a[j] - a[i];

        // And back up over the max values that make a pivot.
        while (0 < j && a[j-1] == a[j]) {
            j--;
        }

        int count_below = 0;
        int count_at = 0;
        vector<pair<int, pair<int, int>>> diff_range_low;
        vector<pair<int, pair<int, int>>> diff_range_high;

        vector<pair<int, pair<int, int>>>::iterator it;
        for (it = diff_range.begin(); it != diff_range.end(); it++) {
            i = it->first;
            j = max(it->second.first, j);
            while (j < n && a[j] - a[i] < pivot) {
                j++;
            }
            count_below += j - it->second.first;
            if (it->second.first < j) {
                // If the pivot is too small, use this.
                diff_range_low.push_back({i, {it->second.first, j-1}});
            }

            while (j < n && a[j] - a[i] == pivot) {
                j++;
                count_at++;
            }
            if (j <= it->second.second) {
                // If the pivot is too big, use this.
                diff_range_high.push_back({i, {j, it->second.second}});
            }
        }

        if (count_below + count_at <= k) {
            // We only need to count ranges past the pivot.
            diff_range = diff_range_high;
            // Keep track of the number below that are accounted for.
            k -= count_below + count_at;
        }
        else if (k < count_below) {
            // We only need to count ranges before the pivot.
            diff_range = diff_range_low;
        }
        else {
            return pivot;
        }
    }

    return a[0];
}

int main() {
    int a[] = {1,4,9,16};
    int n = sizeof(a) / sizeof(a[0]);
    for (int k = 0; k <  n*(n-1)/2; k++) {
        cout << k << "\t" << kth_diff(a, n, k) << endl;
    }
}

I look at this problem like this.

For [a,b,c,d] such a<b<c<d and x,y,z>0 and b = a+x, c = b+y, d=c+z, then b-a = x, c-b = y, c-a = x+y, d-b = y+z, d-a = x+y+z. What does it tell us? The more apart are the elements the bigger the difference, and it adds up with every step.

It is unknown if x<y or x>y but for sure x+y>x and x+y>y, so your differences can be divided into distance classes.

diff_1 = {d-c,c-b,b-a}, diff_2 = {d-b,c-a}, diff_3={d-a}

now what you probably can see by now is min(diff_1) < min(diff_2) < min(diff_3), so to find the second smallest difference you don't need to check for min(diff_3) because it is at best the third smallest element.

So what you do is to implement something like this pseudocode:

int findLeastDiff<k>(std::vector<int> v)
{
  assert(v_contains_k_distinct_elements(v));
  std::vector<int> result;
  std::sort(v.begin(),v.end()); // O(nlog(n));
  v.erase(std::unique(v.begin(),v.end()),v.end()); // O(n)
  for<<int i=1; i<=k; ++i>>
  {
     adjacent_difference<i>(v.begin(), v.end(), std::back_inserter(result));// O(n-i)
  } // O(k(n-k/2)) = O(k*n)
  std::sort(result.begin(), result.begin());  // O(nlog(n));
  result.erase(std::unique(result.begin(),result.end()),result.end()); // O(n)
  return result[k];
}

The above is just a concept and for sure can be optimized a lot. What is the complexity? O(nlog(n)+n+k*n+nlog(n)+n) = O((2log(n)+k+2)*n)

It probably can be optimized with some clever way of reducing the search space by removing ranges with already too big differances.