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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Pairs Whose Sum is Less than Target

Number: 2917

Difficulty: Easy

Paid? No

Companies: Amazon, Meta, josh technology, Accenture

Problem Description

Given a 0-indexed integer array nums and an integer target, count the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] is strictly less than target.

Key Insights

  • Sorting the array helps to efficiently find pairs based on their sum.
  • A two-pointer technique can be used after sorting: one pointer starts at the beginning and the other at the end.
  • If the sum of the elements at the two pointers is less than the target, then all elements between the left pointer and the right pointer form valid pairs with the left element.
  • Adjust pointers accordingly to avoid checking redundant pairs.

Space and Time Complexity

Time Complexity: O(n log n), due to the initial sort and O(n) for the two-pointer traversal. Space Complexity: O(1) if sorting is done in-place (ignoring the space for sorting), otherwise O(n).

Solution

The solution begins by sorting the array. With the array sorted, initialize two pointers: left at the start and right at the end of the array. At each step, if the sum of the elements at these pointers is less than the target, then every index between left and right forms a valid pair with left (since the array is sorted). Add (right - left) to the count and move the left pointer forward. If the sum is not less than the target, move the right pointer backward to try and reduce the sum. Continue this process until the two pointers meet. This method leverages the sorted order to efficiently count valid pairs without checking every combination.

Code Solutions

# Python solution using two pointers after sorting the array.
def count_pairs(nums, target):
    # Sort the input array
    nums.sort()
    count = 0
    left, right = 0, len(nums) - 1

    # Use two pointers to traverse the array
    while left < right:
        # If the current pair sum is less than target
        if nums[left] + nums[right] < target:
            # All pairs (left, left+1), (left, left+2), ..., (left, right) are valid.
            count += right - left
            # Move left pointer to check next element
            left += 1
        else:
            # Sum too large, move right pointer to reduce the sum
            right -= 1

    return count

# Example usage:
print(count_pairs([-1, 1, 2, 3, 1], 2))  # Output: 3
← Back to All Questions