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

def count_pairs(nums, target):
    """Counts the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target."""
    count = 0
    n = len(nums)
    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: nums = {nums1}, target = {target1}, output = {count_pairs(nums1, target1)}")

nums2 = [-6, 2, 5, -2, -7, -1, 3]
target2 = -2
print(f"Example 2: nums = {nums2}, target = {target2}, output = {count_pairs(nums2, target2)}")

Brute Force Solution

The most straightforward approach is to iterate through all possible pairs of indices (i, j) such that 0 <= i < j < n, calculate the sum nums[i] + nums[j], and increment a counter if the sum is less than the target. This approach checks all possible pairs to ensure we find every pair that satisfies the condition.

Optimal Solution

The provided code implements the brute force solution, which is also the optimal solution in terms of space complexity. While we could consider sorting the array to potentially optimize the search, the constraints (n <= 50) make the overhead of sorting unnecessary. The brute force approach is efficient enough for the given constraints and avoids the extra space complexity of other approaches.

Big(O) Run-time Analysis

The run-time complexity is O(n^2) because of the nested loops. The outer loop iterates n times, and the inner loop iterates approximately n times for each iteration of the outer loop. Therefore, the number of operations grows quadratically with the input size n.

Big(O) Space Usage Analysis

The space complexity is O(1) because we only use a constant amount of extra space, regardless of the input size. The variables count, n, i, and j use a fixed amount of memory. We do not use any data structures that scale with the input.

Edge Cases

1. Empty Array: If the input array nums is empty, the function will correctly return 0 because the loops will not execute.
2. Single Element Array: If the input array contains only one element, the function will also correctly return 0 because there are no pairs to consider (i < j condition will always be false).
3. All Numbers Sum to Less Than Target: If all possible pairs sum to a value less than the target, the function will correctly return the number of all possible pairs, which is n * (n - 1) / 2.
4. All Numbers Sum to Greater Than Target: If all possible pairs sum to a value greater than or equal to the target, the function will correctly return 0.
5. Negative Numbers: The code handles negative numbers correctly, as demonstrated in the example cases.
6. Duplicate Numbers: Duplicates in the array are correctly handled, as all unique pairs of indices are considered and checked against the target.