#2426

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Number of Pairs Satisfying Inequality

Count pairs in two arrays satisfying a given inequality condition using binary search over the valid answer space.

array binary search divide and conquer binary indexed tree segment tree

Problem Statement

You are given two integer arrays nums1 and nums2, both of size n, and an integer diff. The goal is to find how many pairs of indices (i, j) satisfy the condition nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff, with the restriction i < j. Your task is to return the number of valid pairs that satisfy this inequality.

The problem requires an efficient approach since the size of the arrays can go up to 10^5, making brute force solutions infeasible. The correct solution involves leveraging binary search or other efficient methods to handle large inputs within the time constraints.

Examples

Example 1

Input: nums1 = [3,2,5], nums2 = [2,2,1], diff = 1

Output: 3

There are 3 pairs that satisfy the conditions:

i = 0, j = 1: 3 - 2 <= 2 - 2 + 1. Since i < j and 1 <= 1, this pair satisfies the conditions.
i = 0, j = 2: 3 - 5 <= 2 - 1 + 1. Since i < j and -2 <= 2, this pair satisfies the conditions.
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

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

Solution Approach

Rearrange the Equation

First, rearrange the inequality nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff into a simpler form. This will help identify the nature of the valid pairs and allow us to optimize the search for matching pairs.

Binary Search for Efficiency

Next, use binary search over the possible valid answer space to efficiently count pairs that satisfy the inequality. This can significantly reduce the time complexity compared to a brute force approach.

Leverage Sorted Data for Fast Lookups

By sorting one of the arrays, we can perform binary search on the second array to quickly determine how many valid pairs exist for each element. This method reduces unnecessary comparisons and speeds up the solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the final approach. Using binary search can reduce the time complexity to O(n log n), where n is the size of the arrays. Sorting one of the arrays and performing binary search over the other array is the key to achieving this efficient solution.

What Interviewers Usually Probe

Ability to simplify a complex inequality and recognize optimization opportunities.
Familiarity with binary search and how it can be applied to this problem.
Experience with handling large input sizes efficiently using sorted data structures or binary search.

Common Pitfalls or Variants

Common pitfalls

Neglecting to rearrange the inequality equation properly, leading to inefficient or incorrect comparisons.
Attempting to solve the problem with a brute force approach, resulting in time complexity issues for large inputs.
Forgetting the constraint that i must be less than j, which can lead to incorrect pair counting.

Follow-up variants

The problem can be extended by adding additional constraints or modifying the inequality condition to require more complex checks.
Instead of two arrays, consider cases where you have more than two arrays and must find pairs satisfying inequalities between them.
Introduce additional parameters to the inequality condition to further explore optimizations or extend the problem to higher-dimensional arrays.

FAQ

What is the best way to approach the Number of Pairs Satisfying Inequality problem?

Rearrange the inequality equation, then use binary search or a sorted array to efficiently count the valid pairs.

How do I handle large inputs in this problem?

Use binary search on the sorted array to reduce unnecessary comparisons and improve the time complexity to O(n log n).

What are common mistakes when solving this problem?

Common mistakes include neglecting the rearrangement of the inequality, using brute force approaches, and forgetting the i < j constraint.

Can the solution be extended to multiple arrays?

Yes, you can extend the approach to handle more arrays, but careful management of the inequality condition is necessary.

How does binary search optimize the solution here?

Binary search allows you to quickly determine how many valid pairs exist for each element in the sorted array, greatly improving efficiency.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

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 ans

Continue Practicing

#2179 count good triplets in an array #1649 create sorted array through instructions #493 reverse pairs