Jobs

Interviews

Discussions

Count the Number of Fair Pairs

Medium

Asked by:

More companies

39 views

Topics:

ArraysTwo PointersBinary Search

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

0 <= i < j < n, and
lower <= nums[i] + nums[j] <= upper

Example 1:

Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6
Output: 6
Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

Example 2:

Input: nums = [1,7,9,2,5], lower = 11, upper = 11
Output: 1
Explanation: There is a single fair pair: (2,3).

Constraints:

1 <= nums.length <= 10⁵
nums.length == n
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= lower <= upper <= 10⁹

Try coding it in LeetCode

Count the Number of Fair Pairs

Medium

Asked by:

39 views

Topics:

ArraysTwo PointersBinary Search

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

0 <= i < j < n, and
lower <= nums[i] + nums[j] <= upper

Example 1:

Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6
Output: 6
Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

Example 2:

Input: nums = [1,7,9,2,5], lower = 11, upper = 11
Output: 1
Explanation: There is a single fair pair: (2,3).

Constraints:

1 <= nums.length <= 10⁵
nums.length == n
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= lower <= upper <= 10⁹

Try coding it in LeetCode

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 are the constraints on the size of the `nums` array, and the ranges for `lower` and `upper`, as well as the values within `nums`? This will help me understand the potential performance implications.
Can `nums` contain negative numbers, zeros, or duplicate values? If so, how should they be handled?
If no fair pairs exist, should I return 0?
Are `lower` and `upper` inclusive bounds for the sum of pairs?
Could the input array be empty or null? If so, what should the function return?

Brute Force Solution

Approach

The brute force approach to finding fair pairs is like checking every possible combination of numbers to see if they meet the fairness criteria. We will consider each pair of numbers in the given collection one by one. We will then count how many of these pairs are deemed 'fair'.

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

Take the first number in the collection.
Pair it with every other number in the collection, including itself.
For each pair, check if the sum of the two numbers falls within the given fairness range.
If the sum is within the range, mark this pair as a 'fair' pair.
Move to the next number in the collection.
Repeat the process of pairing it with every other number and checking for fairness.
Continue this until you've considered every number in the collection and its pairs.
Finally, count the total number of 'fair' pairs you've identified.

Code Implementation

def count_fair_pairs_brute_force(numbers, lower_bound, upper_bound):
    fair_pair_count = 0

    # Iterate through each number in the list.
    for first_index in range(len(numbers)):

        # For each number, iterate through all other numbers (including itself)
        for second_index in range(len(numbers)):

            # Calculate the sum of the current pair.
            current_sum = numbers[first_index] + numbers[second_index]

            # Check if the sum falls within the specified range.
            # If it does, increment the fair pair count.
            if lower_bound <= current_sum <= upper_bound:
                fair_pair_count += 1

    return fair_pair_count

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through the input array of size n. For each element, it then iterates through the entire array again to form pairs. Thus, for each of the n elements, we perform n operations of forming and checking a pair. Therefore, the total number of operations is proportional to n * n, which gives a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through pairs of numbers in the input collection without creating any auxiliary data structures like lists, hash maps, or sets to store intermediate results or track visited pairs. It only uses a fixed number of variables, such as loop counters or temporary variables for calculations. Therefore, the space used does not depend on the input size N (the number of elements in the collection), and the space complexity is constant.

Optimal Solution

Approach

To efficiently count fair pairs, we will sort the numbers first. Then, we'll use a clever approach to quickly find how many pairs meet the fairness criteria without checking every single combination.

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

First, put the list of numbers in order from smallest to largest.
Pick a number from the sorted list.
Use a fast searching technique to find the first number in the list that, when added to the picked number, equals or exceeds the lower limit.
Do the same to find the first number in the list that, when added to the picked number, exceeds the upper limit.
The difference between these two positions tells you how many numbers satisfy the lower and upper limit criteria when paired with the picked number.
Add this count to the total count of fair pairs.
Repeat the process for each number in the sorted list, making sure not to double-count pairs by only considering combinations after the current number.
The final count represents the total number of fair pairs in the original list.

