2824. Count Pairs Whose Sum is Less than Target

Problem Statement

link: LeetCode.cn LeetCode Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

Example:

Input: nums = [-1,1,2,3,1], target = 2 Output: 3

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2 Output: 10

Constraints: 1 <= nums.length == n <= 50 -50 <= nums[i], target <= 50

Solution Approach

Sort the array and use the two-pointer technique to efficiently count pairs whose sum is less than the given target.

Algorithm

1. Sorting: Start by sorting the array to enable efficient pair comparison.
2. Two-Pointer Technique: Use two pointers, one starting from the beginning and the other from the end of the sorted array, to find valid pairs whose sum is less than the target.
3. Count Valid Pairs: Incrementally adjust the pointers and count the pairs while ensuring that the sum of the current pair is less than the target.

Implement

    class Solution:
  def countPairs(self, nums: List[int], target: int) -> int:
      nums.sort()
      i, j = 0, len(nums) - 1
      res = 0
      while i < j:
          while i < j and nums[i] + nums[j] >= target:
              j -= 1
          res += j - i
          i += 1
      return res
  

    
    

Twitter  facebook  Email