unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 2824: Count Pairs Whose Sum is Less than Target

Sort and two pointers

In sorted order, if nums[i] + nums[j] < target, then with nums[i] as the first element there are (j-i) second elements that can make a valid pair.

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

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        # [-1 1 1 2 3]
        #   0 1 2 3 4 

        # [-6  2  5 -2 -7 -1 3]
        #   0  1  2  3  4  5 6
        # [-7 -6 -2 -1  2  3 5], target = -2
        # -7: 5
        # -6: 4
        # -2: 1

        pair_count = 0
        nums.sort()
        left, right = 0, len(nums)-1
        while left < right:
            pair_sum = nums[left] + nums[right]
            if pair_sum < target:
                pair_count += (right-left)
                left += 1
            else:
                right -= 1

        return pair_count

tanvirdotzaman

, ,

Leave a comment