Number of Pairs Satisfying Inequality

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 thenumber of pairs that satisfy the conditions.

Examples

Example 1

1
2
3
4
5
6
7
8


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

1
2
3
4


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 <= 10^5
-10^4 <= nums1[i], nums2[i] <= 10^4
-10^4 <= diff <= 10^4

Solution

Method 1 – Modified Merge Sort (Divide and Conquer)

Intuition

We want to count pairs (i, j) with i < j such that nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff. Rearranging, we get (nums1[i] - nums2[i]) <= (nums1[j] - nums2[j]) + diff. This is a classic “count of pairs with difference <= k” problem, which can be solved efficiently using merge sort and counting during the merge step.

Approach

Compute arr[i] = nums1[i] - nums2[i] for all i.
Use a modified merge sort to count, for each i, the number of j > i such that arr[i] <= arr[j] + diff.
During the merge step, for each left element, use two pointers to count how many right elements satisfy the condition.
Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


#include <vector>
using namespace std;
class Solution {
public:
    long long mergeCount(vector<long long>& arr, int l, int r, int diff) {
        if (r - l <= 1) return 0;
        int m = l + (r - l) / 2;
        long long cnt = mergeCount(arr, l, m, diff) + mergeCount(arr, m, r, diff);
        int j = m;
        for (int i = l; i < m; ++i) {
            while (j < r && arr[i] > arr[j] + diff) ++j;
            cnt += r - j;
        }
        inplace_merge(arr.begin() + l, arr.begin() + m, arr.begin() + r);
        return cnt;
    }
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
        int n = nums1.size();
        vector<long long> arr(n);
        for (int i = 0; i < n; ++i) arr[i] = nums1[i] - nums2[i];
        return mergeCount(arr, 0, n, diff);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func numberOfPairs(nums1, nums2 []int, diff int) int64 {
    n := len(nums1)
    arr := make([]int, n)
    for i := range nums1 {
        arr[i] = nums1[i] - nums2[i]
    }
    var mergeCount func([]int, int, int) int64
    mergeCount = func(a []int, l, r int) int64 {
        if r-l <= 1 { return 0 }
        m := l + (r-l)/2
        cnt := mergeCount(a, l, m) + mergeCount(a, m, r)
        j := m
        for i := l; i < m; i++ {
            for j < r && a[i] > a[j]+diff { j++ }
            cnt += int64(r-j)
        }
        tmp := make([]int, r-l)
        copy(tmp, a[l:r])
        i, j, k := 0, m-l, l
        for i < m-l && j < r-l {
            if tmp[i] <= tmp[j] {
                a[k] = tmp[i]; i++
            } else {
                a[k] = tmp[j]; j++
            }
            k++
        }
        for i < m-l { a[k] = tmp[i]; i++; k++ }
        for j < r-l { a[k] = tmp[j]; j++; k++ }
        return cnt
    }
    return mergeCount(arr, 0, n)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
        int n = nums1.length;
        long[] arr = new long[n];
        for (int i = 0; i < n; ++i) arr[i] = nums1[i] - nums2[i];
        return mergeCount(arr, 0, n, diff);
    }
    private long mergeCount(long[] arr, int l, int r, int diff) {
        if (r - l <= 1) return 0;
        int m = l + (r - l) / 2;
        long cnt = mergeCount(arr, l, m, diff) + mergeCount(arr, m, r, diff);
        int j = m;
        for (int i = l; i < m; ++i) {
            while (j < r && arr[i] > arr[j] + diff) ++j;
            cnt += r - j;
        }
        java.util.Arrays.sort(arr, l, r);
        return cnt;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    fun numberOfPairs(nums1: IntArray, nums2: IntArray, diff: Int): Long {
        val n = nums1.size
        val arr = LongArray(n) { nums1[it].toLong() - nums2[it].toLong() }
        fun mergeCount(arr: LongArray, l: Int, r: Int): Long {
            if (r - l <= 1) return 0L
            val m = l + (r - l) / 2
            var cnt = mergeCount(arr, l, m) + mergeCount(arr, m, r)
            var j = m
            for (i in l until m) {
                while (j < r && arr[i] > arr[j] + diff) j++
                cnt += (r - j)
            }
            arr.sort(l, r)
            return cnt
        }
        return mergeCount(arr, 0, n)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def numberOfPairs(self, nums1, nums2, diff):
        arr = [a-b for a,b in zip(nums1, nums2)]
        def merge_count(arr):
            def sort(l, r):
                if r-l <= 1: return 0
                m = (l+r)//2
                cnt = sort(l, m) + sort(m, r)
                j = m
                for i in range(l, m):
                    while j < r and arr[i] > arr[j] + diff:
                        j += 1
                    cnt += r-j
                arr[l:r] = sorted(arr[l:r])
                return cnt
            return sort(0, len(arr))
        return merge_count(arr)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


impl Solution {
    pub fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, diff: i32) -> i64 {
        let n = nums1.len();
        let mut arr: Vec<i64> = (0..n).map(|i| nums1[i] as i64 - nums2[i] as i64).collect();
        fn merge_count(arr: &mut [i64], diff: i64) -> i64 {
            let n = arr.len();
            if n <= 1 { return 0; }
            let m = n/2;
            let mut cnt = merge_count(&mut arr[..m], diff) + merge_count(&mut arr[m..], diff);
            let mut j = m;
            for i in 0..m {
                while j < n && arr[i] > arr[j] + diff { j += 1; }
                cnt += (n-j) as i64;
            }
            arr.sort();
            cnt
        }
        merge_count(&mut arr, diff as i64)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    numberOfPairs(nums1: number[], nums2: number[], diff: number): number {
        const arr = nums1.map((v, i) => v - nums2[i]);
        function mergeCount(arr: number[], l: number, r: number): number {
            if (r - l <= 1) return 0;
            const m = l + ((r - l) >> 1);
            let cnt = mergeCount(arr, l, m) + mergeCount(arr, m, r);
            let j = m;
            for (let i = l; i < m; ++i) {
                while (j < r && arr[i] > arr[j] + diff) ++j;
                cnt += r - j;
            }
            const tmp = arr.slice(l, r).sort((a, b) => a - b);
            for (let i = l; i < r; ++i) arr[i] = tmp[i - l];
            return cnt;
        }
        return mergeCount(arr, 0, arr.length);
    }
}

Complexity

⏰ Time complexity: O(n log n), since merge sort is used and each merge step is O(n).
🧺 Space complexity: O(n), for the auxiliary arrays.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Modified Merge Sort (Divide and Conquer)#

Intuition#

Approach#

Code#

Complexity#