LeetCode Problem 2426

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Solution

LeetCode 2426 - Number of Pairs Satisfying Inequality

Problem Understanding

We are given two integer arrays, nums1 and nums2, of the same length n, along with an integer diff.

We must count how many index pairs (i, j) satisfy both:

• i < j
• nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff

The goal is to return the total number of valid pairs.

At first glance, the inequality involves values from both arrays and two different indices, making it difficult to count directly. Since n can be as large as 100,000, checking every possible pair is not feasible.

The constraints tell us several important things:

• There can be up to 10^5 elements.
• Values may be negative.
• The answer can be much larger than 2^31 - 1, so we must use a 64-bit integer for the result.
• An O(n²) solution would require roughly 10^10 comparisons in the worst case, which is far too slow.

A useful observation is that the inequality can be transformed into a form involving only one value per index. Once that transformation is made, the problem becomes a classic counting problem that can be solved efficiently using merge sort.

Important edge cases include:

• All pairs being valid.
• No valid pairs.
• Negative values in both arrays.
• Negative diff.
• Large inputs where the answer exceeds 32-bit integer range.
• Duplicate transformed values, which require careful handling of <= rather than <.

Approaches

Brute Force

The most direct approach is to examine every pair (i, j) with i < j.

For each pair, evaluate:

nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff

If the condition holds, increment the answer.

This method is obviously correct because it checks every possible pair exactly as defined by the problem statement.

However, there are:

n(n - 1) / 2

possible pairs.

For n = 100,000, this is approximately five billion pairs, making the approach completely impractical.

Key Insight

Start with the original inequality:

nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff

Move terms involving the same index together:

nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff

Define:

arr[k] = nums1[k] - nums2[k]

The condition becomes:

arr[i] <= arr[j] + diff

Rearranging:

arr[i] - diff <= arr[j]

Now the problem becomes:

Count pairs (i, j) such that:

i < j
arr[i] <= arr[j] + diff

This is similar to counting inversions, except the comparison condition is different.

Whenever we see a pair-counting problem with index ordering constraints and a comparison between values, a merge sort based counting technique is often applicable.

During merge sort, both halves are already sorted. We can count valid cross-half pairs using two pointers before merging the halves.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair directly
Optimal Merge Sort Counting	O(n log n)	O(n)	Counts valid pairs during merge sort

Algorithm Walkthrough

Step 1: Transform the arrays

Create a new array:

arr[i] = nums1[i] - nums2[i]

The original inequality becomes:

arr[i] <= arr[j] + diff

This reduces the problem to working with a single array.

Step 2: Use divide and conquer

Apply merge sort to arr.

Just like inversion counting, every valid pair belongs to one of three categories:

1. Both indices in the left half.
2. Both indices in the right half.
3. One index in each half.

Recursive calls count the first two categories automatically.

We only need to count cross-half pairs during the merge step.

Step 3: Count cross-half pairs

Suppose:

left half  = arr[left:mid+1]
right half = arr[mid+1:right+1]

Both halves are already sorted.

For every value in the left half, we want to know how many values in the right half satisfy:

left_value <= right_value + diff

Equivalently:

right_value >= left_value - diff

Because the right half is sorted, a pointer can move through it monotonically.

For each left element:

• Advance the pointer while:

right_value < left_value - diff

• After the pointer stops, every remaining element in the right half forms a valid pair.

The number of valid partners is:

right_end - pointer + 1

Step 4: Merge the halves

After counting, perform the normal merge sort merge operation.

This preserves sorted order for higher recursive levels.

Step 5: Return the accumulated count

All valid pairs are counted exactly once during the recursion.

The final count is the answer.

Why it works

At every merge step, the left and right halves are already sorted. For a fixed left value, once a right value becomes large enough to satisfy:

right_value >= left_value - diff

all later right values will also satisfy the condition because the right half is sorted. Therefore a single moving pointer can count all valid cross-half pairs efficiently.

Every pair (i, j) belongs to exactly one merge step where the indices first become separated into different halves. That merge step counts the pair exactly once. Thus every valid pair is counted once and only once.

Python Solution

from typing import List

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:
        arr = [a - b for a, b in zip(nums1, nums2)]
        temp = [0] * len(arr)

        def merge_sort(left: int, right: int) -> int:
            if left >= right:
                return 0

            mid = (left + right) // 2

            count = merge_sort(left, mid)
            count += merge_sort(mid + 1, right)

            j = mid + 1

            for i in range(left, mid + 1):
                while j <= right and arr[j] < arr[i] - diff:
                    j += 1

                count += right - j + 1

            i = left
            j = mid + 1
            k = left

            while i <= mid and j <= right:
                if arr[i] <= arr[j]:
                    temp[k] = arr[i]
                    i += 1
                else:
                    temp[k] = arr[j]
                    j += 1
                k += 1

            while i <= mid:
                temp[k] = arr[i]
                i += 1
                k += 1

            while j <= right:
                temp[k] = arr[j]
                j += 1
                k += 1

            for idx in range(left, right + 1):
                arr[idx] = temp[idx]

            return count

        return merge_sort(0, len(arr) - 1)

The implementation begins by constructing the transformed array:

arr[i] = nums1[i] - nums2[i]

This converts the original inequality into a comparison involving only one array.

The recursive merge_sort function returns the number of valid pairs inside the current range while also sorting that range.

After recursively solving the left and right halves, the function counts cross-half pairs. Since both halves are sorted, a single pointer j scans the right half only once. This keeps the counting step linear.

