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

 his 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.

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!