Problem

You are given an array of integers nums and an integer k.

An inversion pair with a threshold x is defined as a pair of indices (i, j) such that:

  • i < j
  • nums[i] > nums[j]
  • The difference between the two numbers is at most x (i.e. nums[i] - nums[j] <= x).

Your task is to determine the minimum integer min_threshold such that there are at least k inversion pairs with threshold min_threshold.

If no such integer exists, return -1.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

Input: nums = [1,2,3,4,3,2,1], k = 7

Output: 2

Explanation:

For threshold x = 2, the pairs are:

(3, 4) where nums[3] == 4 and nums[4] == 3.
(2, 5) where nums[2] == 3 and nums[5] == 2.
(3, 5) where nums[3] == 4 and nums[5] == 2.
(4, 5) where nums[4] == 3 and nums[5] == 2.
(1, 6) where nums[1] == 2 and nums[6] == 1.
(2, 6) where nums[2] == 3 and nums[6] == 1.
(4, 6) where nums[4] == 3 and nums[6] == 1.
(5, 6) where nums[5] == 2 and nums[6] == 1.
There are less than k inversion pairs if we choose any integer less than 2 as threshold.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input: nums = [10,9,9,9,1], k = 4

Output: 8

Explanation:

For threshold x = 8, the pairs are:

(0, 1) where nums[0] == 10 and nums[1] == 9.
(0, 2) where nums[0] == 10 and nums[2] == 9.
(0, 3) where nums[0] == 10 and nums[3] == 9.
(1, 4) where nums[1] == 9 and nums[4] == 1.
(2, 4) where nums[2] == 9 and nums[4] == 1.
(3, 4) where nums[3] == 9 and nums[4] == 1.
There are less than k inversion pairs if we choose any integer less than 8 as threshold.

Constraints

  • 1 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

Solution

Method 1 – Binary Search + BIT (Fenwick Tree)

Intuition

We want the minimum threshold T such that the number of inversion pairs (i < j, nums[i] > nums[j] + T) is at least k. For each T, we can count such pairs efficiently using a Binary Indexed Tree (BIT) by iterating from right to left and querying how many nums[j] < nums[i] - T.

Approach

  1. Binary search T in a reasonable range (e.g., from 0 to max(nums)).
  2. For each T, count inversion pairs using BIT:
    • Iterate nums from right to left.
    • For each nums[i], query BIT for count of nums[j] < nums[i] - T.
    • Update BIT with nums[i].
  3. If count >= k, T is feasible; search for smaller T.
  4. Return the minimal feasible T.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <vector>
