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 andnums1[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.length2 <= n <= 105-104 <= nums1[i], nums2[i] <= 104-104 <= diff <= 104Problem Overview: You are given two arrays nums1 and nums2 and an integer diff. Count pairs (i, j) where i < j and nums1[i] - nums1[j] ≤ nums2[i] - nums2[j] + diff. Rearranging the inequality simplifies it to (nums1[i] - nums2[i]) ≤ (nums1[j] - nums2[j]) + diff. This transformation turns the problem into counting valid pairs in a derived array.
Approach 1: Brute Force (O(n²) time, O(1) space)
Compute a new array arr[i] = nums1[i] - nums2[i]. Then check every pair (i, j) with i < j. For each pair, verify whether arr[i] ≤ arr[j] + diff. This requires two nested loops iterating through all pairs. The approach is straightforward and useful for verifying correctness or small input sizes, but the quadratic time complexity becomes impractical when n grows to tens of thousands.
Approach 2: Sorting + Two-Pointer During Merge (O(n log n) time, O(n) space)
Again start with the transformed array arr[i] = nums1[i] - nums2[i]. The goal becomes counting pairs where arr[i] ≤ arr[j] + diff for i < j. Use a modified merge sort to count valid pairs while merging two sorted halves. For each element in the left half, advance a pointer in the right half while the inequality holds and accumulate the number of valid indices. Because both halves remain sorted, the pointer only moves forward, making counting linear per merge step. The merge step also keeps the array sorted for higher recursion levels.
This technique is similar to counting inversions but with a custom inequality condition. The algorithm divides the array, recursively sorts both halves, counts valid cross pairs using a two-pointer sweep, and finally merges them. Total complexity becomes O(n log n), which handles large inputs efficiently.
Other competitive implementations use a Binary Indexed Tree, Segment Tree, or ordered set to maintain prefix counts while scanning the array. Those approaches also achieve O(n log n) complexity but require coordinate compression.
Recommended for interviews: The merge-sort counting approach. Interviewers expect you to recognize the inequality transformation and reduce the problem to counting pairs in a sorted structure. Brute force demonstrates the baseline understanding, but the merge-sort or tree-based solution shows algorithmic depth and familiarity with divide-and-conquer counting techniques.
The simplest way to solve the problem is by checking each pair of indices (i, j) and verifying if the condition nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff is met. This involves a nested loop where we iterate over each possible pair meeting 0 <= i < j < n. Although this is not an efficient solution for large inputs, it provides a straightforward method to determine all valid pairs.
In this C solution, we use two nested loops: the outer loop starts from the first element, and the inner loop iterates over the succeeding elements. For each pair, we check if the condition is satisfied. If it is, we increment the count.
Time Complexity: O(n^2)
Space Complexity: O(1)
The brute force approach's limit is the O(n2) time complexity. To optimize, sort the transformed key array key[i] = nums1[i] - nums2[i] and use a two-pointer or binary search method to efficiently count valid j indices for each i.
This C implementation firstly computes the transformation array keys, sorts it, and then iterates over it. For each element, it uses binary search to find the range of valid pairs using the diff condition.
Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the keys array.
We can transform the inequality in the problem to nums1[i] - nums2[i] leq 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] leq nums[j] + diff.
We can enumerate j from small to large, find out how many numbers before it satisfy nums[i] leq 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] leq nums[j] + diff in O(log n) time.
The time complexity is O(n times log n).
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time Complexity: O(n^2) |
| Approach 2: Optimized Using Sorting and Two-Pointer Technique | Time Complexity: O(n log n) due to sorting and binary search. |
| Binary Indexed Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Small inputs, quick validation, or understanding the inequality transformation |
| Merge Sort + Two-Pointer Counting | O(n log n) | O(n) | Large arrays where efficient pair counting is required; standard interview solution |
Biweekly Contest 88 | 6198. Number of Pairs Satisfying Inequality • codingMohan • 3,043 views views
Watch 9 more video solutions →Practice Number of Pairs Satisfying Inequality with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor