# Number of Pairs Satisfying Inequality
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-pairs-satisfying-inequality)
Canonical: https://scaleengineer.com/dsa/problems/number-of-pairs-satisfying-inequality
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Merge Sort](https://scaleengineer.com/algorithms/merge-sort)
**Data structures:** Array, Binary Indexed Tree, Segment Tree, Ordered Set
---
## Problem
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`

# Approaches
## Brute Force Iteration
This approach involves checking every possible pair of indices `(i, j)` that satisfy `0 <= i < j < n`. For each pair, we test if the inequality `nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff` holds.
**Time:** O(n^2). The two nested loops iterate through approximately `n^2 / 2` pairs. For `n = 10^5`, this is too slow. · **Space:** O(n) to store the `newNums` array. This can be optimized to O(1) by calculating the differences on the fly, but the time complexity remains the bottleneck.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient and will result in a "Time Limit Exceeded" error for the given constraints.
### Explanation
First, we simplify the inequality. The original condition is `nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff`. By rearranging the terms, we get `nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff`.
To make this easier to work with, we can create a new array, let's call it `newNums`, where `newNums[k] = nums1[k] - nums2[k]`.
The inequality now becomes `newNums[i] <= newNums[j] + diff`.
The algorithm then uses two nested loops. The outer loop iterates `i` from `0` to `n-2`, and the inner loop iterates `j` from `i+1` to `n-1`.
Inside the inner loop, we check if `newNums[i] <= newNums[j] + diff`. If it is, we increment a counter.
After checking all pairs, the value of the counter is the result.
```java
class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
        int n = nums1.length;
        long count = 0;
        int[] newNums = new int[n];
        for (int i = 0; i < n; i++) {
            newNums[i] = nums1[i] - nums2[i];
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (newNums[i] <= (long)newNums[j] + diff) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a new array `newNums` of size `n` where `newNums[k] = nums1[k] - nums2[k]`.
- Initialize a variable `count` to 0.
- Use a nested loop to iterate through all pairs `(i, j)` with `i < j`.
- For each pair, check if `newNums[i] <= newNums[j] + diff`.
- If the condition is met, increment `count`.
- Return `count`.

## Using a Fenwick Tree (BIT)
This approach improves upon the brute force method by using a Fenwick Tree (also known as a Binary Indexed Tree or BIT). We iterate through the array and, for each element, efficiently count how many preceding elements satisfy the required condition.
**Time:** O(n log M), where `n` is the number of elements and `M` is the range of possible values for `nums1[k] - nums2[k]`. Each of the `n` elements involves one query and one update on the BIT, both taking O(log M) time. · **Space:** O(M) for the Fenwick Tree. `M` is determined by the range of values, which is constant in this problem (~80002).
**Pros:** Significantly more efficient than the brute-force approach.; Passes the time limits for the given constraints.
**Cons:** Requires knowledge of Fenwick Trees.; The space complexity depends on the range of values, which could be large in other problems.; Requires careful handling of value-to-index mapping (offsetting).
### Explanation
First, we transform the inequality `nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff` into `nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff`. Let `arr[k] = nums1[k] - nums2[k]`. The problem becomes finding pairs `(i, j)` with `i < j` such that `arr[i] <= arr[j] + diff`.
We can iterate through the `arr` from left to right (say, with index `j`). For each `arr[j]`, we need to count the number of indices `i < j` such that `arr[i] <= arr[j] + diff`.
A Fenwick Tree is an excellent data structure for this. It can perform point updates and prefix sum queries in logarithmic time.
The values in `arr` can be negative and span a large range. A Fenwick tree requires non-negative indices. We can handle this by adding a constant offset to all values to shift them into a positive range. The values `nums1[i] - nums2[i]` are in `[-20000, 20000]`. The values `arr[j] + diff` are in `[-30000, 30000]`. A safe offset would be `40001`, mapping the values to a range suitable for BIT indices (e.g., `[1, 80002]`).
The algorithm is as follows:
1. Initialize a Fenwick tree `bit` of size `~80002` to all zeros.
2. Initialize a `count` to 0.
3. Iterate `j` from `0` to `n-1`.
4. For each `arr[j]`, we need to find the count of previous elements `arr[i]` (where `i < j`) such that `arr[i] <= arr[j] + diff`.
5. This is equivalent to querying the BIT for the number of elements less than or equal to `arr[j] + diff`. We query `bit.query(arr[j] + diff + offset)`.
6. Add the result of the query to our total `count`.
7. After counting, we must add the current element `arr[j]` to our data structure so it can be considered for future `j`'s. We do this by updating the BIT: `bit.update(arr[j] + offset, 1)`.
After iterating through all `j`, `count` will hold the answer.
```java
class FenwickTree {
    private int[] bit;
    private int size;

    public FenwickTree(int size) {
        this.size = size;
        this.bit = new int[size + 1];
    }

    public void update(int index, int delta) {
        while (index <= size) {
            bit[index] += delta;
            index += index & -index;
        }
    }

    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
}

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
        int n = nums1.length;
        long count = 0;
        int offset = 40001; // To handle negative values.
        int size = 80002;
        FenwickTree ft = new FenwickTree(size);

        for (int j = 0; j < n; j++) {
            int val = nums1[j] - nums2[j];
            // We need to find i < j such that nums1[i] - nums2[i] <= val + diff
            int target = val + diff;
            count += ft.query(target + offset);
            
            // Add current value to the Fenwick Tree for subsequent j's
            ft.update(val + offset, 1);
        }
        return count;
    }
}
```
### Algorithm
- Define an offset to map the range of `(nums1[k] - nums2[k])` and `(nums1[k] - nums2[k] + diff)` to positive indices.
- Initialize a Fenwick Tree (BIT) of a size large enough to accommodate the mapped values.
- Initialize a `count` of pairs to 0.
- Iterate through the arrays from `j = 0` to `n-1`.
- For each `j`, calculate `val = nums1[j] - nums2[j]`.
- The condition for a valid pair `(i, j)` with `i < j` is `nums1[i] - nums2[i] <= val + diff`.
- Query the BIT to find the number of elements seen so far (for `i < j`) that are less than or equal to `val + diff`. Add this number to `count`.
- Update the BIT with the current value `val` to include it for future calculations.
- Return `count`.

## Divide and Conquer using Merge Sort
This is a classic and elegant approach for problems involving counting pairs with a certain property (like inversions). We use a divide-and-conquer strategy, specifically a modified Merge Sort algorithm, to count the valid pairs.
**Time:** O(n log n). The recurrence relation for the algorithm is `T(n) = 2T(n/2) + O(n)`, which is the classic Merge Sort complexity. The `O(n)` part comes from the linear scan to count pairs and the linear-time merge operation. · **Space:** O(n) due to the temporary array required for the merge step.
**Pros:** Very efficient, with a time complexity of O(n log n).; It's a self-contained algorithm that doesn't depend on external data structures like Fenwick Trees or specific value ranges.; An elegant application of the divide-and-conquer paradigm.
**Cons:** Can be slightly more complex to implement correctly compared to the brute-force approach.; The recursive nature might lead to stack overflow on extremely large `n` if not implemented iteratively, but this is not an issue for the given constraints.
### Explanation
As before, we transform the problem by creating an array `arr` where `arr[k] = nums1[k] - nums2[k]`. The goal is to find pairs `(i, j)` with `i < j` such that `arr[i] <= arr[j] + diff`.
The core idea is to use a recursive `mergeSort` function that not only sorts a subarray but also counts the valid pairs within it.
A call to `mergeSort(arr, low, high)` will return the number of valid pairs where both indices `i` and `j` are within the range `[low, high]`.
Inside `mergeSort(arr, low, high)`:
1.  **Base Case:** If `low >= high`, there are no pairs, so return 0.
2.  **Divide:** Find the middle index `mid = low + (high - low) / 2`.
3.  **Conquer:** Recursively count pairs in the left half (`low` to `mid`) and the right half (`mid+1` to `high`). The total count so far is `count = mergeSort(arr, low, mid) + mergeSort(arr, mid + 1, high)`.
4.  **Combine (Count Cross-Pairs):** Now, we must count pairs `(i, j)` where `i` is in the left half (`low <= i <= mid`) and `j` is in the right half (`mid+1 <= j <= high`). Since the recursive calls have sorted the left and right halves, we can do this efficiently.
5.  We iterate through each element `arr[i]` in the left half. For each `arr[i]`, we need to find how many elements `arr[j]` in the right half satisfy `arr[j] >= arr[i] - diff`. Since the right half is sorted, we can use a two-pointer approach. We maintain a pointer `k` in the right half. For each `i`, we advance `k` until `arr[k] >= arr[i] - diff`. Then, all elements from `arr[k]` onwards in the right half are valid partners for `arr[i]`. We add `high - k + 1` to our count.
6.  **Merge:** Finally, merge the two sorted halves `arr[low...mid]` and `arr[mid+1...high]` into a single sorted array `arr[low...high]` so that the subarray is sorted for the parent recursive call.
The initial call will be `mergeSort(arr, 0, n-1)`.
```java
class Solution {
    long count = 0;
    int diff;

    public long numberOfPairs(int[] nums1, int[] nums2, int d) {
        this.diff = d;
        int n = nums1.length;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nums1[i] - nums2[i];
        }
        mergeSort(arr, 0, n - 1);
        return count;
    }

    private void mergeSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = low + (high - low) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        countPairs(arr, low, mid, high);
        merge(arr, low, mid, high);
    }

    private void countPairs(int[] arr, int low, int mid, int high) {
        int right = mid + 1;
        for (int left = low; left <= mid; left++) {
            // Find the first element in the right half that is NOT smaller than arr[left] - diff
            while (right <= high && arr[left] > (long)arr[right] + diff) {
                right++;
            }
            // All elements from 'right' to 'high' in the right subarray satisfy the condition
            count += (high - right + 1);
        }
    }

    private void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, k = 0;
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= high) {
            temp[k++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, low, temp.length);
    }
}
```
### Algorithm
- Create a new array `arr` where `arr[k] = nums1[k] - nums2[k]`.
- Implement a recursive `mergeSort` function that takes the array and range `(low, high)`.
- In `mergeSort`, recursively call it for the left `(low, mid)` and right `(mid+1, high)` halves.
- After the recursive calls (which sort the halves), count the "cross pairs". These are pairs `(i, j)` where `i` is in the left half and `j` is in the right.
- To count cross pairs, use a two-pointer technique on the sorted left and right halves to find pairs satisfying `arr[i] <= arr[j] + diff` in O(n) time.
- Add the counts from the left half, right half, and cross pairs.
- Perform a standard merge operation to combine the sorted halves.
- The final result is returned by the top-level call to `mergeSort`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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
```