#include <algorithm>
class BIT {
    std::vector<int> tree;
public:
    BIT(int n): tree(n+2,0) {}
    void add(int i) { for(++i;i<tree.size();i+=i&-i) tree[i]++; }
    int sum(int i) { int s=0; for(++i;i>0;i-=i&-i) s+=tree[i]; return s; }
};
class Solution {
public:
    int minThreshold(std::vector<int>& nums, int k) {
        int n = nums.size();
        std::vector<int> vals = nums;
        std::sort(vals.begin(), vals.end());
        int l = 0, r = *std::max_element(nums.begin(), nums.end());
        while (l < r) {
            int T = (l + r) / 2, cnt = 0;
            BIT bit(n);
            for (int i = n-1; i >= 0; --i) {
                int idx = std::lower_bound(vals.begin(), vals.end(), nums[i]-T) - vals.begin() - 1;
                if (idx >= 0) cnt += bit.sum(idx);
                bit.add(std::lower_bound(vals.begin(), vals.end(), nums[i]) - vals.begin());
            }
            if (cnt >= k) r = T;
            else l = T+1;
        }
        return l;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int minThreshold(int[] nums, int k) {
        int n = nums.length;
        int[] vals = nums.clone();
        Arrays.sort(vals);
        int l = 0, r = Arrays.stream(nums).max().getAsInt();
        while (l < r) {
            int T = (l + r) / 2, cnt = 0;
            BIT bit = new BIT(n);
            for (int i = n-1; i >= 0; i--) {
                int idx = Arrays.binarySearch(vals, nums[i]-T);
                if (idx < 0) idx = -idx-2;
                else idx--;
                if (idx >= 0) cnt += bit.sum(idx);
                bit.add(Arrays.binarySearch(vals, nums[i]));
            }
            if (cnt >= k) r = T;
            else l = T+1;
        }
        return l;
    }
    static class BIT {
        int[] tree;
        BIT(int n) { tree = new int[n+2]; }
        void add(int i) { for(++i;i<tree.length;i+=i&-i) tree[i]++; }
        int sum(int i) { int s=0; for(++i;i>0;i-=i&-i) s+=tree[i]; return s; }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def minThreshold(self, nums: list[int], k: int) -> int:
        vals = sorted(nums)
        n = len(nums)
        def count(T: int) -> int:
            bit = [0]*(n+2)
            def add(i):
                i += 1
                while i < len(bit): bit[i] += 1; i += i & -i
            def sum_(i):
                i += 1; s = 0
                while i > 0: s += bit[i]; i -= i & -i
                return s
            cnt = 0
            for i in range(n-1,-1,-1):
                idx = bisect.bisect_left(vals, nums[i]-T)-1
                if idx >= 0: cnt += sum_(idx)
                add(bisect.bisect_left(vals, nums[i]))
            return cnt
        l, r = 0, max(nums)
        while l < r:
            T = (l+r)//2
            if count(T) >= k: r = T
            else: l = T+1
        return l
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun minThreshold(nums: IntArray, k: Int): Int {
        val vals = nums.sorted()
        val n = nums.size
        fun count(T: Int): Int {
            val bit = IntArray(n+2)
            fun add(i: Int) { var idx=i+1; while(idx<bit.size){bit[idx]++;idx+=idx and -idx} }
            fun sum(i: Int): Int { var idx=i+1; var s=0; while(idx>0){s+=bit[idx];idx-=idx and -idx}; return s }
            var cnt = 0
            for (i in n-1 downTo 0) {
                val idx = vals.binarySearch(nums[i]-T).let{if(it<0)-it-2 else it-1}
                if (idx >= 0) cnt += sum(idx)
                add(vals.binarySearch(nums[i]).let{if(it<0)-it-1 else it})
            }
            return cnt
        }
        var l = 0; var r = nums.maxOrNull()!!
        while (l < r) {
            val T = (l+r)/2
            if (count(T) >= k) r = T else l = T+1
        }
        return l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn min_threshold(nums: Vec<i32>, k: i32) -> i32 {
        let mut vals = nums.clone(); vals.sort();
        let n = nums.len();
        fn count(nums: &Vec<i32>, vals: &Vec<i32>, T: i32) -> i32 {
            let mut bit = vec![0;n+2];
            let mut cnt = 0;
            for i in (0..nums.len()).rev() {
                let idx = match vals.binary_search(&(nums[i]-T)) {
                    Ok(x) => x-1,
                    Err(x) => x-1,
                };
                if idx >= 0 { let mut s=0; let mut j=idx+1; while j>0{ s+=bit[j]; j-=j&-j }; cnt+=s; }
                let mut j = match vals.binary_search(&nums[i]) { Ok(x)=>x, Err(x)=>x }+1;
                while j<bit.len() { bit[j]+=1; j+=j&-j; }
            }
            cnt
        }
        let (mut l, mut r) = (0, *nums.iter().max().unwrap());
        while l < r {
            let T = (l+r)/2;
            if count(&nums, &vals, T) >= k { r = T; } else { l = T+1; }
        }
        l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    minThreshold(nums: number[], k: number): number {
        const vals = [...nums].sort((a,b)=>a-b)
        const n = nums.length
        function count(T: number): number {
            const bit = Array(n+2).fill(0)
            function add(i: number) { i++; while(i<bit.length){bit[i]++;i+=i&-i} }
            function sum(i: number) { i++; let s=0; while(i>0){s+=bit[i];i-=i&-i}; return s }
            let cnt = 0
            for (let i=n-1;i>=0;i--) {
                let idx = vals.findIndex(v=>v>=nums[i]-T)-1
                if (idx >= 0) cnt += sum(idx)
                add(vals.findIndex(v=>v>=nums[i]))
            }
            return cnt
        }
        let l = 0, r = Math.max(...nums)
        while (l < r) {
            let T = Math.floor((l+r)/2)
            if (count(T) >= k) r = T
            else l = T+1
        }
        return l
    }
}

Complexity

  • ⏰ Time complexity: O(n log n log M) — n for each count, log n for BIT, log M for binary search range.
  • 🧺 Space complexity: O(n) — For BIT and value compression.