After counting, a standard merge operation combines the two sorted halves. The merged result is copied back into the original array so that higher recursion levels receive sorted segments.

The total count accumulated across all recursive calls is returned as the final answer.

Go Solution

func numberOfPairs(nums1 []int, nums2 []int, diff int) int64 {
	n := len(nums1)

	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = nums1[i] - nums2[i]
	}

	temp := make([]int, n)

	var mergeSort func(int, int) int64

	mergeSort = func(left, right int) int64 {
		if left >= right {
			return 0
		}

		mid := (left + right) / 2

		count := mergeSort(left, mid)
		count += mergeSort(mid+1, right)

		j := mid + 1

		for i := left; i <= mid; i++ {
			for j <= right && arr[j] < arr[i]-diff {
				j++
			}

			count += int64(right - j + 1)
		}

		i := left
		j = mid + 1
		k := left

		for i <= mid && j <= right {
			if arr[i] <= arr[j] {
				temp[k] = arr[i]
				i++
			} else {
				temp[k] = arr[j]
				j++
			}
			k++
		}

		for i <= mid {
			temp[k] = arr[i]
			i++
			k++
		}

		for j <= right {
			temp[k] = arr[j]
			j++
			k++
		}

		for idx := left; idx <= right; idx++ {
			arr[idx] = temp[idx]
		}

		return count
	}

	return mergeSort(0, n-1)
}

The Go implementation follows exactly the same divide-and-conquer strategy.

One important difference is that the return type is explicitly int64, since the number of valid pairs can exceed the range of a 32-bit integer. All pair counts are therefore accumulated using int64.

Slices are used for both the working array and temporary merge buffer, providing the same functionality as Python lists.

Worked Examples

Example 1

nums1 = [3,2,5]
nums2 = [2,2,1]
diff = 1

Transform:

arr = [1,0,4]

Condition:

arr[i] <= arr[j] + 1

First merge

Left:

[1]

Right:

[0]

i value	Pointer Position	Valid Count
1	right value 0 satisfies 0 >= 0	1

Count = 1

Merged:

[0,1]

Final merge

Left:

[0,1]

Right:

[4]

Left Value	Required Right Value
0	>= -1
1	>= 0

Both conditions are satisfied by 4.

Additional count:

2

Total:

1 + 2 = 3

Answer:

3

Example 2

nums1 = [3,-1]
nums2 = [-2,2]
diff = -1

Transform:

arr = [5,-3]

Condition:

arr[i] <= arr[j] - 1

Check cross pair:

5 <= -4

False.

Count:

0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Merge sort performs log n levels, each level processes n elements
Space	O(n)	Temporary merge array requires linear extra memory

The counting step inside each merge operation is linear because the right-side pointer only moves forward. Therefore each merge level performs O(n) work. Since merge sort has O(log n) levels, the total running time is O(n log n). The temporary buffer used during merging requires O(n) additional space.

Test Cases

sol = Solution()

assert sol.numberOfPairs([3, 2, 5], [2, 2, 1], 1) == 3  # example 1

assert sol.numberOfPairs([3, -1], [-2, 2], -1) == 0  # example 2

assert sol.numberOfPairs([1, 1], [1, 1], 0) == 1  # single valid pair

assert sol.numberOfPairs([1, 2], [1, 1], -10) == 0  # no valid pair

assert sol.numberOfPairs([5, 5, 5], [0, 0, 0], 0) == 3  # all equal transformed values

assert sol.numberOfPairs([0, 0, 0, 0], [0, 0, 0, 0], 0) == 6  # every pair valid

assert sol.numberOfPairs([-5, -4, -3], [0, 0, 0], 0) == 3  # increasing transformed values

assert sol.numberOfPairs([10, 9, 8], [0, 0, 0], 0) == 0  # decreasing transformed values

assert sol.numberOfPairs([10000, -10000], [-10000, 10000], 0) == 1  # extreme values

assert sol.numberOfPairs([1, 2, 3, 4], [4, 3, 2, 1], 2) == 6  # larger positive diff

Test Summary

Test	Why
Example 1	Verifies official example
Example 2	Verifies official example with zero answer
Two identical values	Smallest non-trivial valid case
Large negative diff	Ensures restrictive conditions work
Equal transformed values	Tests handling of duplicates
All zeros	Every pair should be counted
Increasing transformed values	Many valid pairs
Decreasing transformed values	No valid pairs
Extreme values	Verifies large magnitude arithmetic
Larger positive diff	Tests permissive inequality

Edge Cases

Duplicate transformed values

When multiple indices produce the same value of nums1[i] - nums2[i], the inequality may still be satisfied. A common mistake is to use a strict comparison during counting. The implementation carefully counts values satisfying >= arr[i] - diff, ensuring duplicates are handled correctly.

Negative diff

A negative diff makes the condition harder to satisfy. Some solutions incorrectly assume the threshold is always increasing. The transformed inequality remains valid regardless of the sign of diff, and the merge sort counting logic works without modification.

Very Large Answers

For n = 100000, the number of pairs can be:

100000 * 99999 / 2

which is approximately five billion. This exceeds the range of a signed 32-bit integer. The Go implementation therefore uses int64, and Python naturally supports arbitrarily large integers.

Arrays Containing Negative Numbers

Since both input arrays may contain negative values, transformed values can also be negative. The merge sort approach depends only on relative ordering, not on value ranges, so negative numbers are handled naturally without any special cases.

All Pairs Valid

If every pair satisfies the inequality, the answer reaches the maximum possible number of pairs. The algorithm still performs only O(n log n) work because it counts groups of pairs through sorted ranges rather than examining pairs individually.