Problem

Given two integer arrays nums1 and nums2 of length n, count the pairs of indices (i, j) such that i < j and nums1[i] + nums1[j] > nums2[i] + nums2[j].

Return the number of pairs satisfying the condition.

Examples

Example 1:

1
2
3
4

Input: nums1 = [2,1,2,1], nums2 = [1,2,1,2]
Output: 1
Explanation: The pairs satisfying the condition are:
- (0, 2) where 2 + 2 > 1 + 1.

Example 2:

1
2
3
4
5
6
7
8

Input: nums1 = [1,10,6,2], nums2 = [1,4,1,5]
Output: 5
Explanation: The pairs satisfying the condition are:
- (0, 1) where 1 + 10 > 1 + 4.
- (0, 2) where 1 + 6 > 1 + 1.
- (1, 2) where 10 + 6 > 4 + 1.
- (1, 3) where 10 + 2 > 4 + 5.
- (2, 3) where 6 + 2 > 1 + 5.

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^5

Solution

Method 1 – Sorting and Two Pointers

Intuition

We can reduce the problem to counting pairs (i, j) with i < j such that (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0. By sorting the differences, we can use two pointers or binary search to efficiently count valid pairs.

Approach

  1. Compute the difference array: diff[i] = nums1[i] - nums2[i].
  2. Sort the diff array.
  3. For each index i, use binary search to find the smallest j > i such that diff[i] + diff[j] > 0.
  4. The number of valid pairs for i is n - pos, where pos is the first index where diff[i] + diff[pos] > 0.
  5. Sum up the counts for all i.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    long long countPairs(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> diff(n);
        for (int i = 0; i < n; ++i) diff[i] = nums1[i] - nums2[i];
        sort(diff.begin(), diff.end());
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            int l = i+1, r = n;
            while (l < r) {
                int m = l + (r-l)/2;
                if (diff[i] + diff[m] > 0) r = m;
                else l = m+1;
            }
            ans += n - l;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func CountPairs(nums1, nums2 []int) int64 {
    n := len(nums1)
    diff := make([]int, n)
    for i := 0; i < n; i++ {
        diff[i] = nums1[i] - nums2[i]
    }
    sort.Ints(diff)
    var ans int64
    for i := 0; i < n; i++ {
        l, r := i+1, n
        for l < r {
            m := l + (r-l)/2
            if diff[i]+diff[m] > 0 {
                r = m
            } else {
                l = m+1
            }
        }
        ans += int64(n - l)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public long countPairs(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] diff = new int[n];
        for (int i = 0; i < n; i++) diff[i] = nums1[i] - nums2[i];
        Arrays.sort(diff);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int l = i+1, r = n;
            while (l < r) {
                int m = l + (r-l)/2;
                if (diff[i] + diff[m] > 0) r = m;
                else l = m+1;
            }
            ans += n - l;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countPairs(nums1: IntArray, nums2: IntArray): Long {
        val n = nums1.size
        val diff = IntArray(n) { nums1[it] - nums2[it] }
        diff.sort()
        var ans = 0L
        for (i in 0 until n) {
            var l = i+1; var r = n
            while (l < r) {
                val m = l + (r-l)/2
                if (diff[i] + diff[m] > 0) r = m else l = m+1
            }
            ans += n - l
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def countPairs(self, nums1: list[int], nums2: list[int]) -> int:
        n = len(nums1)
        diff = [a-b for a, b in zip(nums1, nums2)]
        diff.sort()
        ans = 0
        for i in range(n):
            l, r = i+1, n
            while l < r:
                m = (l + r) // 2
                if diff[i] + diff[m] > 0:
                    r = m
                else:
                    l = m + 1
            ans += n - l
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn count_pairs(nums1: Vec<i32>, nums2: Vec<i32>) -> i64 {
        let n = nums1.len();
        let mut diff: Vec<i32> = nums1.iter().zip(nums2.iter()).map(|(&a, &b)| a-b).collect();
        diff.sort();
        let mut ans = 0i64;
        for i in 0..n {
            let (mut l, mut r) = (i+1, n);
            while l < r {
                let m = l + (r-l)/2;
                if diff[i] + diff[m] > 0 {
                    r = m;
                } else {
                    l = m+1;
                }
            }
            ans += (n - l) as i64;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    countPairs(nums1: number[], nums2: number[]): number {
        const n = nums1.length;
        const diff = nums1.map((a, i) => a - nums2[i]);
        diff.sort((a, b) => a - b);
        let ans = 0;
        for (let i = 0; i < n; i++) {
            let l = i+1, r = n;
            while (l < r) {
                const m = l + ((r-l) >> 1);
                if (diff[i] + diff[m] > 0) r = m;
                else l = m+1;
            }
            ans += n - l;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), since we sort the array and for each index perform a binary search.
  • 🧺 Space complexity: O(n), for the difference array.