Count Pairs Whose Sum is Less than Target

Easy

Bloomberg LP

0 views

Topics:

ArraysTwo Pointers

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

Count Pairs Whose Sum is Less than Target

Easy

Bloomberg LP

0 views

Topics:

ArraysTwo Pointers

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array? Can they be negative?
What is the maximum size of the `nums` array? Is the array ever empty or null?
Is the target value within a reasonable range compared to the values in `nums`, such that overflow during the sum calculation is not a concern?
If no pairs satisfy the condition, should I return 0?
Can the same number be part of multiple valid pairs (i.e., if `nums = [1, 2, 3]` and `target = 5`, should (1, 2) and (1, 3) both be counted if the indices are different)?

Brute Force Solution

Approach

The brute force method involves checking every possible combination of two numbers from the list to see if their sum meets our condition. It's like comparing each item with every other item to find matches. We will simply go through all possible pairings.

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Add it to every other number in the list, one at a time.
Each time you add two numbers together, check if the sum is less than the target number.
If the sum is less than the target, count it as a valid pair.
Move to the second number in the list, and repeat the process of adding it to every other number.
Continue this process for each number in the list until you've checked all possible pairs.
Finally, add up the total number of valid pairs you counted.

Code Implementation

def count_pairs_brute_force(numbers, target):
    pair_count = 0
    # Iterate through each number in the list.
    for first_index in range(len(numbers)):

        # For each number, iterate through the rest of the list.
        for second_index in range(first_index + 1, len(numbers)):
            # Compare the sum of the pair to the target.
            if numbers[first_index] + numbers[second_index] < target:
                pair_count += 1

    return pair_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through each number in the list of size n. For each number, it then compares it with every other number in the list to check if their sum is less than the target. This nested comparison results in roughly n operations for each of the n numbers. Consequently, the total number of comparisons approximates n * n/2. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The brute force approach described involves iterating through the input list and comparing pairs of numbers. No additional data structures, such as arrays or hash maps, are created to store intermediate results or visited elements. The algorithm only uses a few constant-size variables for indexing and counting the pairs. Therefore, the auxiliary space required does not depend on the input size N, and the space complexity is O(1).

Optimal Solution

Approach

The most efficient way to find these pairs involves first arranging the numbers in order from smallest to largest. Then, we can use a clever approach that avoids checking every single possible pair, saving a lot of time.

Here's how the algorithm would work step-by-step:

First, put all the numbers in order, from smallest to largest.
Start by looking at the smallest number in the list.
Find the largest number in the list that, when added to the smallest number, is still less than the target number.
Count how many numbers are between the smallest number and that largest number you just found (including the largest number). This tells you how many pairs you can make with that smallest number that meet the criteria.
Move to the next smallest number in the list.
Repeat the process, but you don't need to check numbers you've already considered. Since the list is in order, you only need to look at numbers that are to the right of the current smallest number.
Continue this until you've checked all the numbers, and add up the counts you found for each number. The total is the number of pairs that add up to less than the target.

Code Implementation

def count_pairs_less_than_target(numbers, target):
    numbers.sort()
    count_of_pairs = 0
    left_index = 0

    while left_index < len(numbers):
        right_index = len(numbers) - 1

        # Find the rightmost index such that the sum is less than the target
        while left_index < right_index and numbers[left_index] + numbers[right_index] >= target:
            right_index -= 1

        # If the indices are the same, no pairs are found.
        if left_index == right_index:
            left_index += 1
            continue

        # Count pairs: All elements between left and right form valid pairs
        count_of_pairs += right_index - left_index

        left_index += 1

    return count_of_pairs

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first sorts the input array of size n, which takes O(n log n) time. Then, for each element in the sorted array, it performs a search for the largest number such that their sum is less than the target. This search can be implemented efficiently using binary search, which takes O(log n) time. Since this binary search is performed for each of the n elements, the total time complexity for this part is O(n log n). Therefore, the overall time complexity is dominated by the sorting step and the subsequent searches, resulting in O(n log n).

Space Complexity

O(1) – The algorithm first sorts the input array, but we're analyzing auxiliary space which excludes modifying the input in place. The explanation describes iterating through the sorted array with two pointers, keeping track of the smallest and largest numbers to form pairs. This approach does not require any additional data structures that scale with the input size N (the number of elements in the input array). Only a few variables are used to store indices and potentially a count, resulting in constant auxiliary space.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty because there are no pairs.
Input array with less than two elements	Return 0 because at least two elements are needed to form a pair.
Input array with all elements equal	The solution should correctly count pairs meeting the condition even if all elements are the same.
Input array contains negative numbers	The algorithm must handle negative numbers correctly when calculating the sum of pairs.
Input array contains zero	The presence of zero should not impact the correctness of the pair counting.
Target value is very large, potentially causing integer overflow during summation	Using a language with potential for integer overflow should either use a larger numeric type or carefully check for overflow during calculation.
Target value is very small, potentially leading to many pairs satisfying the condition.	The algorithm's complexity should handle scenarios where many or all pairs meet the condition.
Input array contains very large or very small numbers which could cause an integer overflow if added	Use a data type with sufficient range or check for potential overflow before adding the numbers.