Leetcode: 2426. Number of Pairs Satisfying Inequality

Pattern: Compute values for all pair in array. Can we simplify the problem while keeping it the same? The condition can be stated as \(n_1[i]-n_2[i]-diff \leq n_1[j]-n_2[j]\). Can we state the problem as result of multiple searches? For each position \(i\), we search for the smallest \(j\) that satisfy the condition. Time complexity is \(O(n \log n)\) and space is \(O(n)\).

from sortedcontainers import SortedList
from typing import List

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:
        N = len(nums1)
        s = SortedList()
        ans = 0
        for i in range(N - 1, -1, -1):
            ans += len(s) - s.bisect_left(nums1[i] - nums2[i] - diff)
            s.add(nums1[i] - nums2[i])
        return ans