Skip to main content
Talentd

Count the Number of Fair Pairs - Solution & Explanation

MediumArrayTwo PointersBinary SearchSorting19 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

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

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.

This C implementation uses binary search after sorting the array. Two loops identify the lower and upper bounds of valid pair elements, and count their occurrences.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), where the sorting step dominates the complexity. Each binary search operation runs in O(log n).

Space Complexity: O(1), as we sort in-place.

Try this approach in the editor ā†’

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.

The brute-force C implementation iterates over each element and checks every subsequent element for compliant pair conditions. This straightforward iteration checks all n^2 pairs.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), as it examines every possible pair.

Space Complexity: O(1), since no additional space is utilized.

Try this approach in the editor ā†’

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Approach 1: Two-Pointer Technique after Sorting

Time Complexity: O(n log n), where the sorting step dominates the complexity. Each binary search operation runs in O(log n).

Space Complexity: O(1), as we sort in-place.

Approach 2: Brute Force

Time Complexity: O(n^2), as it examines every possible pair.

Space Complexity: O(1), since no additional space is utilized.

Sorting + Binary Searchā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(nĀ²)O(1)Small arrays or when demonstrating baseline logic in interviews
Sort + Two Pointers Range CountingO(n log n)O(1) extraPreferred for large inputs; efficient pair counting after sorting

Video Solution

Count the Number of Fair Pairs - Leetcode 2563 - Python ā€¢ NeetCodeIO ā€¢ 18,113 views views

Watch 9 more video solutions ā†’

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.

Ready to solve this problem?

Practice Count the Number of Fair Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Pairs With Absolute Difference K

Next

Count of Range Sum