Number of pairs satisfying inequality

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

46.8% acceptance

Feb 25, 2026

577

You are given two 0-indexed integer arrays nums1 and nums2, each of size n, and an integer diff. Find the number of pairs (i, j) such that: 0 <= i < j <= n - 1 and nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff. Return the number of pairs that satisfy the conditions.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, diff: i32) -> i64 {
    // Transform: count pairs (i<j) where a[i] <= a[j] + diff
    // where a[k] = nums1[k] - nums2[k]
    // Equivalently, for each j, count i < j where a[i] <= a[j] + diff
    // Use BIT (Fenwick tree) with coordinate compression.
    // a[k] ranges from -2*10^4 to 2*10^4, so a[j]+diff ranges from -3*10^4 to 3*10^4.
    let n = nums1.len();
    let a: Vec<i32> = (0..n).map(|i| nums1[i] - nums2[i]).collect();

    const OFFSET: i32 = 30001;
    const SIZE: usize = 60002;
    let mut bit = vec![0i64; SIZE + 2];

    fn bit_update(bit: &mut Vec<i64>, mut i: usize, size: usize) {
      while i <= size {
        bit[i] += 1;
        i += i & i.wrapping_neg();
      }
    }

    fn bit_query(bit: &[i64], mut i: usize) -> i64 {
      let mut s = 0i64;
      while i > 0 {
        s += bit[i];
        i -= i & i.wrapping_neg();
      }
      s
    }

    let mut ans = 0i64;
    for j in 0..n {
      let upper = ((a[j] + diff + OFFSET) as usize).min(SIZE);
      ans += bit_query(&bit, upper);
      bit_update(&mut bit, (a[j] + OFFSET) as usize, SIZE);
    }
    ans
  }
}