Number of Pairs Satisfying Inequality

HARD

Description

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 <= 10⁵
-10⁴ <= nums1[i], nums2[i] <= 10⁴
-10⁴ <= diff <= 10⁴

Approaches

Checkout 3 different approaches to solve Number of Pairs Satisfying Inequality. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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 newNums of size n where newNums[k] = nums1[k] - nums2[k].
Initialize a variable count to 0.
Use a nested loop to iterate through all pairs (i, j) with i < j.
For each pair, check if newNums[i] <= newNums[j] + diff.
If the condition is met, increment count.
Return count.

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 Analysis

Time Complexity: O(n^2). The two nested loops iterate through approximately `n^2 / 2` pairs. For `n = 10^5`, this is too slow.Space Complexity: 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.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Highly inefficient and will result in a "Time Limit Exceeded" error for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Number of Pairs Satisfying Inequality. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Number of Pairs Satisfying Inequality

Algorithms:

Binary SearchDivide and ConquerMerge Sort

Data Structures:

ArrayBinary Indexed TreeSegment TreeOrdered Set