Code Implementation

def count_fair_pairs(numbers, lower_limit, upper_limit):
    numbers.sort()
    number_of_fair_pairs = 0

    for first_index in range(len(numbers)):

        #Avoid double counting by checking pairs ahead
        for second_index in range(first_index + 1, len(numbers)):
            sum_of_pair = numbers[first_index] + numbers[second_index]

            # Check if the pair meets fairness criteria
            if lower_limit <= sum_of_pair <= upper_limit:
                number_of_fair_pairs += 1

    return number_of_fair_pairs

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operations in this approach are sorting the input array and performing binary searches within a loop. Sorting the array of n elements takes O(n log n) time. Then, for each of the n elements in the sorted array, we perform two binary searches, each taking O(log n) time. Therefore, the binary searches within the loop contribute O(n log n) to the total time complexity. Combining sorting and searching, the overall time complexity is O(n log n) + O(n log n), which simplifies to O(n log n).

Space Complexity

O(1) – The algorithm primarily uses a sorted version of the input array. Since the sorting operation can be done in-place or might create a copy depending on the implementation details, let's assume the best case scenario that it's done in-place, or that the sorted array is already the input itself. It also uses a few integer variables to keep track of indexes and counts, such as the current element's index and the count of fair pairs. These integer variables consume a constant amount of extra space regardless of the input array's size, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 if the input array is empty because no pairs can be formed.
Array with only one element	Return 0 as a pair requires at least two elements, and the problem definition specifies i < j.
Array with two elements where the sum falls outside the range [lower, upper]	Return 0 because the single possible pair is not fair.
Array with two elements where the sum falls inside the range [lower, upper]	Return 1 because the single possible pair is fair.
Large array with many fair pairs	Ensure the chosen algorithm (e.g., sorting and two-pointers) scales efficiently to avoid exceeding time limits.
Array with all identical values	The algorithm should correctly count the number of valid pairs (i, j) where i < j when all values are the same.
Negative numbers, zeros, and positive numbers in the array	The algorithm must correctly handle negative, zero, and positive numbers without causing unexpected behavior such as integer overflows or incorrect comparisons.
lower > upper	Return 0 since no sum can be between lower and upper and therefore there are no fair pairs.

Empty input array

How to Handle:

Return 0 if the input array is empty because no pairs can be formed.

Array with only one element

How to Handle:

Return 0 as a pair requires at least two elements, and the problem definition specifies i < j.

Array with two elements where the sum falls outside the range [lower, upper]

How to Handle:

Return 0 because the single possible pair is not fair.

Array with two elements where the sum falls inside the range [lower, upper]

How to Handle:

Return 1 because the single possible pair is fair.

Large array with many fair pairs

How to Handle:

Ensure the chosen algorithm (e.g., sorting and two-pointers) scales efficiently to avoid exceeding time limits.

Array with all identical values

How to Handle:

The algorithm should correctly count the number of valid pairs (i, j) where i < j when all values are the same.

Negative numbers, zeros, and positive numbers in the array

How to Handle:

The algorithm must correctly handle negative, zero, and positive numbers without causing unexpected behavior such as integer overflows or incorrect comparisons.

lower > upper

How to Handle:

Return 0 since no sum can be between lower and upper and therefore there are no fair pairs.

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 are the constraints on the size of the `nums` array, and the ranges for `lower` and `upper`, as well as the values within `nums`? This will help me understand the potential performance implications.
Can `nums` contain negative numbers, zeros, or duplicate values? If so, how should they be handled?
If no fair pairs exist, should I return 0?
Are `lower` and `upper` inclusive bounds for the sum of pairs?
Could the input array be empty or null? If so, what should the function return?

Brute Force Solution

Approach

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

