Number of Pairs Satisfying Inequality

Number of Pairs Satisfying Inequality

What is this problem about?

The Number of Pairs Satisfying Inequality problem asks you to count pairs (i, j) where i < j and nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff. By rearranging: (nums1[i] - nums2[i]) - (nums1[j] - nums2[j]) <= diff. Defining arr[i] = nums1[i] - nums2[i], count pairs (i,j) where i < j and arr[i] - arr[j] <= diff. This hard coding problem reduces to counting inversions with a threshold.

Why is this asked in interviews?

Meta, Amazon, and Google ask this hard problem because the rearrangement reveals a modified inversion-counting problem. The efficient solution uses merge sort, Binary Indexed Tree (BIT), or an ordered set. The array, divide and conquer, binary search, ordered set, merge sort, binary indexed tree, and segment tree interview pattern is comprehensively tested.

Algorithmic pattern used

Modified merge sort. During merge sort, for each element in the right half, count how many elements in the left half satisfy left - right <= diff, i.e., left <= right + diff. Since the left half is sorted, use binary search to count valid pairs. This gives O(n log n) total time.

Example explanation

arr = [3,2,5,1]. diff = 2. Count pairs (i<j) where arr[i] - arr[j] <= 2.

• (0,1): 3-2=1 ≤ 2 ✓
• (0,3): 3-1=2 ≤ 2 ✓
• (1,3): 2-1=1 ≤ 2 ✓
• (2,1): no (j must be > i). (2,3): 5-1=4 > 2 ✗. Valid: 3 out of... wait i<j means: (0,1),(0,2),(0,3),(1,2),(1,3),(2,3). Check each. (0,1): 1≤2✓, (0,2): -2≤2✓, (0,3): 2≤2✓, (1,2): -3≤2✓, (1,3): 1≤2✓, (2,3): 4>2✗. Count=5.

Common mistakes candidates make

• Forgetting to rearrange the inequality before solving.
• Using O(n²) brute force scan.
• Incorrect merge sort pair counting (sorting and counting must be coordinated carefully).
• Off-by-one in binary search for counting valid left elements.

Interview preparation tip

Inequality-pair counting problems often reduce to counting inversions with a threshold. The key transformation: rearrange f(i,j) ≤ C into a form where one variable is on each side, then use merge sort or BIT to count efficiently. Practice the standard merge-sort inversion counting first, then extend to threshold variants. This technique appears in several hard array problems at Meta and Google.