Skip to content

3520. Minimum Threshold for Inversion Pairs Count

  • Time: $O(n\log\max(\texttt{nums}))$
  • Space: $O(1)$
 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
31
32
33
class Solution {
 public:
  int minThreshold(vector<int>& nums, int k) {
    const int mx = ranges::max(nums);
    int l = 0;
    int r = mx + 1;

    while (l < r) {
      const int m = (l + r) / 2;
      if (countInversionPairs(nums, k, m))
        r = m;
      else
        l = m + 1;
    }

    return l > mx ? -1 : l;
  }

 private:
  bool countInversionPairs(const vector<int>& nums, int k, int threshold) {
    int inversionCount = 0;
    vector<int> sortedNums;

    for (const int num : nums) {
      const auto lower = ranges::upper_bound(sortedNums, num);
      const auto upper = ranges::upper_bound(sortedNums, num + threshold);
      inversionCount += upper - lower;
      sortedNums.insert(lower, num);
    }

    return inversionCount >= k;
  }
};

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
  public int minThreshold(int[] nums, int k) {
    final int mx = Arrays.stream(nums).max().getAsInt();
    int l = 0;
    int r = mx + 1;

    while (l < r) {
      final int m = (l + r) / 2;
      if (countInversionPairs(nums, k, m))
        r = m;
      else
        l = m + 1;
    }

    return l > mx ? -1 : l;
  }

  private boolean countInversionPairs(final int[] nums, final int k, final int threshold) {
    int inversionCount = 0;
    List<Integer> sortedNums = new ArrayList<>();

    for (final int num : nums) {
      final int lower = firstGreater(sortedNums, num);
      final int upper = firstGreater(sortedNums, num + threshold);
      inversionCount += upper - lower;
      sortedNums.add(lower, num);
    }

    return inversionCount >= k;
  }

  private int firstGreater(List<Integer> arr, int target) {
    int l = 0;
    int r = arr.size();
    while (l < r) {
      final int m = (l + r) / 2;
      if (arr.get(m) > target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}