Take the first number in the collection.
Pair it with every other number in the collection, including itself.
For each pair, check if the sum of the two numbers falls within the given fairness range.
If the sum is within the range, mark this pair as a 'fair' pair.
Move to the next number in the collection.
Repeat the process of pairing it with every other number and checking for fairness.
Continue this until you've considered every number in the collection and its pairs.
Finally, count the total number of 'fair' pairs you've identified.

Code Implementation

def count_fair_pairs_brute_force(numbers, lower_bound, upper_bound):
    fair_pair_count = 0

    # Iterate through each number in the list.
    for first_index in range(len(numbers)):

        # For each number, iterate through all other numbers (including itself)
        for second_index in range(len(numbers)):

            # Calculate the sum of the current pair.
            current_sum = numbers[first_index] + numbers[second_index]

            # Check if the sum falls within the specified range.
            # If it does, increment the fair pair count.
            if lower_bound <= current_sum <= upper_bound:
                fair_pair_count += 1

    return fair_pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To efficiently count fair pairs, we will sort the numbers first. Then, we'll use a clever approach to quickly find how many pairs meet the fairness criteria without checking every single combination.

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

First, put the list of numbers in order from smallest to largest.
Pick a number from the sorted list.
Use a fast searching technique to find the first number in the list that, when added to the picked number, equals or exceeds the lower limit.
Do the same to find the first number in the list that, when added to the picked number, exceeds the upper limit.
The difference between these two positions tells you how many numbers satisfy the lower and upper limit criteria when paired with the picked number.
Add this count to the total count of fair pairs.
Repeat the process for each number in the sorted list, making sure not to double-count pairs by only considering combinations after the current number.
The final count represents the total number of fair pairs in the original list.

Code Implementation

def count_fair_pairs(numbers, lower_limit, upper_limit):
    numbers.sort()
    number_of_fair_pairs = 0

    for first_index in range(len(numbers)):

        #Avoid double counting by checking pairs ahead
        for second_index in range(first_index + 1, len(numbers)):
            sum_of_pair = numbers[first_index] + numbers[second_index]

            # Check if the pair meets fairness criteria
            if lower_limit <= sum_of_pair <= upper_limit:
                number_of_fair_pairs += 1

    return number_of_fair_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 if the input array is empty because no pairs can be formed.
Array with only one element	Return 0 as a pair requires at least two elements, and the problem definition specifies i < j.
Array with two elements where the sum falls outside the range [lower, upper]	Return 0 because the single possible pair is not fair.
Array with two elements where the sum falls inside the range [lower, upper]	Return 1 because the single possible pair is fair.
Large array with many fair pairs	Ensure the chosen algorithm (e.g., sorting and two-pointers) scales efficiently to avoid exceeding time limits.
Array with all identical values	The algorithm should correctly count the number of valid pairs (i, j) where i < j when all values are the same.
Negative numbers, zeros, and positive numbers in the array	The algorithm must correctly handle negative, zero, and positive numbers without causing unexpected behavior such as integer overflows or incorrect comparisons.
lower > upper	Return 0 since no sum can be between lower and upper and therefore there are no fair pairs.

Empty input array

How to Handle:

Return 0 if the input array is empty because no pairs can be formed.

Array with only one element

How to Handle:

Return 0 as a pair requires at least two elements, and the problem definition specifies i < j.

Array with two elements where the sum falls outside the range [lower, upper]

How to Handle:

Return 0 because the single possible pair is not fair.

Array with two elements where the sum falls inside the range [lower, upper]

How to Handle:

Return 1 because the single possible pair is fair.

Large array with many fair pairs

How to Handle:

Ensure the chosen algorithm (e.g., sorting and two-pointers) scales efficiently to avoid exceeding time limits.

Array with all identical values

How to Handle:

The algorithm should correctly count the number of valid pairs (i, j) where i < j when all values are the same.

Negative numbers, zeros, and positive numbers in the array

How to Handle:

The algorithm must correctly handle negative, zero, and positive numbers without causing unexpected behavior such as integer overflows or incorrect comparisons.

lower > upper

How to Handle:

Return 0 since no sum can be between lower and upper and therefore there are no fair pairs.