Is Count Pairs in Two Arrays easy or hard?

Count Pairs in Two Arrays is typically classified as a Medium problem. The main challenge is recognizing that the inequality can be rewritten using a difference array, which then enables a standard sorted two-pointer pair counting pattern.

Count Pairs in Two Arrays Python/Java solution

Most implementations compute the diff array, sort it, then use two pointers to count pairs whose sum is positive. The logic is identical across Python, Java, C++, Go, JavaScript, and TypeScript, differing only in syntax for sorting and pointer movement.

How to solve Count Pairs in Two Arrays in O(n log n)?

First compute diff[i] = nums1[i] - nums2[i]. Sort this array, then use two pointers from both ends. If diff[left] + diff[right] > 0, all elements between left and right form valid pairs with right, so add right - left to the count and move right leftward; otherwise move left forward.

What is the best approach for Count Pairs in Two Arrays?

The optimal approach transforms the problem using diff[i] = nums1[i] - nums2[i]. After sorting this difference array, apply a two-pointer scan to count pairs where diff[i] + diff[j] > 0. Sorting takes O(n log n) time and the pointer sweep is O(n), making it efficient for large inputs.

Is Count Pairs in Two Arrays asked at Google/Amazon/Meta?

Problems involving pair counting with array transformations and two-pointer scans are common in interviews at companies like Google, Amazon, and Meta. Variations often test sorting, inequality manipulation, and efficient pair counting in arrays.

What data structure is used in Count Pairs in Two Arrays?

The core structure is a transformed array called diff, derived from nums1 and nums2. After sorting this array, the algorithm relies on the two-pointer technique or binary search to count valid index pairs efficiently.

What is the time complexity of Count Pairs in Two Arrays?

The optimized solution runs in O(n log n) time due to sorting the difference array. After sorting, counting valid pairs with the two-pointer technique takes O(n). The brute force method requires O(n^2) comparisons and is usually too slow for large constraints.

Description Hints 4 Solution Video 8:26

1885. Count Pairs in Two Arrays

Medium60.5% acceptance2 companiesPremium elsewhere, free here

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.

Example 1:

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:

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⁵
1 <= nums1[i], nums2[i] <= 10⁵

Asked at 2 companies

Shopee Teradata

Topics

Hints open one at a time

Hint 1

We can write it as nums1[i] - nums2[i] > nums2[j] - nums1[j] instead of nums1[i] + nums1[j] > nums2[i] + nums2[j].

Hint 2

Store nums1[idx] - nums2[idx] in a data structure.

Hint 3

Store nums2[idx] - nums1[idx] in a different data structure.

Hint 4

For each integer in the first data structure, count the number of the strictly smaller integers in the second data structure with a larger index in the original array.

8:26

Still stuck?Read the written solution, or watch a walkthrough.

Open solution