I Feel Ducky

Leetcode #2563 - Count the Number of Fair Pairs

📝 Description

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 considered fair if:

📘 Examples

Example 1:

Input:
nums = [0,1,7,4,4,5], lower = 3, upper = 6
Output: 6

Explanation:
There are 6 fair pairs:

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

🎯 Would you like to try it yourself? Click here to solve it on Leetcode!

🤔 So... What's Going On Here?

Alright, so the problem is asking us to count how many "fair pairs" exist in an array. Now, a fair pair is just a fancy way of saying:

Pick two different elements (with the first one coming before the second), and check if their sum lands between two numbers — lower and upper.

Sounds simple enough, right?

Let’s break it down with an example:

Say we have this array:
nums = [0, 1, 7, 4, 4, 5]
and we're told:
lower = 3, upper = 6

Now our job is to go through all the possible pairs where the first number comes before the second (like (0, 1), (0, 2), etc.), and for each pair, check if their sum is at least 3 but no more than 6.

Every time we find a pair like that, we count it. By the end, we want to know how many such pairs exist.

The trick here is: this sounds simple, but as the array gets bigger (and it can go up to 100,000 elements!), going through every pair manually becomes really slow. But hey — we’ll worry about that later.

🐢 Naive Solution — Brute Forcing It

Before we get all fancy with optimized code, let’s start with the good ol’ brute-force approach. It’s the most straightforward way to solve the problem — even if it’s not the fastest.

Here’s what we’re doing in this version:

  1. Loop through every possible pair (i, j) in the array.
  2. Make sure i < j — so we don’t count the same pair twice or pair an element with itself.
  3. Add the two numbers together.
  4. If the sum falls between lower and upper, boom! It’s a fair pair. We increment our counter.

And here's the code in Go:

func countFairPairs(nums []int, lower int, upper int) int64 {
    var fairPairs int64
    for i := 0; i < len(nums)-1; i++ {
        for j := i + 1; j <= len(nums)-1; j++ {
            if (nums[i] + nums[j]) >= lower && (nums[i] + nums[j]) <= upper {
                fairPairs++
            }
        }
    }
    return fairPairs
}

🧠 What’s going on here?

We’re just checking every single pair to see if it’s fair. That’s why this is called a "naive" solution — we’re not trying to be clever (yet). This works fine for small arrays, but once the input size grows, it’ll start to feel real slow. Why? Because the number of pairs grows really fast. For n elements, we’re doing about n * (n-1)/2 checks. That’s a lot!

But don’t worry — we’ll make it faster soon. Up next: we figure out how to make this smarter and more efficient 🚀

📊 Complexity Talk — How Bad Is It?

Now that we’ve got our naive solution working, let’s chat about how efficient (or... not) it is.

⏱️ Time Complexity

We’ve got two nested loops here:

for i := 0; i < len(nums)-1; i++ {
    for j := i + 1; j <= len(nums)-1; j++ {
        // ...
    }
}

This means for every element in the array, we’re checking it against every other element after it. So if we have n elements, we’re doing something like:

n * (n - 1) / 2

That’s O(n²) — which is totally fine if n is small, but remember, n can go up to 100,000 😬

If you try this on a big input... yeah, your program might take a nap 💤 or timeout altogether.

💾 Space Complexity

The good news? This solution is super light on memory.

We’re just using:

So that’s O(1) space — constant space! 🎉

🚨 Summary

Type Complexity
Time Complexity O(n²)
Space Complexity O(1)

🧭 Thinking Ahead — How Can We Do Better?

Alright, so the brute force method works, but it’s like trying to find matching socks in a huge pile one by one — it gets sloooow. We want something faster.

Let’s talk about how we can be a bit smarter about this.

👟 Enter: Two Pointers

Here’s a trick that works really well for this kind of problem: the Two Pointers Pattern.

It sounds fancy, but it’s actually super simple.

🧪 Here’s an example:

Let’s say you need pairs of numbers that add up to something between 20 and 25.

And let’s say your array (after sorting) looks like this:

[1, 3, 7, 11, 14, 20, 25, 46]

Now, you place two fingers on the array:

So we’re looking at 1 + 46 = 47.
Way too big! ❌

But here’s the catch: 1 is the smallest number. So no matter which number we pair it with (as long as it's 46 or something even bigger), the sum will stay too high.

That means:
46 is not helping. Let’s ignore it and move the right pointer (j) left.

Now we try 1 + 25 = 26.
Still too big. Move j again.

Try 1 + 20 = 21.
Ah! That works ✅

And now we’ve found a valid pair!

🧠 Why This Works

Because the array is sorted, we can make smart moves:

This lets us skip tons of unnecessary checks, and that’s why it’s so much faster.

🧮 But We Need to Count All the Pairs

Now here’s the catch: we don’t just want one pair — we want to count every valid pair.

And that's where things get a little tricky. Because checking all the possible pairs with two pointers the normal way... it's still too slow.

So instead, we do something smarter:

🎯 A Clever Variation: Count Everything ≤ upper, Then Subtract < lower

Instead of directly counting the number of pairs in the range [lower, upper], we flip the problem:

✅ First, count how many pairs have a sum less than or equal to upper
🚫 Then, subtract how many pairs have a sum less than lower

And just like that, we’re left with the number of pairs in exactly the range we want.

This trick is called the Prefix Subtraction Pattern.

It lets us simplify the problem to a single helper function:

countPairsAtMost(nums, limit)

And then we use:

countPairsAtMost(nums, upper) - countPairsAtMost(nums, lower - 1)

🤓 Why This Works So Well This variation combines a bunch of great ideas:

✅ It avoids checking every pair

✅ It uses a sorted array to skip unnecessary work

✅ It counts multiple valid pairs at once (j - i), instead of one at a time

✅ It reuses logic for two different limits using subtraction

It’s not the classic two-pointers approach — we’re not moving both pointers together through the array — but it’s built on that same idea: use the sorted structure to move fast.

So you can think of it as:

A variation of the Two Pointers Pattern, powered by Prefix Subtraction.

This is the actual code we end up using:

func countPairsAtMost(nums []int, limit int) int {
	count := 0
	for i, j := 0, len(nums)-1; i < j; i++ {
		for ; i < j && nums[i]+nums[j] > limit; j-- {
		}
		count += j - i
	}
	return count
}

func countFairPairs(nums []int, lower int, upper int) int64 {
	sort.Ints(nums)
	return int64(countPairsAtMost(nums, upper) - countPairsAtMost(nums, lower-1))
}

✅ Wrapping It Up

By combining sorting, a clever variation of the two pointers technique, and the prefix subtraction pattern, we were able to bring the time complexity down from:

Why O(n log n)?

So overall, this is a massive improvement — especially when dealing with large arrays.

🚀 The End Result?

And the best part?

This optimized solution finishes in just 20ms and uses only 10.1MB of memory.

That’s a clean, fast, and elegant win! 🎉

Thanks for sticking through the journey — from brute force to efficient solution. You not only solved the problem, but picked up some super useful patterns along the way 🙌

#Algorithms #Array Problems #Coding Interview #Go #Golang #Leetcode #Optimization #Prefix Sum #Problem Solving #Range Queries #Sorting #Time Complexity #Two Pointers