Problem statement

https://leetcode.com/problems/count-pairs-in-two-arrays/

Solution 1

Actually, what we need to find is number of pairs nums1[i] - nums2[i] > nums2[j] - nums1[j], such that i < j. From this moment problem becomes almost the same as 0315 Count of Smaller Numbers After Self with only difference that we need to put -num to our sorted list, because if we define nums3 = nums1 - nums2, we are looking for pairs nums3[i] > -nums3[j], where i < j.

Complexity

It is O(n log n) for time and O(n) for space.

Code

from sortedcontainers import SortedList

class Solution:
    def countPairs(self, nums1, nums2):
        nums3 = [x-y for x,y in zip(nums1, nums2)]
        SList, ans = SortedList(), []
        
        for num in nums3[::-1]:
            ind = SortedList.bisect_left(SList, num)
            ans.append(ind)
            SList.add(-num)
            
        return sum(ans)

Solution 2

If fact we are looking for pairs nums3[i] + nums3[j] > 0, which is symmetric with respect to i and j, so we can forgot condition i < j and look for all pairs where i != j. So, what we can do is to sort nums3 and then use binary search or two pointers approach to find desired number of pairs, using technique similar to 2sum.

Complexity

It is still O(n log n) for time and O(n) for space.

Code

class Solution:
    def countPairs(self, nums1, nums2):
        nums3 = sorted([x1 - x2 for x1, x2 in zip(nums1, nums2)])
        beg, end, ans = 0, len(nums3) - 1, 0
        while beg < end:
            if nums3[beg] + nums3[end] > 0:
                ans += (end - beg)
                end -= 1
            else:
                beg += 1
        
        return ans