LC1885. Count Pairs in Two Arrays

Approach 1: Binary Search

from bisect import bisect_right
 
class Solution:
    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        # Reorder the eqn such that it becomes:
        #    (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0
        n = len(nums1)
        diffs = [nums1[i] - nums2[i] for i in range(n)]
        
        # Since we just need the count of indexes, we can sort and do
        # binary search to optimize (no need to worry about i < j)
        diffs.sort()
 
        total = 0
        for i in range(n):
            # Anything coming after diffs[i] will also be +ve and hence
            # satisfy diffs[i] + diffs[j] > 0
            if diffs[i] > 0:
                total += n - i - 1
                continue
            
            # bisect_right does binary search to find a `lo` that comes RIGHT AFTER
            # all elements <= 0 (the key fn turns `diffs` into list of diff[i] + diff[j]
            # for only comparison purposes)
            pos = bisect_right(diffs, 0, lo=i+1, key=lambda v: v + diffs[i])
            total += n - pos
        
        return total

Complexity

Time: $O(nlogn)$
Space: $O(n)$

Notes

See bisect_right docs for more info.

Approach 1: Two-Pointer

from bisect import bisect_right
 
class Solution:
    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        # Reorder the eqn such that it becomes:
        #    (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0
        n = len(nums1)
        diffs = [nums1[i] - nums2[i] for i in range(n)]
        
        # Since we just need the count of indexes, we can sort
        # (no need to worry about i < j)
        diffs.sort()
 
        total = 0
        left, right = 0, n - 1
        
        while left < right:
            # Surely if this is true, anything from diffs[left+1] onwards
            # must be bigger than diffs[left] and hence satisfy the inequality
            if diffs[left] + diffs[right] > 0:
                total += right - left
                right -= 1
            else:
                left += 1
        
        return total

Complexity

Time: $O(nlogn)$ — but faster than binary search approach since in the latter, we have to do another $O(nlogn)$ to find the pairs using binary search.
Space: $O(n)$

Other Languages