Skip to main content
Talentd

Number of Pairs Satisfying Inequality - Solution & Explanation

HardArrayBinary SearchDivide and ConquerBinary Indexed Tree17 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the keys array.

Try this approach in the editor →

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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2: Optimized Using Sorting and Two-Pointer Technique

Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the keys array.

Binary Indexed Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n²)O(1)Small inputs, quick validation, or understanding the inequality transformation
Merge Sort + Two-Pointer CountingO(n log n)O(n)Large arrays where efficient pair counting is required; standard interview solution

Video Solution

Biweekly Contest 88 | 6198. Number of Pairs Satisfying Inequality • codingMohan • 3,098 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Number of Pairs Satisfying Inequality with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Nice Pairs in an Array

Next

Count Number of Bad Pairs