• Leetcode POTDs

Problem 2563 Count the Number of Fair Pairs

Problem Statement

Link - Problem 2563

Question

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 <= 105
• nums.length == n
• -109 <= nums[i] <= 109
• -109 <= lower <= upper <= 109

Solution

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(),nums.end());
        long long ans = 0;
        for(int i=0;i<nums.size(); i++){
            auto right = upper_bound(nums.begin()+i+1,nums.end(),upper-nums[i]);
            auto left = lower_bound(nums.begin()+i+1,nums.end(),lower-nums[i]);
            ans += (right-left);
        }
        return ans;

    }
};

Complexity Analysis

| Algorithm                              | Time Complexity | Space Complexity |
| -------------------------------------- | --------------- | ---------------- |
| Modified Merge Sort with Binary Search | O(n log n)      | O(1)             |

Explanation

Intial Thoughts

When approaching a problem with pairs and constraints, consider first organizing the data if possible, as seen in the use of sorting. Then, identify potential pairs by narrowing the differences in values. This includes determining a range for the acceptable values, like using lower and upper bounds. Think about using ‘sliding window’ style solutions to reduce the total number of calculations needed, as there can be pairs of pairs. One can also notice the repeated subtraction in the potential calculation of the pairs; instead, compute each difference and then set conditions.

Intuitive Analysis

For fair pairs, see the bigger picture: instead of individually inspecting pairs one by one, slice the whole list of numbers and check individual ‘head-starts’ as we proceed in our sequence – which gives a relative space to efficiently spot pairs that we care about. Observe and then minimize the steps in computing potential valid pairs – it’s better to minimize redundant calculations instead of iterating and checking for every potential situation.

1. Intuition

• The problem can be solved by iterating over the array and for each element, finding the range of elements that can form a fair pair.
• To efficiently find the range of elements, we can use a sorted array and binary search.
• Sorting the array allows us to use upper_bound and lower_bound functions to find the range of elements in O(log n) time.
• The key insight is that for each element, we only need to consider the elements to its right to form a fair pair.
• This is because the problem statement specifies that i < j, so we can’t form a pair with an element to the left.
• Using upper_bound and lower_bound functions ensures that we don’t count duplicate pairs.
• The time complexity of this approach is O(n log n) due to the sorting and binary search.

2. Implementation

• The array is sorted using the sort(nums.begin(),nums.end()) function.
• The upper_bound function is used to find the upper limit of the range of elements that can form a fair pair, auto right = upper_bound(nums.begin()+i+1,nums.end(),upper-nums[i]).
• The lower_bound function is used to find the lower limit of the range of elements that can form a fair pair, auto left = lower_bound(nums.begin()+i+1,nums.end(),lower-nums[i]).
• The number of fair pairs for each element is calculated as the difference between the upper and lower limits, ans += (right-left).
• The for loop iterates over the array, and for each element, it calculates the number of fair pairs and adds it to the total count.
• The long long data type is used to store the total count to avoid overflow.

Complexity Analysis

Time Complexity:

• The algorithm iterates through the sorted array of size ’n’, resulting in a linear operation with a time complexity of O(n).
• However, the dominant operations are the binary searches performed by the ‘upper_bound’ and ’lower_bound’ functions within the loop, each with a time complexity of O(log n) due to their binary search nature.
• Therefore, the overall time complexity is the product of these operations, resulting in O(n log n). This classification is justified due to the logarithmic search time being amplified by the linear number of iterations.

Space Complexity:

• The algorithm sorts the input array ’nums’ in-place, which does not require any additional memory proportional to the input size.
• The usage of pointers and variables (e.g., ‘i’, ‘right’, and ’left’) is constant and not dependent on the input size, and thus does not affect the overall space complexity.
• Therefore, the algorithm has a space complexity of O(1), as it only requires a constant amount of memory.

Footnote

This question is rated as Medium difficulty.

Hints

Sort the array in ascending order.

For each number in the array, keep track of the smallest and largest numbers in the array that can form a fair pair with this number.

As you move to larger number, both boundaries move down.

Similar Questions: