Solution: Count Pairs in Two Arrays

Statement

You are given two positive integer arrays, nums1 and nums2, both of length $n$. Your task is to count and return the number of pairs of indexes $(i, j)$ where:

• $i < j$ , and

• $\text{nums1}[i] + \text{nums1}[j] > \text{nums2}[i] + \text{nums2}[j]$

In simpler terms, the sum of two elements from nums1 must be greater than that of the corresponding elements from nums2.

Constraints:

• $n =$ nums1.length $=$ nums2.length

• $1 \leq n \leq 10^3$

• $1 \leq$ nums1[i], nums2[i] $\leq 10^4$

Solution

A brute force approach would involve iterating through all pairs $(i, j)$ using nested loops. For each pair:

1. Compute $\text{nums1}[i] + \text{nums1}[j]$.

2. Compare it with $\text{nums2}[i] + \text{nums2}[j]$.

3. Increment a counter if the condition is satisfied.

However, this approach requires $O(n^2)$ comparisons, which is inefficient for large inputs.

To optimize, we can simplify the condition: