Number of Pairs Satisfying Inequality solution and explanation
Google
6 more videos on this problem
Biweekly Contest 88 | 6198. Number of Pairs Satisfying InequalitycodingMohan · 18:35 · 3K views
Leetcode BiWeekly contest 88 - Hard - Number of Pairs Satisfying InequalityPrakhar Agrawal · 12:57 · 1K views
2426. Number of Pairs Satisfying Inequality (Leetcode Hard)Programming Live with Larry · 8:45 · 1K views
【每日一题】LeetCode 2426. Number of Pairs Satisfying InequalityHuifeng Guan · 24:50 · 814 views
Leetcode 6198 Number of Pairs Satisfying Inequality | Biweekly Contest 88 | In hindiCodewa · 7:51 · 447 views
leetcode 2426. Number of Pairs Satisfying Inequality - binary search or sorted containerCode-Yao · 12:55 · 288 views
LeetCode Hard: 2426. Number of Pairs Satisfying Inequalityrobzingcod · 23:44 · 70 views
The 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 - 1andnums1[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 <= 104
Approach overview
Problem 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 1: Approach 1: Brute Force
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.
def num_pairs_satisfying_inequality(nums1, nums2, diff):
count = 0
n = len(nums1)
for i in range(n):
for j in range(i + 1, n):
if nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff:
count += 1
return countpublic class Solution {
public int numPairsSatisfyingInequality(int[] nums1, int[] nums2, int diff) {
int count = 0;
for (int i = 0; i < nums1.length; i++) {
for (int j = i + 1; j < nums1.length; j++) {
if (nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff) {
count++;
}
}
}
return count;
}
}#include <vector>
int numPairsSatisfyingInequality(std::vector<int>& nums1, std::vector<int>& nums2, int diff) {
int count = 0;
int n = nums1.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff) {
count++;
}
}
}
return count;
}function numPairsSatisfyingInequality(nums1, nums2, diff) {
let count = 0;
for (let i = 0; i < nums1.length; i++) {
for (let j = i + 1; j < nums1.length; j++) {
if (nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff) {
count++;
}
}
}
return count;
}#include <stdio.h>
int numPairsSatisfyingInequality(int* nums1, int nums2[], int n, int diff) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff) {
count++;
}
}
}
return count;
}public class Solution {
public int NumPairsSatisfyingInequality(int[] nums1, int[] nums2, int diff) {
int count = 0;
for (int i = 0; i < nums1.Length; i++) {
for (int j = i + 1; j < nums1.Length; j++) {
if (nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff) {
count++;
}
}
}
return count;
}
}This Python solution uses easy-to-read syntax and nested loops to find and count the pairs satisfying the inequality condition.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Approach 2: Optimized Using Sorting and Two-Pointer Technique
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.
from bisect import bisect_right
def num_pairs_satisfying_inequality(nums1, nums2, diff):
count = 0
n = len(nums1)
keys = [nums1[i] - nums2[i] for i in range(n)]
keys.sort()
for i in range(n - 1):
target = keys[i] + diff
pos = bisect_right(keys, target, i + 1)
count += pos - (i + 1)
return countimport java.util.Arrays;
public class Solution {
public int numPairsSatisfyingInequality(int[] nums1, int[] nums2, int diff) {
int count = 0;
int n = nums1.length;
int[] keys = new int[n];
for (int i = 0; i < n; i++) {
keys[i] = nums1[i] - nums2[i];
}
Arrays.sort(keys);
for (int i = 0; i < n - 1; i++) {
int target = keys[i] + diff;
int pos = Arrays.binarySearch(keys, i + 1, n, target + 1);
if (pos < 0) pos = -pos - 1;
count += pos - (i + 1);
}
return count;
}
}#include <vector>
#include <algorithm>
int numPairsSatisfyingInequality(std::vector<int>& nums1, std::vector<int>& nums2, int diff) {
int count = 0;
std::vector<int> keys(nums1.size());
for (size_t i = 0; i < nums1.size(); i++) {
keys[i] = nums1[i] - nums2[i];
}
std::sort(keys.begin(), keys.end());
for (int i = 0; i < keys.size() - 1; i++) {
int target = keys[i] + diff;
auto pos = std::upper_bound(keys.begin() + i + 1, keys.end(), target);
count += pos - (keys.begin() + i + 1);
}
return count;
}function numPairsSatisfyingInequality(nums1, nums2, diff) {
let count = 0;
const n = nums1.length;
const keys = nums1.map((num, i) => num - nums2[i]);
keys.sort((a, b) => a - b);
for (let i = 0; i < n - 1; i++) {
const target = keys[i] + diff;
let left = i + 1, right = n;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (keys[mid] <= target) left = mid + 1;
else right = mid;
}
count += left - (i + 1);
}
return count;
}#include <stdio.h>
#include <stdlib.h>
int comparator(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int numPairsSatisfyingInequality(int* nums1, int* nums2, int n, int diff) {
int count = 0;
int* keys = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
keys[i] = nums1[i] - nums2[i];
}
qsort(keys, n, sizeof(int), comparator);
for (int i = 0; i < n - 1; i++) {
int findValue = keys[i] + diff;
int idx = i + 1, high = n;
while (idx < high) {
int mid = idx + (high - idx) / 2;
if (keys[mid] <= findValue) idx = mid + 1;
else high = mid;
}
count += idx - (i + 1);
}
free(keys);
return count;
}using System;
public class Solution {
public int NumPairsSatisfyingInequality(int[] nums1, int[] nums2, int diff) {
int count = 0;
int n = nums1.Length;
int[] keys = new int[n];
for (int i = 0; i < n; i++) {
keys[i] = nums1[i] - nums2[i];
}
Array.Sort(keys);
for (int i = 0; i < n - 1; i++) {
int target = keys[i] + diff;
int pos = Array.BinarySearch(keys, i + 1, n - (i + 1), target + 1);
if (pos < 0) pos = ~pos;
count += pos - (i + 1);
}
return count;
}
}In this Python solution, we transform the array, sort it, and use bisect_right for binary search operations to pinpoint positions efficiently. This setup helps minimize the computational cost compared to a naive approach.
Time Complexity: O(n log n) induced by sorting and binary searching.
Space Complexity: O(n) given by the keys list.
Approach 3: Binary Indexed Tree
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).
type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) lowbit(x int) int {
return x & -x
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += this.lowbit(x)
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= this.lowbit(x)
}
return s
}
func numberOfPairs(nums1 []int, nums2 []int, diff int) int64 {
tree := newBinaryIndexedTree(100000)
ans := 0
for i := range nums1 {
v := nums1[i] - nums2[i]
ans += tree.query(v + diff + 40000)
tree.update(v+40000, 1)
}
return int64(ans)
}Complexity comparison
| 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) induced by sorting and binary searching. |
| Binary Indexed Tree | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Number of Pairs Satisfying Inequality easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing an inequality transformation and combining it with an advanced counting technique. A brute force solution is simple, but reaching the expected O(n log n) complexity requires knowledge of merge sort counting or tree-based range queries.
Number of Pairs Satisfying Inequality Python/Java solution
Python and Java solutions usually implement the merge sort counting technique. After building the transformed array arr[i] = nums1[i] - nums2[i], the recursive merge process counts valid pairs before merging sorted halves. The same logic translates directly across Python, Java, C++, and other languages with O(n log n) time complexity.
How to solve Number of Pairs Satisfying Inequality in O(n log n)?
Transform the inequality by defining arr[i] = nums1[i] - nums2[i]. The condition becomes arr[i] ≤ arr[j] + diff for i < j. Apply a modified merge sort that counts valid cross pairs between the left and right halves using a two-pointer sweep before merging. Each merge step processes elements in linear time, resulting in overall O(n log n) complexity.
What is the best approach for Number of Pairs Satisfying Inequality?
The most efficient approach uses a merge sort based counting technique. First compute arr[i] = nums1[i] - nums2[i], then count pairs where arr[i] ≤ arr[j] + diff during the merge step of merge sort. This keeps both halves sorted and allows a two-pointer sweep to count valid pairs in linear time per merge. The overall complexity is O(n log n) time and O(n) space.
Is Number of Pairs Satisfying Inequality asked at Google/Amazon/Meta?
This problem pattern appears in interviews at companies like Google, Amazon, and Meta under variations of pair counting with inequalities. Candidates are expected to recognize transformations and apply divide-and-conquer counting, Binary Indexed Tree, or segment tree techniques to achieve O(n log n) performance.
What data structure is used in Number of Pairs Satisfying Inequality?
Common solutions use merge sort with two pointers, a Binary Indexed Tree (Fenwick Tree), a Segment Tree, or an ordered set. These structures allow efficient counting of previously seen values that satisfy the inequality constraint. All optimized implementations typically run in O(n log n) time.
What is the time complexity of Number of Pairs Satisfying Inequality?
The brute force approach takes O(n²) time because every pair (i, j) must be checked. The optimal solution using merge sort counting or a Binary Indexed Tree reduces this to O(n log n) time. Space complexity for the optimized approach is typically O(n) due to auxiliary arrays or tree structures.