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.
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 ; } }Video 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.