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 < jnums[i] > nums[j]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.
Example 1:
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:
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 <= 1041 <= nums[i] <= 1091 <= k <= 109Problem Overview: You are given an array and a target number of inversion pairs. The goal is to determine the smallest threshold value T such that the array contains at least the required number of inversion pairs where the difference between elements exceeds that threshold. A pair (i, j) is considered when i < j and the value relationship satisfies the inversion condition relative to T.
Approach 1: Brute Force Pair Enumeration (O(n²) time, O(1) space)
Check every pair (i, j) where i < j. For a chosen threshold T, evaluate whether the pair forms a valid inversion according to the problem condition and count it. Repeat this check for different threshold values until the minimum valid threshold is found. This approach is straightforward and useful for understanding the inversion definition, but the nested iteration over all pairs makes it impractical for large inputs.
Approach 2: Binary Search on Threshold + Fenwick Tree (O(n log n log V) time, O(n) space)
The key insight is that the number of valid inversion pairs changes monotonically with the threshold. Larger thresholds reduce the number of qualifying pairs, which allows a binary search over possible threshold values. For each candidate threshold, scan the array and count valid pairs efficiently using a Binary Indexed Tree. Coordinate compression maps values into a compact index range. As you iterate through the array, query the Fenwick Tree to determine how many previous elements form valid inversions with the current element, then update the structure with the current value. This reduces pair counting from quadratic to logarithmic per operation.
Approach 3: Binary Search + Segment Tree (O(n log n log V) time, O(n) space)
A Segment Tree can replace the Fenwick Tree for range frequency queries. After compressing values, the tree maintains counts of previously processed elements. During the scan, perform a range query to count elements that satisfy the inversion condition relative to the current number and threshold. Then update the tree at the compressed index of the current value. Segment trees are slightly heavier than Fenwick Trees but support more flexible range operations if the inversion condition becomes more complex.
Recommended for interviews: Binary search combined with a Fenwick Tree is the expected solution. The brute force approach shows you understand how inversion pairs are defined, but the optimized method demonstrates the ability to combine monotonic search with efficient frequency queries. Interviewers typically look for the insight that the answer space can be binary searched while inversion counting is handled with a logarithmic data structure.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n²) | O(1) | Small arrays or when validating the inversion definition |
| Binary Search + Fenwick Tree | O(n log n log V) | O(n) | General optimal solution for large inputs |
| Binary Search + Segment Tree | O(n log n log V) | O(n) | Useful when extended range queries or modifications are required |
Practice Minimum Threshold for Inversion Pairs Count with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor