Number of Pairs Satisfying Inequality
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every possible pair of indices (i, j) that satisfy 0 <= i < j < n. For each pair, we test if the inequality nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff holds.
Algorithm
- Create a new array
newNumsof sizenwherenewNums[k] = nums1[k] - nums2[k]. - Initialize a variable
countto 0. - Use a nested loop to iterate through all pairs
(i, j)withi < j. - For each pair, check if
newNums[i] <= newNums[j] + diff. - If the condition is met, increment
count. - Return
count.
Walkthrough
First, we simplify the inequality. The original condition is nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff. By rearranging the terms, we get nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff.
To make this easier to work with, we can create a new array, let's call it newNums, where newNums[k] = nums1[k] - nums2[k].
The inequality now becomes newNums[i] <= newNums[j] + diff.
The algorithm then uses two nested loops. The outer loop iterates i from 0 to n-2, and the inner loop iterates j from i+1 to n-1.
Inside the inner loop, we check if newNums[i] <= newNums[j] + diff. If it is, we increment a counter.
After checking all pairs, the value of the counter is the result.
class Solution { public long numberOfPairs(int[] nums1, int[] nums2, int diff) { int n = nums1.length; long count = 0; int[] newNums = new int[n]; for (int i = 0; i < n; i++) { newNums[i] = nums1[i] - nums2[i]; } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (newNums[i] <= (long)newNums[j] + diff) { count++; } } } return count; }}Complexity
Time
O(n^2). The two nested loops iterate through approximately `n^2 / 2` pairs. For `n = 10^5`, this is too slow.
Space
O(n) to store the `newNums` array. This can be optimized to O(1) by calculating the differences on the fly, but the time complexity remains the bottleneck.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient and will result in a "Time Limit Exceeded" error for the given constraints.
This approach improves upon the brute force method by using a Fenwick Tree (also known as a Binary Indexed Tree or BIT). We iterate through the array and, for each element, efficiently count how many preceding elements satisfy the required condition.
Algorithm
- Define an offset to map the range of
(nums1[k] - nums2[k])and(nums1[k] - nums2[k] + diff)to positive indices. - Initialize a Fenwick Tree (BIT) of a size large enough to accommodate the mapped values.
- Initialize a
countof pairs to 0. - Iterate through the arrays from
j = 0ton-1. - For each
j, calculateval = nums1[j] - nums2[j]. - The condition for a valid pair
(i, j)withi < jisnums1[i] - nums2[i] <= val + diff. - Query the BIT to find the number of elements seen so far (for
i < j) that are less than or equal toval + diff. Add this number tocount. - Update the BIT with the current value
valto include it for future calculations. - Return
count.
Walkthrough
First, we transform the inequality nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff into nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff. Let arr[k] = nums1[k] - nums2[k]. The problem becomes finding pairs (i, j) with i < j such that arr[i] <= arr[j] + diff.
We can iterate through the arr from left to right (say, with index j). For each arr[j], we need to count the number of indices i < j such that arr[i] <= arr[j] + diff.
A Fenwick Tree is an excellent data structure for this. It can perform point updates and prefix sum queries in logarithmic time.
The values in arr can be negative and span a large range. A Fenwick tree requires non-negative indices. We can handle this by adding a constant offset to all values to shift them into a positive range. The values nums1[i] - nums2[i] are in [-20000, 20000]. The values arr[j] + diff are in [-30000, 30000]. A safe offset would be 40001, mapping the values to a range suitable for BIT indices (e.g., [1, 80002]).
The algorithm is as follows:
- Initialize a Fenwick tree
bitof size~80002to all zeros. - Initialize a
countto 0. - Iterate
jfrom0ton-1. - For each
arr[j], we need to find the count of previous elementsarr[i](wherei < j) such thatarr[i] <= arr[j] + diff. - This is equivalent to querying the BIT for the number of elements less than or equal to
arr[j] + diff. We querybit.query(arr[j] + diff + offset). - Add the result of the query to our total
count. - After counting, we must add the current element
arr[j]to our data structure so it can be considered for futurej's. We do this by updating the BIT:bit.update(arr[j] + offset, 1). After iterating through allj,countwill hold the answer.
class FenwickTree { private int[] bit; private int size; public FenwickTree(int size) { this.size = size; this.bit = new int[size + 1]; } public void update(int index, int delta) { while (index <= size) { bit[index] += delta; index += index & -index; } } public int query(int index) { int sum = 0; while (index > 0) { sum += bit[index]; index -= index & -index; } return sum; }} class Solution { public long numberOfPairs(int[] nums1, int[] nums2, int diff) { int n = nums1.length; long count = 0; int offset = 40001; // To handle negative values. int size = 80002; FenwickTree ft = new FenwickTree(size); for (int j = 0; j < n; j++) { int val = nums1[j] - nums2[j]; // We need to find i < j such that nums1[i] - nums2[i] <= val + diff int target = val + diff; count += ft.query(target + offset); // Add current value to the Fenwick Tree for subsequent j's ft.update(val + offset, 1); } return count; }}Complexity
Time
O(n log M), where `n` is the number of elements and `M` is the range of possible values for `nums1[k] - nums2[k]`. Each of the `n` elements involves one query and one update on the BIT, both taking O(log M) time.
Space
O(M) for the Fenwick Tree. `M` is determined by the range of values, which is constant in this problem (~80002).
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Passes the time limits for the given constraints.
Cons
Requires knowledge of Fenwick Trees.
The space complexity depends on the range of values, which could be large in other problems.
Requires careful handling of value-to-index mapping (offsetting).
This is a classic and elegant approach for problems involving counting pairs with a certain property (like inversions). We use a divide-and-conquer strategy, specifically a modified Merge Sort algorithm, to count the valid pairs.
Algorithm
- Create a new array
arrwherearr[k] = nums1[k] - nums2[k]. - Implement a recursive
mergeSortfunction that takes the array and range(low, high). - In
mergeSort, recursively call it for the left(low, mid)and right(mid+1, high)halves. - After the recursive calls (which sort the halves), count the "cross pairs". These are pairs
(i, j)whereiis in the left half andjis in the right. - To count cross pairs, use a two-pointer technique on the sorted left and right halves to find pairs satisfying
arr[i] <= arr[j] + diffin O(n) time. - Add the counts from the left half, right half, and cross pairs.
- Perform a standard merge operation to combine the sorted halves.
- The final result is returned by the top-level call to
mergeSort.
Walkthrough
As before, we transform the problem by creating an array arr where arr[k] = nums1[k] - nums2[k]. The goal is to find pairs (i, j) with i < j such that arr[i] <= arr[j] + diff.
The core idea is to use a recursive mergeSort function that not only sorts a subarray but also counts the valid pairs within it.
A call to mergeSort(arr, low, high) will return the number of valid pairs where both indices i and j are within the range [low, high].
Inside mergeSort(arr, low, high):
- Base Case: If
low >= high, there are no pairs, so return 0. - Divide: Find the middle index
mid = low + (high - low) / 2. - Conquer: Recursively count pairs in the left half (
lowtomid) and the right half (mid+1tohigh). The total count so far iscount = mergeSort(arr, low, mid) + mergeSort(arr, mid + 1, high). - Combine (Count Cross-Pairs): Now, we must count pairs
(i, j)whereiis in the left half (low <= i <= mid) andjis in the right half (mid+1 <= j <= high). Since the recursive calls have sorted the left and right halves, we can do this efficiently. - We iterate through each element
arr[i]in the left half. For eacharr[i], we need to find how many elementsarr[j]in the right half satisfyarr[j] >= arr[i] - diff. Since the right half is sorted, we can use a two-pointer approach. We maintain a pointerkin the right half. For eachi, we advancekuntilarr[k] >= arr[i] - diff. Then, all elements fromarr[k]onwards in the right half are valid partners forarr[i]. We addhigh - k + 1to our count. - Merge: Finally, merge the two sorted halves
arr[low...mid]andarr[mid+1...high]into a single sorted arrayarr[low...high]so that the subarray is sorted for the parent recursive call. The initial call will bemergeSort(arr, 0, n-1).
class Solution { long count = 0; int diff; public long numberOfPairs(int[] nums1, int[] nums2, int d) { this.diff = d; int n = nums1.length; int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = nums1[i] - nums2[i]; } mergeSort(arr, 0, n - 1); return count; } private void mergeSort(int[] arr, int low, int high) { if (low >= high) { return; } int mid = low + (high - low) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); countPairs(arr, low, mid, high); merge(arr, low, mid, high); } private void countPairs(int[] arr, int low, int mid, int high) { int right = mid + 1; for (int left = low; left <= mid; left++) { // Find the first element in the right half that is NOT smaller than arr[left] - diff while (right <= high && arr[left] > (long)arr[right] + diff) { right++; } // All elements from 'right' to 'high' in the right subarray satisfy the condition count += (high - right + 1); } } private void merge(int[] arr, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; while (i <= mid && j <= high) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= high) { temp[k++] = arr[j++]; } System.arraycopy(temp, 0, arr, low, temp.length); }}Complexity
Time
O(n log n). The recurrence relation for the algorithm is `T(n) = 2T(n/2) + O(n)`, which is the classic Merge Sort complexity. The `O(n)` part comes from the linear scan to count pairs and the linear-time merge operation.
Space
O(n) due to the temporary array required for the merge step.
Trade-offs
Pros
Very efficient, with a time complexity of O(n log n).
It's a self-contained algorithm that doesn't depend on external data structures like Fenwick Trees or specific value ranges.
An elegant application of the divide-and-conquer paradigm.
Cons
Can be slightly more complex to implement correctly compared to the brute-force approach.
The recursive nature might lead to stack overflow on extremely large
nif not implemented iteratively, but this is not an issue for the given constraints.
Solutions
Solution
class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public static final int lowbit ( int x ) { return x & - x ; } public void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += lowbit ( x ); } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= lowbit ( x ); } return s ; } } class Solution { public long numberOfPairs ( int [] nums1 , int [] nums2 , int diff ) { BinaryIndexedTree tree = new BinaryIndexedTree ( 100000 ); long ans = 0 ; for ( int i = 0 ; i < nums1 . length ; ++ i ) { int v = nums1 [ i ] - nums2 [ i ]; ans += tree . query ( v + diff + 40000 ); tree . update ( v + 40000 , 1 ); } return ans ; } }class BinaryIndexedTree { public: int n ; vector < int > c ; BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += lowbit ( x ); } } int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= lowbit ( x ); } return s ; } int lowbit ( int x ) { return x & - x ; } }; class Solution { public: long long numberOfPairs ( vector < int >& nums1 , vector < int >& nums2 , int diff ) { BinaryIndexedTree * tree = new BinaryIndexedTree ( 1e5 ); long long ans = 0 ; for ( int i = 0 ; i < nums1 . size (); ++ i ) { int v = nums1 [ i ] - nums2 [ i ]; ans += tree -> query ( v + diff + 40000 ); tree -> update ( v + 40000 , 1 ); } return ans ; } };class BinaryIndexedTree : def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) @ staticmethod def lowbit ( x ): return x & - x def update ( self , x , delta ): while x <= self . n : self . c [ x ] += delta x += BinaryIndexedTree . lowbit ( x ) def query ( self , x ): s = 0 while x : s += self . c [ x ] x -= BinaryIndexedTree . lowbit ( x ) return s class Solution : def numberOfPairs ( self , nums1 : List [ int ], nums2 : List [ int ], diff : int ) -> int : tree = BinaryIndexedTree ( 10 ** 5 ) ans = 0 for a , b in zip ( nums1 , nums2 ): v = a - b ans += tree . query ( v + diff + 40000 ) tree . update ( v + 40000 , 1 ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.