DSA problem
Number of Pairs Satisfying Inequality
You are given two 0-indexed integer arrays nums1 and nums2 of equal length n, and an integer diff. Find the number of pairs (i, j) such that 0 <= i < j < n and nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.
The inequality looks two-dimensional but is really one-dimensional in disguise. Subtract nums2[i] - nums2[j] from both sides: (nums1[i] - nums2[i]) - (nums1[j] - nums2[j]) <= diff. Define d[k] = nums1[k] - nums2[k]. The problem reduces to counting pairs (i, j) with i < j and d[i] <= d[j] + diff — a classic "count smaller (with offset) to the left" problem solvable in O(n log n).
Iterate j from 0 to n - 1. For each j we want the count of indices i < j whose d[i] <= d[j] + diff. If we maintain a Fenwick tree (Binary Indexed Tree) of the multiset {d[0], d[1], ..., d[j-1]} indexed by value, the answer for this j is a prefix-sum query at value d[j] + diff. After recording the answer we increment the BIT at value d[i] = d[j] to make it available to future queries.
Because d[k] may be negative or large, coordinate-compress the values. Build the universe S from every d[k] and every d[k] + diff (these are the only values we ever query at), sort and dedupe to ranks 1..K, and use those ranks as Fenwick indices. The total cost is O(n log n) time and O(n) extra space.
Examples
nums1 = [3,2,5], nums2 = [2,2,1], diff = 13nums1 = [3,-1], nums2 = [-2,2], diff = -10nums1 = [1,1,1,1], nums2 = [1,1,1,1], diff = 06Constraints
- n == nums1.length == nums2.length
- 2 <= n <= 10^5
- -10^4 <= nums1[i], nums2[i] <= 10^4
- -10^4 <= diff <= 10^4
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.