Efficient Solution of LeetCode 2563: Count the Number of Fair Pairs in C++ | LeetCode Problems

This problem tests our understanding of efficient array traversal techniques and highlights the power of binary search when working with sorted arrays. By the end of this post, you’ll have a clear, optimized solution in C++ that avoids Time Limit Exceeded (TLE) errors and uses two-pointer and binary search techniques.

Let’s get started by breaking down the problem and exploring a step-by-step approach to a performant solution.

Problem Statement

Given:

• An integer array nums of size n.
• Two integers, lower and upper.

Our goal is to count all pairs (i, j) where:

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

Example Walkthrough

Let's clarify with an example:

Example 1

• Input: nums = [0, 1, 7, 4, 4, 5], lower = 3, upper = 6
• Output: 6
• Explanation: Valid pairs that satisfy the condition are (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 only one valid pair: (2, 3).

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i], lower, upper <= 10^9

With the constraints, a brute-force approach will fail due to excessive runtime. This is where sorting and binary search come into play.

---

Strategy: Optimized Approach with Sorting and Binary Search

To solve this problem efficiently, we’ll use the following approach:

1. Sort the Array: Sorting enables us to efficiently search for valid pairs using binary search, which will significantly reduce the number of operations.
2. Binary Search for Range: For each element nums[i], we’ll determine a valid range of nums[j] values that can form a fair pair with nums[i]. We’ll find the start and end of this range using:
   • lower_bound to get the minimum valid nums[j].
   • upper_bound to get the maximum valid nums[j].
3. Calculate Pair Count: For each i, the difference right - left (from binary search results) gives us the count of valid j values. Summing these differences gives the total number of fair pairs.

Step-by-Step Solution Code

Here’s the complete C++ code for this approach:

#include <vector>

#include <algorithm>

class Solution {

public:

    long long countFairPairs(std::vector<int>& nums, int lower, int upper) {

        // Step 1: Sort the array

        std::sort(nums.begin(), nums.end());

        long long count = 0;

        // Step 2: Loop through each element and find valid j values

        for (int i = 0; i < nums.size(); i++) {

            // Define the target range for nums[j]

            int low = lower - nums[i];

            int up = upper - nums[i];

            // Use binary search to find the bounds

            int left = std::lower_bound(nums.begin() + i + 1, nums.end(), low) - nums.begin();

            int right = std::upper_bound(nums.begin() + i + 1, nums.end(), up) - nums.begin();

            // The number of valid pairs with nums[i] is the difference right - left

            count += right - left;

        }

        return count;

    }

};

Explanation of Key Steps

1. Sorting (O(n log n)):

   • Sorting allows us to leverage binary search, which is much faster than checking each potential pair individually.

2. Binary Search for Valid j Values (O(log n)):

   • For each i, we calculate a low and up threshold based on the values of lower and upper.
   • Using lower_bound and upper_bound on the range starting from i + 1, we get the count of j values where nums[i] + nums[j] lies within [lower, upper].

3. Efficient Pair Count Calculation:

   • right - left tells us exactly how many valid pairs exist with nums[i] as the first element.

Complexity Analysis

• Time Complexity: $O(n\log n$
• Space Complexity: $O(1)$

This solution is optimized for large inputs, avoiding TLE even when n reaches 10^5.

---

Why This Solution Works

The combination of sorting and binary search allows us to take advantage of the sorted order of nums. By transforming the problem into finding ranges of j values, we sidestep the need for nested loops and keep operations efficient. This is a great example of how sorting and binary search can simplify complex pairing problems.

FAQs for LeetCode 2563: Count the Number of Fair Pairs

1. What is a "fair pair" in this problem?
A fair pair is a pair of indices (i, j) where:

• 0 <= i < j < n (indices are ordered).
• The sum nums[i] + nums[j] lies between lower and upper (inclusive).

2. Why does the brute-force approach fail?
A brute-force solution (checking all possible pairs) has O(n²) time complexity, which is too slow for constraints like n = 10^5. Sorting + binary search reduces it to O(n log n).

3. Why is sorting necessary?
Sorting enables binary search, allowing us to find valid j values for each i in O(log n) time instead of O(n).

4. How does lower_bound and upper_bound work here?

• lower_bound(nums.begin(), nums.end(), low) finds the first j where nums[j] >= lower - nums[i].
• upper_bound(nums.begin(), nums.end(), up) finds the first j where nums[j] > upper - nums[i].
  The difference (right - left) gives the count of valid j values for nums[i].

5. What’s the time complexity of the optimized solution?

• O(n log n) for sorting.
• O(n log n) for binary searches (n elements × O(log n) per search).
  Total: O(n log n).

6. Why do we start binary search from i + 1?
To avoid counting duplicates or pairs where j <= i (since i < j is required).

7. Can this problem be solved with a two-pointer technique?
Yes! After sorting, use two pointers (left/right) to find valid ranges for each i. However, binary search is more intuitive for this problem.

8. What if the array contains negative numbers?
The solution still works because sorting handles negatives correctly (e.g., -5 + 10 = 5 is treated the same as 3 + 2).

9. How does the code avoid integer overflow?

• The constraints allow nums[i] up to ±1e9, but lower - nums[i] and upper - nums[i] are computed as integers.
• Using long long for count prevents overflow when summing large counts.

10. Can we use hash maps instead of sorting?
No, because hash maps don’t help in finding ranges of values (binary search requires sorted order).

11. What’s the space complexity?
O(1) extra space (ignoring sorting, which may use O(log n) stack space in quicksort).

12. Why is the output 6 in Example 1?
For nums = [0,1,7,4,4,5], valid pairs are:
(0,3)=4, (0,4)=4, (0,5)=5, (1,3)=5, (1,4)=5, (1,5)=6 → Total 6.

13. How would you handle duplicate values in the array?
The solution already handles duplicates because sorting groups them, and binary search counts all valid js (including duplicates).

14. Is this problem similar to Two Sum?
Partially, but Two Sum finds exact sums, whereas this problem counts sums in a range.

15. What’s the role of std::upper_bound?
It finds the first element greater than upper - nums[i], so right - left counts values ≤ upper.

16. Can we solve this with a sliding window?
Sliding windows work for contiguous subarrays, but this problem needs any pairs, so binary search is better.

17. What if lower > upper?
The answer is 0 (no valid pairs exist since the range is invalid).

18. How would you modify the solution for i <= j?
Change the binary search to start from i instead of i + 1 and adjust bounds to avoid double-counting.

19. Why use long long for the count?
For large n (e.g., 1e5), the count can exceed INT_MAX.

20. Can this approach be used for triplets or quadruples?
Yes! For triplets, sort and fix two indices, then binary search for the third. Time complexity becomes O(n² log n).

LeetCode 2563: Count the Number of Fair Pairs can be solved efficiently using sorting and binary search. By following this method, we achieve optimal performance without sacrificing readability. Remember, whenever you face a pairing problem, consider sorting and using binary search to find ranges—it might be the key to an efficient solution!

With this approach, you’re ready to tackle similar problems on LeetCode and beyond. If you found this helpful, feel free to share or bookmark it for your coding journey!