Count Pairs Whose Sum is Less than Target

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 1:

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.

Example 2:

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
- (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
- (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
- (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
- (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
- (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
- (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
- (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
- (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target

Constraints:

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

Brute Force Solution

The most straightforward way to solve this problem is to iterate through all possible pairs of indices (i, j) such that 0 <= i < j < n and check if nums[i] + nums[j] < target. If it is, we increment a counter.

def count_pairs_brute_force(nums, target):
    n = len(nums)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] < target:
                count += 1
    return count

# Example usage
nums1 = [-1, 1, 2, 3, 1]
target1 = 2
print(f"Example 1: {count_pairs_brute_force(nums1, target1)}")  # Output: 3

nums2 = [-6, 2, 5, -2, -7, -1, 3]
target2 = -2
print(f"Example 2: {count_pairs_brute_force(nums2, target2)}")  # Output: 10

Time and Space Complexity of Brute Force Solution

Time Complexity

The brute-force solution has a time complexity of O(n^2) because it involves nested loops. The outer loop runs n times, and the inner loop runs approximately n/2 times on average. This results in n * (n/2) operations, which simplifies to O(n^2).

Space Complexity

The space complexity of the brute-force solution is O(1) because it only uses a constant amount of extra space. The algorithm uses a counter variable to keep track of the number of pairs, but it doesn't use any additional data structures that scale with the input size.

Optimal Solution (Using Sorting and Two Pointers)

To improve the time complexity, we can sort the array first and then use a two-pointer approach. This will allow us to find pairs that satisfy the condition in O(n) time after the sorting.

def count_pairs_optimal(nums, target):
    nums.sort()
    n = len(nums)
    left = 0
    right = n - 1
    count = 0
    
    while left < right:
        if nums[left] + nums[right] < target:
            count += right - left  # All pairs (left, left+1), (left, left+2), ..., (left, right) satisfy the condition
            left += 1
        else:
            right -= 1
    
    return count

# Example usage
nums1 = [-1, 1, 2, 3, 1]
target1 = 2
print(f"Example 1: {count_pairs_optimal(nums1, target1)}")  # Output: 3

nums2 = [-6, 2, 5, -2, -7, -1, 3]
target2 = -2
print(f"Example 2: {count_pairs_optimal(nums2, target2)}")  # Output: 10

Time and Space Complexity of Optimal Solution

Time Complexity

The optimal solution has a time complexity of O(n log n) due to the sorting step. After sorting, the two-pointer approach takes O(n) time. Thus, the overall time complexity is dominated by the sorting step, which is O(n log n).

Space Complexity

• If the sorting algorithm uses O(1) space (e.g., heapsort), the space complexity is O(1).
• If the sorting algorithm uses O(n) space (e.g., merge sort), the space complexity is O(n).

In Python, nums.sort() is implemented using the Timsort algorithm, which has O(n) space complexity in the worst case and O(1) in the best case. For the sake of this problem, we can assume the space complexity is closer to O(1).

Edge Cases

1. Empty Array: If the input array nums is empty, there are no pairs, so the function should return 0.
2. Array with One Element: If the input array has only one element, there are no pairs, so the function should return 0.
3. All Elements are the Same: The algorithm should correctly handle cases where all elements in the array are the same.
4. Target is Very Large or Very Small: The algorithm should work correctly regardless of how large or small the target value is.
5. Integer Overflow: When summing nums[i] + nums[j], ensure that the result does not cause an integer overflow. Given the constraints, this is not a concern since -50 <= nums[i], target <= 50.

Here's the code that handles the edge cases:

def count_pairs_optimal_with_edge_cases(nums, target):
    n = len(nums)
    if n <= 1:
        return 0

    nums.sort()
    left = 0
    right = n - 1
    count = 0

    while left < right:
        if nums[left] + nums[right] < target:
            count += right - left
            left += 1
        else:
            right -= 1

    return count