LeetCode 1885: Count Pairs in Two Arrays

Brute Force

Check sum1 > sum2

Time: $\mathcal{O}(n^2)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        count = 0
        n = len(nums1)
        for i in range(n-1):
            for j in range(i+1, n):
                sum1 = nums1[i] + nums1[j]
                sum2 = nums2[i] + nums2[j]
                count += (1 if sum1 > sum2 else 0)
        return count

Check diff1 + diff2 > 0

We check against a modified version of the inequality: (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0. An important difference is that outer loop is only handling the index i and the inner loop is only handling the index j.

Time: $\mathcal{O}(n^2)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        count = 0
        n = len(nums1)
        for i in range(n-1):
            diff1 = nums1[i] - nums2[i]
            for j in range(i+1, n):
                diff2 = nums1[j] - nums2[j]
                count += (1 if diff1 + diff2 > 0 else 0)
        return count

Sorted diffs

For each diff1 the inner loop is counting valid diff2‘s in $\mathcal{O}(n)$ time. We could compute on a sorted list of diffs to make the inner loop $\mathcal{O}(\lg{n})$ .

With a sorted list of diffs, we could consider each diff as the left diff ( $d_l = \text{nums1}[i] - \text{nums2}[i]$ ) and could efficiently find how many diffs on its right ( $d_r = \text{nums1}[j] - \text{nums2}[j]$ ) are bigger than $-d_l$ . Because, we could binary-search for the leftmost occurrence of $x \ge -d_l + 1$ . All diffs from thereon work as $d_r$ such that $d_l + d_r > 0$ .

Time: $\mathcal{O}(n \cdot \lg{n})$ , space: $\mathcal{O}(n)$ .

class Solution:
    def find_leftmost_index(self, x, nums, begin) -> int:
        lo, hi = begin, len(nums)-1
        pos = -1
        while lo <= hi:
            mid = (lo+hi) // 2
            if nums[mid] < x:
                lo = mid+1
            else:
                pos = mid
                hi = mid-1
        return pos

    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        diffs = sorted(x-y for x, y in zip(nums1, nums2))
        count, n = 0, len(diffs)
        for i, d1 in enumerate(diffs):
            least_d2 = -d1+1
            pos = self.find_leftmost_index( least_d2, diffs, i+1 )
            if pos < 0:
                continue
            count += (n-pos)
        return count

Two pointers

In the sorted array, given a target, we can count all pairs with sum bigger than target in one scan. Here we use target = 0.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(n)$ .

class Solution:
    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        diffs = sorted(x-y for x, y in zip(nums1, nums2))
        count, n = 0, len(diffs)
        i, j = 0, n-1
        while i < j:
            diff_sum = diffs[i] + diffs[j]
            if diff_sum <= 0:
                i += 1
            else:
                count += (j-i)
                j -= 1
        return count

unreasonably effective