Count Pairs in Two Arrays - Solution & Explanation

Problem Overview: You are given two arrays nums1 and nums2 of equal length. Count the number of index pairs (i, j) with i < j such that nums1[i] + nums1[j] > nums2[i] + nums2[j]. The trick is recognizing that the inequality can be rearranged to compare pair sums of transformed values instead of working with both arrays directly.

A useful transformation is to compute diff[i] = nums1[i] - nums2[i]. The condition becomes diff[i] + diff[j] > 0. Once reduced to this form, the task becomes counting pairs in a single array whose sum is positive. This turns the problem into a classic Array pair-counting problem.

Approach 1: Brute Force (O(n²) time, O(1) space)

Iterate over every pair of indices (i, j) where i < j. For each pair, compute (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) and check if it is greater than zero. Increment the count when the condition holds. This method is straightforward and useful for validating logic during interviews, but it performs O(n²) comparisons and becomes impractical for large inputs.

Approach 2: Sorting + Two Pointers (O(n log n) time, O(n) space)

First compute the diff array and sort it using Sorting. Once sorted, use the classic Two Pointers technique. Start one pointer at the beginning and the other at the end. If diff[left] + diff[right] > 0, then every index between left and right - 1 will also satisfy the condition with right, because the array is sorted. Add right - left to the answer and move the right pointer inward. Otherwise move the left pointer forward. This reduces the pair counting to a single linear scan after sorting.

Approach 3: Sorting + Binary Search (O(n log n) time, O(n) space)

After building and sorting the diff array, iterate through each index i. For every value diff[i], you need the smallest index j > i such that diff[i] + diff[j] > 0. This can be found using Binary Search for the first value greater than -diff[i]. The number of valid pairs contributed by i is the remaining elements to the right of that position. The approach is clean and predictable but slightly slower in practice than the two-pointer sweep.

Recommended for interviews: The sorting + two pointers solution is typically expected. Transforming the inequality into a single array difference shows problem insight, and the two-pointer sweep demonstrates familiarity with common sorted-array patterns. Mentioning the brute force approach first shows understanding of the baseline, but implementing the O(n log n) optimized version signals strong algorithmic thinking.