Count Pairs in Two Arrays

Count Pairs in Two Arrays

What is this problem about?

The "Count Pairs in Two Arrays interview question" is a relational comparison problem. You are given two integer arrays, nums1 and nums2, both of the same length. You need to find the number of pairs $(i, j)$ such that $0 \leq i < j < n$ and nums1[i] + nums1[j] > nums2[i] + nums2[j]. This problem requires you to analyze the interaction between elements at the same index across two different arrays.

Why is this asked in interviews?

Companies like Shopee and Teradata ask the "Count Pairs in Two Arrays coding problem" to evaluate a candidate's ability to simplify a mathematical inequality. The brute-force $O(N^2)$ solution is easy to find, but the optimized $O(N \log N)$ solution requires a clever algebraic transformation and the "Two Pointers interview pattern." It tests your ability to think critically about how to rearrange terms to isolate variables.

Algorithmic pattern used

The key to this problem is Inequality Transformation and Two Pointers.

1. Algebraic Shift: The condition nums1[i] + nums1[j] > nums2[i] + nums2[j] can be rewritten as: (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0.
2. Difference Array: Create a new array diff where diff[i] = nums1[i] - nums2[i]. The problem now becomes finding pairs $(i, j)$ in the diff array such that diff[i] + diff[j] > 0.
3. Sorting: Sort the diff array.
4. Two Pointers: Use two pointers, left at the start and right at the end. If diff[left] + diff[right] > 0, then all elements between left and right will also satisfy the condition when paired with diff[right]. Add right - left to your total and move the right pointer. Otherwise, move the left pointer.

Example explanation

nums1 = [2, 1, 2, 1], nums2 = [1, 2, 1, 2]

1. diff array: [2-1, 1-2, 2-1, 1-2] = [1, -1, 1, -1].
2. Sorted diff: [-1, -1, 1, 1].
3. Two Pointers:
   • left=0 (-1), right=3 (1): Sum = 0. Not $> 0$. left++.
   • left=1 (-1), right=3 (1): Sum = 0. Not $> 0$. left++.
   • left=2 (1), right=3 (1): Sum = 2. $> 0$. All pairs between indices 2 and 3 work. Count += $3 - 2 = 1$. right--. Total pairs: 1.

Common mistakes candidates make

• $O(N^2)$ Brute Force: Trying to check all pairs directly, which is too slow.
• Forgetting the transformation: Trying to solve the problem with the two original arrays separately instead of combining them into a diff array.
• Sorting the wrong arrays: Attempting to sort nums1 and nums2 independently, which breaks the relationship between elements at the same index.

Interview preparation tip

Whenever you see a problem with A[i] + A[j] > B[i] + B[j], your first instinct should be to group the i terms and the j terms together. This "Sorting interview pattern" transformation is a very common technique for turning pair-sum problems into simple array problems.