We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Pairs Whose Sum is Less than Target

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem requires counting pairs of indices where the sum of the corresponding elements is less than a given target.
  • A brute-force approach would involve checking all possible pairs, which can be inefficient.
  • A more efficient approach can leverage sorting and the two-pointer technique to reduce the time complexity.

Space and Time Complexity

Time Complexity: O(n log n) for sorting, followed by O(n) for the two-pointer traversal. Overall, it is O(n log n). Space Complexity: O(1) if sorting in place, or O(n) if using additional space for a copy of the array.

Solution

To solve this problem, we first sort the array. Once sorted, we can use two pointers to efficiently count the valid pairs. The left pointer starts at the beginning of the array, while the right pointer starts just after the left pointer. For each position of the left pointer, we find the maximum position of the right pointer such that the sum of the elements at these indices is less than the target. This allows us to count all valid pairs in one pass.

Code Solutions

def countPairs(nums, target):
    nums.sort()  # Sort the array
    count = 0
    n = len(nums)
    
    for i in range(n):
        left = i + 1  # Start the right pointer just after the left pointer
        right = n - 1  # Start the right pointer at the end of the array
        
        while left <= right:
            if nums[i] + nums[left] < target:
                count += (right - left)  # All pairs (i, left), (i, left+1), ..., (i, right) are valid
                break
            left += 1  # Move the left pointer to the right
    
    return count
← Back to All Questions