<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 BIT {
    public:
    int size;
    vector<int> table;
    BIT(int n)
    {
        this->size = n+1;
        table.resize(size+1,0);
    }
    void update(int i, int delta)
    {
        i++;
        while(i<size)
        {
            table[i] += delta;
            i += (i&(-i));
        }
    }
    int sum(int i)
    {
        i++;
        int sum = 0;
        while(i>0)
        {
            sum += table[i];
            i -= (i&(-i));
        }
        return sum;
    }
    int rangeQuery(int i,int j) {return sum(j) - sum(i-1);}

};
class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size();
        int s = 0;
        int maxi = -1;
        int mini = 1e9;
        for(auto it:nums)
        {
            maxi = max(maxi, it);
            mini = min(mini, it);
        }
        int e = maxi-mini;
        int mid = (s+e)/2;
        const int target = (n*(n-1))/2 - k; 
        int ans;
        while(s<=e)
        {
            int biggerCount = 0;
            int equalCount = 0;
            BIT b(maxi+1);
            for(int i=n-1;i>=0;i--)
            {
                int element = nums[i];
                if(element+mid+1 <= maxi) biggerCount += b.rangeQuery(element+mid+1,maxi);
                if(element-mid-1 >= 0) biggerCount += b.rangeQuery(0,element-mid-1);
                if(element+mid <= maxi) equalCount += b.rangeQuery(element+mid,element+mid);
                if(element-mid >=0) equalCount += b.rangeQuery(element-mid,element-mid);
                b.update(element,1);
            }
            int maxAheadCount = max(equalCount-1,0) + biggerCount;
            int minAheadCount = biggerCount;
            if(target>=minAheadCount && target<=maxAheadCount) 
            {
                ans = mid;
                break;
            }
            else if(target<minAheadCount) s = mid+1;
            else e = mid-1;
            mid = (s+e)/2;
        }
        set<int> st(nums.begin(), nums.end());
        int smallestDiff = 1e9;
        for(int i=0;i<n;i++)
        {
            int element = nums[i];
            auto it = st.upper_bound(element+ans);
            if(it==st.begin()) continue;
            it--;
            smallestDiff = min(smallestDiff,element + ans - *it);
        }
        return ans - smallestDiff;
    }
};
213195