2426. Number of Pairs Satisfying Inequality

Description

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.

 

Example 1:

Input: nums1 = [3,2,5], nums2 = [2,2,1], diff = 1
Output: 3
Explanation:
There are 3 pairs that satisfy the conditions:
1. i = 0, j = 1: 3 - 2 <= 2 - 2 + 1. Since i < j and 1 <= 1, this pair satisfies the conditions.
2. i = 0, j = 2: 3 - 5 <= 2 - 1 + 1. Since i < j and -2 <= 2, this pair satisfies the conditions.
3. i = 1, j = 2: 2 - 5 <= 2 - 1 + 1. Since i < j and -3 <= 2, this pair satisfies the conditions.
Therefore, we return 3.

Example 2:

Input: nums1 = [3,-1], nums2 = [-2,2], diff = -1
Output: 0
Explanation:
Since there does not exist any pair that satisfies the conditions, we return 0.

 

Constraints:

• n == nums1.length == nums2.length
• 2 <= n <= 105
• -104 <= nums1[i], nums2[i] <= 104
• -104 <= diff <= 104

 

Solutions

Solution: Binary Indexed Tree

• Time complexity: O(nlogM)
• Space complexity: O(M)

 

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} diff
 * @return {number}
 */
const numberOfPairs = function (nums1, nums2, diff) {
  const n = nums1.length;
  const nums = [];

  for (let index = 0; index < n; index++) {
    const num = nums1[index] - nums2[index];

    nums.push(num);
  }

  const minNum = Math.min(...nums);
  const maxNum = Math.max(...nums);
  const offset = Math.abs(Math.min(minNum, minNum + diff)) + 1;
  const bit = new BIT(offset + Math.max(maxNum, maxNum + diff));
  let result = 0;

  for (const num of nums) {
    result += bit.query(num + diff + offset);
    bit.update(num + offset, 1);
  }

  return result;
};

class BIT {
  constructor(n) {
    this.bit = Array.from({ length: n + 1 }, () => 0);
  }

  update(num, delta) {
    while (num < this.bit.length) {
      this.bit[num] += delta;
      num += num & -num;
    }
  }

  query(num) {
    let result = 0;

    while (num > 0) {
      result += this.bit[num];
      num -= num & -num;
    }

    return result;
  }
}