Number of pairs that satisfies the range condition (lower <= p[i] - p[j] <= upper)

 

How does one can find the number of pairs in an array that satisfies the below condition?

: lower <= p[i] - p[j] <= upper

 

The simplest and most intuitive approach would be iterating over all the pairs of the array, which would be O(N**2).

 

The mergesort approach, on the other hand, can solve the problem in O(NlogN).

 

The below question should be addressed with the same method.

327. Count of Range Sum

https://leetcode.com/problems/count-of-range-sum/description/

Count of Range Sum - LeetCode

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        pSum = [0]
        for num in nums:
            pSum.append(pSum[-1] + num)
        ret = 0
        def mergeSort(pSum, left, right):
            if left == right:
                return [pSum[left]]
            nonlocal lower, upper, ret
            mid = (left + right) // 2
            lSum = mergeSort(pSum, left, mid)
            rSum = mergeSort(pSum, mid+1, right)
            l, r = 0, 0
            for lVal in lSum:
                while r < len(rSum) and rSum[r] - lVal <= upper:
                    r += 1
                while l < len(rSum) and rSum[l] - lVal < lower:
                    l += 1
                ret += r - l
            pSum[left:right+1] = sorted(pSum[left:right+1])
            return pSum[left:right+1]
        mergeSort(pSum, 0, len(pSum)-1)
        return ret

 

315. Count of Smaller Numbers After Self

https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

Count of Smaller Numbers After Self - LeetCode

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        N = len(nums)
        ret = [0] * N
        def mergesort(iarr, left, right):
            if left == right:
                return [iarr[left]]
            mid = (left + right) // 2
            larr = mergesort(iarr, left, mid)
            rarr = mergesort(iarr, mid+1, right)
            j = 0
            for i in larr:
                n1 = nums[i]
                while j < len(rarr) and nums[rarr[j]] < n1:
                    j += 1
                ret[i] += j
            iarr[left:right+1] = sorted(iarr[left:right+1], key=lambda i: nums[i])
            return iarr[left:right+1]
        mergesort([i for i in range(N)], 0, N-1)
        return ret