LeetCode Solutions Blog

Number of Pairs Satisfying Inequality

Number: 2513

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given two 0-indexed integer arrays nums1 and nums2 of equal length and an integer diff, count the number of index pairs (i, j) with 0 <= i < j < n such that: nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff. In other words, after rearranging terms, we need to count pairs with: (nums1[i] - nums2[i]) <= (nums1[j] - nums2[j]) + diff.

Key Insights

Transform the problem by defining a new array value: diff_arr[i] = nums1[i] - nums2[i].
The inequality becomes: diff_arr[i] <= diff_arr[j] + diff for i < j.
For every index j, count how many earlier indices i have a diff_arr value <= diff_arr[j] + diff.
Use data structures such as Binary Indexed Tree (Fenwick Tree) or balanced BST to count the number of valid indices efficiently.
Discretize the values since nums1 and nums2 lie in a moderate range but the computed differences can be shifted by diff.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting for discretization and BIT operations for each element. Space Complexity: O(n) for the BIT and the discretized mapping.

Solution

The idea is to pre-compute an array diff_arr where each element is computed as nums1[i] - nums2[i]. The problem then reduces to counting, for each index j, the number of indices i < j that satisfy: diff_arr[i] <= diff_arr[j] + diff. A Binary Indexed Tree (BIT) is used to maintain counts of previously seen diff_arr values (after discretization). We discretize the possible values (both diff_arr and diff_arr[j] + diff) to map them onto indices in the BIT. As we iterate through diff_arr from left to right, we query the BIT for how many indices have values less than or equal to diff_arr[j] + diff. Then update the BIT with the current diff_arr[j]. This counts all valid pairs in an efficient manner.

Code Solutions

# Python solution using a Binary Indexed Tree (BIT)

class BIT:
    # Initialize BIT with given size
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)
        
    # Update BIT at index i (1-indexed) with value delta
    def update(self, i, delta):
        while i <= self.size:
            self.tree[i] += delta
            i += i & -i
            
    # Query BIT: get the prefix sum for index i (1-indexed)
    def query(self, i):
        result = 0
        while i > 0:
            result += self.tree[i]
            i -= i & -i
        return result

def numberOfPairs(nums1, nums2, diff):
    n = len(nums1)
    # Compute the difference array where each element is nums1[i] - nums2[i]
    diff_arr = [nums1[i] - nums2[i] for i in range(n)]
    
    # Prepare a sorted list of all values that we will query/update:
    # Include each diff_arr[j] and diff_arr[j] + diff for proper discretization.
    all_values = []
    for val in diff_arr:
        all_values.append(val)
        all_values.append(val + diff)
    sorted_values = sorted(set(all_values))
    
    # Map each value to its discretized index (1-indexed for BIT)
    value_to_index = {value: i+1 for i, value in enumerate(sorted_values)}
    
    # Initialize BIT based on the number of unique values
    bit = BIT(len(sorted_values))
    result = 0
    
    # Iterate over diff_arr elements
    for val in diff_arr:
        # Query BIT: count number of previous indices where stored value <= current val + diff
        index_query = value_to_index[val + diff]
        result += bit.query(index_query)
        # Add current diff_arr value into BIT for later queries
        index_update = value_to_index[val]
        bit.update(index_update, 1)
        
    return result

# Example usage:
nums1 = [3, 2, 5]
nums2 = [2, 2, 1]
diff = 1
print(numberOfPairs(nums1, nums2, diff))  # Output should be 3