LeetCode 2426. Number of Pairs Satisfying Inequality Solution in Java, C++, Python & Go | Explanation + Code

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 1: Binary Indexed Tree

We can transform the inequality in the problem to nums1[i] - nums2[i] ≤ nums1[j] - nums2[j] + diff. Therefore, if we calculate the difference between the corresponding elements of the two arrays and get another array nums, the problem is transformed into finding the number of pairs in nums that satisfy nums[i] ≤ nums[j] + diff.

We can enumerate j from small to large, find out how many numbers before it satisfy nums[i] ≤ nums[j] + diff, and thus calculate the number of pairs. We can use a binary indexed tree to maintain the prefix sum, so we can find out how many numbers before it satisfy nums[i] ≤ nums[j] + diff in O(log n) time.

The time complexity is O(n × log n).

PythonJavaC++Go

class BinaryIndexedTree: def __init__(self, n): self.n = n self.c = [0] * (n + 1) @staticmethod def lowbit(x): return x & -x def update(self, x, delta): while x <= self.n: self.c[x] += delta x += BinaryIndexedTree.lowbit(x) def query(self, x): s = 0 while x: s += self.c[x] x -= BinaryIndexedTree.lowbit(x) return s class Solution: def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int: tree = BinaryIndexedTree(10**5) ans = 0 for a, b in zip(nums1, nums2): v = a - b ans += tree.query(v + diff + 40000) tree.update(v + 40000, 1) return ans(code-box)

class BinaryIndexedTree { private int n; private int[] c; public BinaryIndexedTree(int n) { this.n = n; c = new int[n + 1]; } public static final int lowbit(int x) { return x & -x; } public void update(int x, int delta) { while (x <= n) { c[x] += delta; x += lowbit(x); } } public int query(int x) { int s = 0; while (x > 0) { s += c[x]; x -= lowbit(x); } return s; } } class Solution { public long numberOfPairs(int[] nums1, int[] nums2, int diff) { BinaryIndexedTree tree = new BinaryIndexedTree(100000); long ans = 0; for (int i = 0; i < nums1.length; ++i) { int v = nums1[i] - nums2[i]; ans += tree.query(v + diff + 40000); tree.update(v + 40000, 1); } return ans; } }(code-box)

class BinaryIndexedTree { public: int n; vector<int> c; BinaryIndexedTree(int _n) : n(_n) , c(_n + 1) {} void update(int x, int delta) { while (x <= n) { c[x] += delta; x += lowbit(x); } } int query(int x) { int s = 0; while (x > 0) { s += c[x]; x -= lowbit(x); } return s; } int lowbit(int x) { return x & -x; } }; class Solution { public: long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) { BinaryIndexedTree* tree = new BinaryIndexedTree(1e5); long long ans = 0; for (int i = 0; i < nums1.size(); ++i) { int v = nums1[i] - nums2[i]; ans += tree->query(v + diff + 40000); tree->update(v + 40000, 1); } return ans; } };(code-box)

type BinaryIndexedTree struct { n int c []int } func newBinaryIndexedTree(n int) *BinaryIndexedTree { c := make([]int, n+1) return &BinaryIndexedTree{n, c} } func (this *BinaryIndexedTree) lowbit(x int) int { return x & -x } func (this *BinaryIndexedTree) update(x, delta int) { for x <= this.n { this.c[x] += delta x += this.lowbit(x) } } func (this *BinaryIndexedTree) query(x int) int { s := 0 for x > 0 { s += this.c[x] x -= this.lowbit(x) } return s } func numberOfPairs(nums1 []int, nums2 []int, diff int) int64 { tree := newBinaryIndexedTree(100000) ans := 0 for i := range nums1 { v := nums1[i] - nums2[i] ans += tree.query(v + diff + 40000) tree.update(v+40000, 1) } return int64(ans) }(code-box)