Count the Number of Fair Pairs solution and explanation
Google
TCS
9 more videos on this problem
Count the Number of Fair Pairs - Leetcode 2563 - PythonNeetCodeIO · 18:52 · 18K views
Count the Number of Fair Pairs | Detailed Explanation | Leetcode 2563 | codestorywithMIKcodestorywithMIK · 34:31 · 17K views
Count the Number of Fair Pairs | Leetcode 2563Techdose · 14:29 · 8K views
2563. Count the Number of Fair Pairs | Weekly Contest 332 | LeetCode 2563Bro Coders · 8:17 · 4K views
2563. Count the Number of Fair Pairs || Binary Search || Asked by Salesforce & GoogleAryan Mittal · 16:21 · 3K views
LeetCode 2563 Count the Number of Fair Pairs | Two Pointers Trick You MUST Know! 🔥Code Harmony · 19:24 · 1K views
2563. Count the Number of Fair Pairs (Leetcode Medium)Programming Live with Larry · 8:44 · 1K views
Leetcode 2563 Count the Number of Fair Pairs (Java) - Leetcode Weekly Contest 332TheAnalyticGuy · 9:30 · 737 views
2563. Count the Number of Fair Pairs | Leetcode Daily - PythonLeetcode Daily · 10:04 · 469 views
Count the Number of Fair Pairs - Leetcode 2563 - PythonTim Huang · 4:12 · 198 views
The problem
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, andlower <= 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 <= 105nums.length == n-109 <= nums[i] <= 109-109 <= lower <= upper <= 109
Approach overview
Problem Overview: Given an integer array nums and two integers lower and upper, count the number of pairs (i, j) such that i < j and the sum nums[i] + nums[j] lies in the inclusive range [lower, upper]. The goal is to efficiently count valid pairs without checking every combination.
Approach 1: Brute Force (O(n²) time, O(1) space)
The simplest solution checks every pair of indices. Use two nested loops: the outer loop picks i, and the inner loop checks every j > i. For each pair, compute the sum and verify whether it falls between lower and upper. Increment the counter when the condition holds. This approach directly mirrors the problem definition and is easy to implement, but it becomes slow for large arrays because the number of comparisons grows quadratically.
Approach 2: Two-Pointer Technique after Sorting (O(n log n) time, O(1) extra space)
A more efficient strategy sorts the array first, which enables the use of the two pointers pattern. After sorting using a standard sorting algorithm, the problem reduces to counting how many pairs have sums within a range. Instead of checking every pair, compute the number of pairs with sum <= upper and subtract the number of pairs with sum < lower. Each of these counts can be found with a two-pointer sweep: place one pointer at the start and the other at the end of the array. If the sum is within the bound, every element between the pointers forms a valid pair with the left pointer, so add that count and move the left pointer forward. Otherwise move the right pointer backward. This linear scan after sorting avoids redundant checks and drastically reduces the runtime.
Some implementations replace the right pointer adjustment with a binary search to locate the valid range for each index, but the two-pointer sweep is typically faster in practice because it runs in a single pass.
Recommended for interviews: Start by describing the brute force solution to demonstrate understanding of the pair constraint. Then transition to the sorted two-pointer strategy. Interviewers usually expect the optimized approach because it reduces the complexity from O(n²) to O(n log n) due to sorting, with only a linear scan afterward.
Approach 1: Approach 1: Two-Pointer Technique after Sorting
This approach leverages sorting and a two-pointer technique to efficiently find the number of fair pairs. By sorting the array, we bring potential fair pairs closer, simplifying the conditions checking. Two pointers are then used to find suitable pairs within the bounds.
First, sort the array nums. As we iterate through each element as one half of the pair, use two pointers to find elements that complete the pair within the given range of sums.
from typing import List
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums.sort()
count = 0
for i in range(len(nums)):
low_index = self.lowerBound(nums, i + 1, len(nums), lower - nums[i])
high_index = self.upperBound(nums, i + 1, len(nums), upper - nums[i])
count += high_index - low_index
return count
def lowerBound(self, nums: List[int], start: int, end: int, target: int) -> int:
low, high = start, end
while low < high:
mid = low + (high - low) // 2
if nums[mid] < target:
low = mid + 1
else:
high = mid
return low
def upperBound(self, nums: List[int], start: int, end: int, target: int) -> int:
low, high = start, end
while low < high:
mid = low + (high - low) // 2
if nums[mid] <= target:
low = mid + 1
else:
high = mid
return low
# Test the implementation
if __name__ == "__main__":
sol = Solution()
nums = [0, 1, 7, 4, 4, 5]
result = sol.countFairPairs(nums, 3, 6)
print(f"Number of fair pairs: {result}")import java.util.*;
public class Solution {
public int countFairPairs(int[] nums, int lower, int upper) {
Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length; i++) {
int lowBound = lowerBound(nums, i + 1, nums.length, lower - nums[i]);
int upBound = upperBound(nums, i + 1, nums.length, upper - nums[i]);
count += upBound - lowBound;
}
return count;
}
private int lowerBound(int[] nums, int start, int end, int target) {
int low = start, high = end;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
private int upperBound(int[] nums, int start, int end, int target) {
int low = start, high = end;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] <= target) low = mid + 1;
else high = mid;
}
return low;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {0, 1, 7, 4, 4, 5};
int result = sol.countFairPairs(nums, 3, 6);
System.out.println("Number of fair pairs: " + result);
}
}#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
int countFairPairs(std::vector<int>& nums, int lower, int upper) {
std::sort(nums.begin(), nums.end());
int count = 0;
for (int i = 0; i < nums.size(); ++i) {
auto low = std::lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]);
auto high = std::upper_bound(nums.begin() + i + 1, nums.end(), upper - nums[i]);
count += high - low;
}
return count;
}
};
int main() {
Solution sol;
std::vector<int> nums = {0, 1, 7, 4, 4, 5};
int result = sol.countFairPairs(nums, 3, 6);
std::cout << "Number of fair pairs: " << result << std::endl;
return 0;
}function countFairPairs(nums, lower, upper) {
nums.sort((a, b) => a - b);
let count = 0;
for (let i = 0; i < nums.length; i++) {
let lowIndex = lowerBound(nums, i + 1, nums.length, lower - nums[i]);
let highIndex = upperBound(nums, i + 1, nums.length, upper - nums[i]);
count += highIndex - lowIndex;
}
return count;
}
function lowerBound(nums, start, end, target) {
let low = start, high = end;
while (low < high) {
let mid = low + Math.floor((high - low) / 2);
if (nums[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
function upperBound(nums, start, end, target) {
let low = start, high = end;
while (low < high) {
let mid = low + Math.floor((high - low) / 2);
if (nums[mid] <= target) low = mid + 1;
else high = mid;
}
return low;
}
const nums = [0, 1, 7, 4, 4, 5];
const result = countFairPairs(nums, 3, 6);
console.log(`Number of fair pairs: ${result}`);#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int countFairPairs(int *nums, int numsSize, int lower, int upper) {
qsort(nums, numsSize, sizeof(int), compare);
int count = 0;
for (int i = 0; i < numsSize; ++i) {
int left = i + 1, right = numsSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[i] + nums[mid] < lower) {
left = mid + 1;
} else {
right = mid - 1;
}
}
int lowIndex = left;
left = i + 1; right = numsSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[i] + nums[mid] <= upper) {
left = mid + 1;
} else {
right = mid - 1;
}
}
int highIndex = right;
count += (highIndex - lowIndex + 1);
}
return count;
}
int main() {
int nums[] = {0,1,7,4,4,5};
int lower = 3, upper = 6;
int result = countFairPairs(nums, 6, lower, upper);
printf("Number of fair pairs: %d\n", result);
return 0;
}using System;
public class Solution {
public int CountFairPairs(int[] nums, int lower, int upper) {
Array.Sort(nums);
int count = 0;
for (int i = 0; i < nums.Length; i++) {
int lowBound = LowerBound(nums, i + 1, nums.Length, lower - nums[i]);
int upBound = UpperBound(nums, i + 1, nums.Length, upper - nums[i]);
count += upBound - lowBound;
}
return count;
}
private int LowerBound(int[] nums, int start, int end, int target) {
int low = start, high = end;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
private int UpperBound(int[] nums, int start, int end, int target) {
int low = start, high = end;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] <= target) low = mid + 1;
else high = mid;
}
return low;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {0, 1, 7, 4, 4, 5};
int result = sol.CountFairPairs(nums, 3, 6);
Console.WriteLine("Number of fair pairs: " + result);
}
}Python's solution involves sorting and utilizing internal methods lowerBound and upperBound to localize and calculate fair pairs, iterating through the array.
Time Complexity: O(n log n). The sorting and binary search operations define the complexity.
Space Complexity: O(1). The space utilized is minimal as computation happens in-place.
Approach 2: Approach 2: Brute Force
A simpler, brute-force approach involves examining every possible pair (i, j) to determine if it fits the 'fair pair' criteria. While this method is easier to understand and implement, it becomes inefficient as the input size increases.
from typing import List
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if lower <= nums[i] + nums[j] <= upper:
count += 1
return count
if __name__ == "__main__":
sol = Solution()
nums = [0, 1, 7, 4, 4, 5]
result = sol.countFairPairs(nums, 3, 6)
print(f"Number of fair pairs: {result}")public class Solution {
public int countFairPairs(int[] nums, int lower, int upper) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int sum = nums[i] + nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {0, 1, 7, 4, 4, 5};
int result = sol.countFairPairs(nums, 3, 6);
System.out.println("Number of fair pairs: " + result);
}
}#include <iostream>
#include <vector>
class Solution {
public:
int countFairPairs(std::vector<int>& nums, int lower, int upper) {
int count = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
int sum = nums[i] + nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
};
int main() {
Solution sol;
std::vector<int> nums = {0, 1, 7, 4, 4, 5};
int result = sol.countFairPairs(nums, 3, 6);
std::cout << "Number of fair pairs: " << result << std::endl;
return 0;
}function countFairPairs(nums, lower, upper) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
const sum = nums[i] + nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
const nums = [0, 1, 7, 4, 4, 5];
const result = countFairPairs(nums, 3, 6);
console.log(`Number of fair pairs: ${result}`);#include <stdio.h>
int countFairPairs(int *nums, int numsSize, int lower, int upper) {
int count = 0;
for (int i = 0; i < numsSize; ++i) {
for (int j = i + 1; j < numsSize; ++j) {
int sum = nums[i] + nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {0, 1, 7, 4, 4, 5};
int lower = 3, upper = 6;
int result = countFairPairs(nums, 6, lower, upper);
printf("Number of fair pairs: %d\n", result);
return 0;
}using System;
public class Solution {
public int CountFairPairs(int[] nums, int lower, int upper) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
int sum = nums[i] + nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {0, 1, 7, 4, 4, 5};
int result = sol.CountFairPairs(nums, 3, 6);
Console.WriteLine("Number of fair pairs: " + result);
}
}Python's brute-force approach navigates all permissible indices, leveraging nested for loops to identify pair sums constrained by bounds.
Time Complexity: O(n^2), examining each pair sequentially.
Space Complexity: O(1), keeping computations in-place.
Approach 3: Sorting + Binary Search
First, we sort the array nums in ascending order. Then, for each nums[i], we use binary search to find the lower bound j of nums[j], i.e., the first index that satisfies nums[j] >= lower - nums[i]. Then, we use binary search again to find the lower bound k of nums[k], i.e., the first index that satisfies nums[k] >= upper - nums[i] + 1. Therefore, [j, k) is the index range for nums[j] that satisfies lower <= nums[i] + nums[j] <= upper. The count of these indices corresponding to nums[j] is k - j, and we can add this to the answer. Note that j > i.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array nums.
function countFairPairs(nums: number[], lower: number, upper: number): number {
const search = (x: number, l: number): number => {
let r = nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
nums.sort((a, b) => a - b);
let ans = 0;
for (let i = 0; i < nums.length; ++i) {
const j = search(lower - nums[i], i + 1);
const k = search(upper - nums[i] + 1, i + 1);
ans += k - j;
}
return ans;
}func countFairPairs(nums []int, lower int, upper int) (ans int64) {
sort.Ints(nums)
for i, x := range nums {
j := sort.Search(len(nums), func(h int) bool { return h > i && nums[h] >= lower-x })
k := sort.Search(len(nums), func(h int) bool { return h > i && nums[h] >= upper-x+1 })
ans += int64(k - j)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Technique after Sorting | Time Complexity: O(n log n). The sorting and binary search operations define the complexity. Space Complexity: O(1). The space utilized is minimal as computation happens in-place. |
| Approach 2: Brute Force | Time Complexity: O(n^2), examining each pair sequentially. Space Complexity: O(1), keeping computations in-place. |
| Sorting + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Small arrays or when demonstrating baseline logic in interviews |
| Sort + Two Pointers Range Counting | O(n log n) | O(1) extra | Preferred for large inputs; efficient pair counting after sorting |
Frequently asked questions
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.