The inequality nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff has four array accesses and a constant, but it simplifies once we group the terms by index.

Rearranging the inequality:

nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff

nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff

If we define a new array arr where arr[k] = nums1[k] - nums2[k], the inequality becomes:

arr[i] <= arr[j] + diff

Or equivalently: arr[i] - arr[j] <= diff

So the problem reduces to: given an array arr, count all pairs (i, j) with i < j such that arr[i] - arr[j] <= diff. This is a variant of counting inversions. The i < j index constraint combined with a value comparison is what merge sort-based counting and order-statistic structures like a Binary Indexed Tree are built to handle efficiently.

Key Constraints:

Intuition

Build the array arr where arr[k] = nums1[k] - nums2[k], then check every pair (i, j) with i < j against the simplified condition arr[i] - arr[j] <= diff. Two nested loops cover all pairs. This is the baseline before optimizing.

Algorithm

Example Walkthrough

Input: nums1 = [3, 2, 5], nums2 = [2, 2, 1], diff = 1

First, build arr = [1, 0, 4].

Result: 3 pairs.

Code

The quadratic scan is wasteful: for a fixed j, it recompares against every earlier element one at a time. Sorting the values lets us count matching elements in bulk, and merge sort can do this sorting while still respecting the i < j ordering.

Intuition

Merge sort splits the array into a left half (smaller indices) and a right half (larger indices), sorts each, then merges them. The counting happens just before each merge. At that point every element in the left half had a smaller original index than every element in the right half, so the cross-boundary pairs are precisely the i < j pairs where i is in the left half and j is in the right half. Pairs that lie entirely inside one half are counted by the recursive calls on that half.

Both halves are sorted just before the merge. So for each element arr[j] in the right half, we count how many elements arr[i] in the left half satisfy arr[i] <= arr[j] + diff. Because the left half is sorted ascending, those matching elements form a prefix, and a single forward-moving pointer finds the prefix length.

The right half is also sorted ascending, so as j advances, arr[j] and the threshold arr[j] + diff only increase. The pointer therefore never moves backward: it advances across all of the right half once per merge, making the counting step O(n) per merge level and O(n log n) overall.

Algorithm

Example Walkthrough

Code

Merge sort reaches O(n log n) but needs a custom recursive merge. The next approach reaches the same bound with a single left-to-right pass, delegating the counting to a Binary Indexed Tree.

Intuition

Instead of using merge sort's divide-and-conquer structure to enforce the i < j ordering, process elements from left to right. By the time we reach index j, all elements at indices 0 through j - 1 have already been processed, so we need an efficient way to count how many of those earlier values satisfy arr[i] <= arr[j] + diff.

A Binary Indexed Tree (also called a Fenwick Tree) supports two operations in O(log n) time: update a position (add 1 to record that a value has been seen) and query a prefix sum (count how many recorded values fall at or below a threshold). Counting earlier values at or below arr[j] + diff is a prefix-sum query.

The values of arr[k] range from -20,000 to 20,000, so adding a fixed offset of 20,001 maps them to positive indices. For each index j, query the BIT for the count of recorded values at most arr[j] + diff, add that to the result, then record arr[j]. Querying before recording enforces i < j: only values from earlier indices are in the tree when index j is counted.

Algorithm

Example Walkthrough

Code