Skip to main content
Talentd

Count Pairs in Two Arrays - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersBinary SearchSorting13 min readAsked at: Teradata, Shopee
Practice this problem

Problem Statement

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

Approach Overview

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.

Solution

We can transform the inequality in the problem to nums1[i] - nums2[i] + nums1[j] - nums2[j] > 0, which simplifies to nums[i] + nums[j] > 0, where nums[i] = nums1[i] - nums2[i].

For the array nums, we need to find all pairs (i, j) that satisfy nums[i] + nums[j] > 0.

We can sort the array nums and then use the two-pointer method. Initialize the left pointer l = 0 and the right pointer r = n - 1. Each time, we check if nums[l] + nums[r] is less than or equal to 0. If it is, we move the left pointer to the right in a loop until nums[l] + nums[r] > 0. At this point, all pairs with the left pointer at l, l + 1, l + 2, cdots, r - 1 and the right pointer at r satisfy the condition, and there are r - l such pairs. We add these pairs to the answer. Then, move the right pointer to the left and continue the above process until l \ge r.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n²)O(1)Small inputs or when validating the core inequality logic
Sorting + Two PointersO(n log n)O(n)Best general solution after transforming to a difference array
Sorting + Binary SearchO(n log n)O(n)When you prefer predictable searches instead of two-pointer sweeps

Video Solution

1885. Count Pairs in Two Arrays - Week 1/5 Leetcode May Challenge • Programming Live with Larry • 991 views views

Watch 1 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Count Pairs in Two Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Value of Equation

Next

Substrings That Begin and End With the Same Letter