Is Count the Number of Fair Pairs easy or hard?

The problem is rated Medium on LeetCode. The difficulty comes from recognizing that naive pair checking is too slow and that sorting plus a two-pointer counting technique reduces the complexity to O(n log n).

Count the Number of Fair Pairs Python/Java solution

Most implementations follow the same pattern across languages: sort the array, then run a helper function that counts pairs with sums below a threshold using two pointers. This logic translates directly to Python, Java, C++, C#, and JavaScript with minimal changes.

How to solve Count the Number of Fair Pairs in O(n)?

After sorting the array, counting pairs with a two-pointer sweep takes O(n) time. However, sorting itself costs O(n log n), so the full algorithm is O(n log n). The linear step works by expanding and shrinking pointers to count all pairs whose sums stay within a bound.

What is the best approach for Count the Number of Fair Pairs?

The most efficient approach sorts the array and uses a two-pointer scan to count pairs with sums within the allowed range. After sorting, compute pairs with sum <= upper and subtract pairs with sum < lower. The algorithm runs in O(n log n) time due to sorting and O(1) extra space.

Is Count the Number of Fair Pairs asked at Google/Amazon/Meta?

Pair counting and range-sum problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants using sorting, two pointers, or binary search are common because they test optimization from O(n^2) to O(n log n).

What data structure is used in Count the Number of Fair Pairs?

The solution primarily uses arrays combined with sorting and the two-pointer technique. Some alternative implementations use binary search on the sorted array to locate valid partner indices for each element.

What is the time complexity of Count the Number of Fair Pairs?

The brute force solution runs in O(n^2) time because it checks every pair of indices. The optimized solution sorts the array and performs a linear two-pointer scan, resulting in O(n log n) time and O(1) extra space.

Description Hints 3 Solution Video 18:52

2563. Count the Number of Fair Pairs

Q: Is Count the Number of Fair Pairs asked at Google/Amazon/Meta?

Pair counting and range-sum problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants using sorting, two pointers, or binary search are common because they test optimization from O(n^2) to O(n log n).

Q: What data structure is used in Count the Number of Fair Pairs?

The solution primarily uses arrays combined with sorting and the two-pointer technique. Some alternative implementations use binary search on the sorted array to locate valid partner indices for each element.

Q: What is the time complexity of Count the Number of Fair Pairs?

The brute force solution runs in O(n^2) time because it checks every pair of indices. The optimized solution sorts the array and performs a linear two-pointer scan, resulting in O(n log n) time and O(1) extra space.

Medium52.7% acceptance9 companies

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⁹

Asked at 9 companies

McDonald's Qualcomm Salesforce

Google Amazon Bloomberg

TCS Microsoft Meta

Topics

Hints open one at a time

Hint 1

Sort the array in ascending order.

Hint 2

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.

Hint 3

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

18:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution