DDSA Solutions

2563. Count the Number of Fair Pairs

MediumView on LeetCode
ArrayTwo PointersBinary SearchSorting
Time: O(n log n)
Space: O(1)

Problem Overview

Count pairs with sum in [lower, upper].

Intuition

Count pairs with sum in [lower, upper]. Sort, two pointers for counting pairs in range.

Algorithm

  1. 1Sort. For each i: count j > i where lower-nums[i] <= nums[j] <= upper-nums[i]. Binary search for bounds.

Common Pitfalls

  • •Binary search for upper_bound(upper-nums[i]) - lower_bound(lower-nums[i]) for each i.
2563.cs
C#
// Approach: Sort; for each i binary search for valid j range where sum falls in [lower, upper].
// Time: O(n log n) Space: O(1)
public class Solution
{
    public long CountFairPairs(int[] nums, int lower, int upper)
    {
        Array.Sort(nums);
        return CountLess(nums, upper) - CountLess(nums, lower - 1);
    }

    private long CountLess(int[] nums, int sum)
    {
        long res = 0;
        for (int i = 0, j = nums.Length - 1; i < j; ++i)
        {
            while (i < j && nums[i] + nums[j] > sum)
                --j;
            res += j - i;
        }
        return res;
    }
}
Was this solution helpful?

Related Problems