Count The Number Of Fair Pairs
01 · Problem
You are given an integer array nums of length n and two integers lower and upper.
A pair of indices (i, j) is called fair when 0 <= i < j < n and the sum nums[i] + nums[j] falls inside the inclusive range [lower, upper].
Return the total number of fair pairs. Pairs are counted by index, so duplicate values at different positions form distinct pairs. If n < 2, the answer is 0.
02 · Examples
nums = [2,5,1,4], lower = 5, upper = 7
4
The pair sums are 2+5=7, 2+1=3, 2+4=6, 5+1=6, 5+4=9 and 1+4=5. Four of them (7, 6, 6, 5) lie in [5, 7].
nums = [1,7,9,2,5], lower = 11, upper = 11
1
Only 9 + 2 = 11 hits the target exactly.
nums = [3,3,3], lower = 6, upper = 6
3
Every one of the three index pairs (0,1), (0,2), (1,2) sums to 6. Pairs are counted by index, so equal values still count separately.
03 · Constraints
- 011 <= nums.length <= 105
- 02-109 <= nums[i] <= 109
- 03-109 <= lower <= upper <= 109
- 04The answer fits in a 64-bit signed integer
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.