Watch 10 video solutions for Number of Pairs Satisfying Inequality, a hard level problem involving Array, Binary Search, Divide and Conquer. This walkthrough by codingMohan has 3,043 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |