<p>The <strong>distance of a pair</strong> of integers <code>a</code> and <code>b</code> is defined as the absolute difference between <code>a</code> and <code>b</code>.</p>

<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the</em> <code>k<sup>th</sup></code> <em>smallest <strong>distance among all the pairs</strong></em> <code>nums[i]</code> <em>and</em> <code>nums[j]</code> <em>where</em> <code>0 &lt;= i &lt; j &lt; nums.length</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,1], k = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> Here are all the pairs:
(1,3) -&gt; 2
(1,1) -&gt; 0
(3,1) -&gt; 2
Then the 1<sup>st</sup> smallest distance pair is (1,1), and its distance is 0.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1], k = 2
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,6,1], k = 3
<strong>Output:</strong> 5
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= k &lt;= n * (n - 1) / 2</code></li>
</ul>

class Solution {
  vector<int> st;
  int mx = 1e6+1;

  void add(int num)
  {
    int N = st.size() >> 1;
    st[num += N] += 1;

    while(num >>= 1)
    {
      st[num] = st[num<<1] + st[num<<1|1];
    }
  }

  int sum(int begin, int end)
  {
    int N = st.size() >> 1;
    begin += N;
    end += N;

    int result = 0;
    while(begin < end)
    {
      if(end & 1)   { result += st.at(--end);   }
      if(begin & 1) { result += st.at(begin++); }

      begin >>= 1;
      end >>= 1;
    }

    return result;
  }

  int countPairsWithDiffLessEqThan(const vector<int>& nums, int threshold)
  {
    ranges::fill(st, 0);

    int count = 0;
    for(int idx = 0;idx < nums.size();++idx)
    {
      // prev is smaller: 1. prev < nums[idx]
      //                  2. nums[idx] - prev <= threshold
      //                  => nums[idx] > prev >= nums[idx] - threshold
      count += sum(max(nums[idx] - threshold, 0), nums[idx]);

      // prev is larger or equal:  1. prev >= nums[idx]
      //                           2. prev - nums[idx] <= threshold
      //                           => nums[idx] <= prev <= nums[idx] + threshold
      count += sum(nums[idx], min(nums[idx] + threshold + 1, mx));

      add(nums[idx]);
    }

    return count;
  }

public:
    int smallestDistancePair(vector<int>& nums, int k) {
      st.resize(2*mx);
      auto [mnItr, mxItr] = minmax_element(nums.begin(), nums.end());

      int begin = 0; int end = *mxItr - *mnItr + 1;

      while(begin != end)
      {
        int mid = begin + (end - begin)/2;
        int c = countPairsWithDiffLessEqThan(nums, mid);

        if(c < k) { begin = mid+1; }
        else      { end = mid;     }
      }

      return begin;
    }
};

125175