1885. Count Pairs in Two Arrays 🔒
Problem Description
You are given two integer arrays nums1
and nums2
, both of length n
. Your task is to count the number of pairs of indices (i, j)
that satisfy the following conditions:
i < j
(the first index must be strictly less than the second index)nums1[i] + nums1[j] > nums2[i] + nums2[j]
(the sum of elements fromnums1
at positionsi
andj
must be greater than the sum of elements fromnums2
at the same positions)
The key insight is that we need to find pairs where the sum from the first array exceeds the sum from the second array at the same index positions.
For example, if we have:
nums1 = [2, 1, 2, 1]
nums2 = [1, 2, 1, 2]
We would check all pairs (i, j)
where i < j
:
- For pair
(0, 1)
: Check if2 + 1 > 1 + 2
(which is3 > 3
, false) - For pair
(0, 2)
: Check if2 + 2 > 1 + 1
(which is4 > 2
, true) - And so on...
The solution transforms this problem by rearranging the inequality to (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0
. This allows us to create a new array where each element is the difference between corresponding elements of nums1
and nums2
, then find pairs in this new array whose sum is positive. The sorting and two-pointer technique efficiently counts all valid pairs without checking every possible combination.
Intuition
The original condition nums1[i] + nums1[j] > nums2[i] + nums2[j]
involves comparing sums from two different arrays, which makes it complex to work with directly. Let's rearrange this inequality to see if we can simplify it.
By moving terms around, we get:
nums1[i] + nums1[j] > nums2[i] + nums2[j]
→ nums1[i] - nums2[i] + nums1[j] - nums2[j] > 0
This rearrangement reveals something important: we can think of this as the sum of two differences being positive. If we define a new array nums
where nums[k] = nums1[k] - nums2[k]
, then our condition becomes simply nums[i] + nums[j] > 0
.
Now we've transformed the problem into finding pairs in a single array whose sum is positive. This is a classic two-sum variant problem.
Why does sorting help? Once we sort the array, we can use the two-pointer technique efficiently. Consider the sorted array with pointers at both ends:
- If the smallest element (left) plus the largest element (right) is positive, then the smallest element paired with ANY element from its right up to the largest will also give a positive sum
- If their sum is not positive, we know the smallest element cannot form a valid pair with the current right element (or any smaller element to its left), so we need to move to a larger left element
This way, instead of checking all O(n²)
pairs, we can count valid pairs in O(n log n)
time (sorting) plus O(n)
time (two-pointer traversal). The key insight is recognizing that the problem can be transformed into a simpler form where established algorithms apply directly.
Learn more about Two Pointers, Binary Search and Sorting patterns.
Solution Approach
The implementation follows these key steps:
Step 1: Transform the Array
nums = [a - b for a, b in zip(nums1, nums2)]
We create a new array nums
where each element is the difference between corresponding elements of nums1
and nums2
. This transforms our problem from finding pairs where nums1[i] + nums1[j] > nums2[i] + nums2[j]
to finding pairs where nums[i] + nums[j] > 0
.
Step 2: Sort the Array
nums.sort()
Sorting enables us to use the two-pointer technique efficiently. After sorting, smaller values are on the left and larger values are on the right.
Step 3: Initialize Two Pointers
l, r = 0, len(nums) - 1
ans = 0
We set up two pointers: l
starting at the beginning (smallest element) and r
at the end (largest element). The variable ans
keeps track of our count.
Step 4: Two-Pointer Traversal
while l < r: while l < r and nums[l] + nums[r] <= 0: l += 1 ans += r - l r -= 1
The outer loop continues while l < r
. For each position of the right pointer r
:
-
Inner while loop: We move the left pointer
l
to the right as long asnums[l] + nums[r] <= 0
. This finds the first position wherenums[l] + nums[r] > 0
. -
Count valid pairs: Once we find a valid
l
, all indices froml
tor-1
paired with indexr
form valid pairs. That'sr - l
pairs total. We add this count to our answer. -
Move right pointer: We then decrement
r
to check pairs with the next largest element.
Why this works:
- If
nums[l] + nums[r] > 0
, thennums[k] + nums[r] > 0
for alll ≤ k < r
(since the array is sorted andnums[k] ≥ nums[l]
) - By fixing
r
and finding the smallest validl
, we can count all valid pairs with right endpointr
in constant time - Moving
r
leftward ensures we count each pair exactly once
Time Complexity: O(n log n)
for sorting + O(n)
for the two-pointer traversal = O(n log n)
Space Complexity: O(n)
for the transformed array nums
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Given:
nums1 = [3, 1, 4, 2]
nums2 = [2, 3, 1, 1]
Step 1: Transform the Array
Create the difference array:
nums[0] = 3 - 2 = 1
nums[1] = 1 - 3 = -2
nums[2] = 4 - 1 = 3
nums[3] = 2 - 1 = 1
So nums = [1, -2, 3, 1]
Step 2: Sort the Array
After sorting: nums = [-2, 1, 1, 3]
Step 3: Two-Pointer Traversal
Initialize: l = 0
, r = 3
, ans = 0
Iteration 1: r = 3
(element value: 3)
- Check if
nums[0] + nums[3] = -2 + 3 = 1 > 0
✓ Yes! - All indices from
l
tor-1
paired withr
are valid - Count =
r - l = 3 - 0 = 3
valid pairs- Pairs: (0,3), (1,3), (2,3) with sums: 1, 4, 4
- Update:
ans = 0 + 3 = 3
- Move:
r = 2
Iteration 2: r = 2
(element value: 1)
- Check if
nums[0] + nums[2] = -2 + 1 = -1 > 0
✗ No - Move
l
right:l = 1
- Check if
nums[1] + nums[2] = 1 + 1 = 2 > 0
✓ Yes! - Count =
r - l = 2 - 1 = 1
valid pair- Pair: (1,2) with sum: 2
- Update:
ans = 3 + 1 = 4
- Move:
r = 1
Iteration 3: r = 1
(element value: 1)
- Now
l = 1
andr = 1
, sol < r
is false - Loop terminates
Final Answer: 4
Verification with Original Arrays: The 4 valid pairs in terms of original indices are:
- Indices (1,2):
1 + 4 > 3 + 1
→5 > 4
✓ - Indices (0,2):
3 + 4 > 2 + 1
→7 > 3
✓ - Indices (0,3):
3 + 2 > 2 + 1
→5 > 3
✓ - Indices (2,3):
4 + 2 > 1 + 1
→6 > 2
✓
The transformation and sorting allowed us to efficiently count these pairs without checking all possible combinations.
Solution Implementation
1class Solution:
2 def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
3 # Transform the problem: nums1[i] - nums2[i] + nums1[j] - nums2[j] > 0
4 # This is equivalent to finding pairs where diff[i] + diff[j] > 0
5 diff = [num1 - num2 for num1, num2 in zip(nums1, nums2)]
6
7 # Sort the difference array for two-pointer approach
8 diff.sort()
9
10 # Initialize two pointers and result counter
11 left = 0
12 right = len(diff) - 1
13 count = 0
14
15 # Use two-pointer technique to find valid pairs
16 while left < right:
17 # If sum is not positive, move left pointer to increase sum
18 while left < right and diff[left] + diff[right] <= 0:
19 left += 1
20
21 # All elements between left and right form valid pairs with right
22 # Since diff[left] + diff[right] > 0, and array is sorted,
23 # all diff[k] where k > left will also satisfy diff[k] + diff[right] > 0
24 count += right - left
25
26 # Move right pointer to check next element
27 right -= 1
28
29 return count
30
1class Solution {
2 public long countPairs(int[] nums1, int[] nums2) {
3 int n = nums1.length;
4
5 // Create difference array where diff[i] = nums1[i] - nums2[i]
6 // This transforms the problem: nums1[i] + nums1[j] > nums2[i] + nums2[j]
7 // Into: diff[i] + diff[j] > 0
8 int[] diff = new int[n];
9 for (int i = 0; i < n; i++) {
10 diff[i] = nums1[i] - nums2[i];
11 }
12
13 // Sort the difference array to use two-pointer technique
14 Arrays.sort(diff);
15
16 // Initialize two pointers for finding valid pairs
17 int left = 0;
18 int right = n - 1;
19 long pairCount = 0;
20
21 // Use two-pointer approach to count pairs where diff[left] + diff[right] > 0
22 while (left < right) {
23 // Move left pointer forward while sum is not positive
24 while (left < right && diff[left] + diff[right] <= 0) {
25 left++;
26 }
27
28 // All indices from left to right-1 form valid pairs with index right
29 // Since array is sorted, if diff[left] + diff[right] > 0,
30 // then diff[left+1] + diff[right] > 0, and so on
31 pairCount += right - left;
32
33 // Move right pointer to check next element
34 right--;
35 }
36
37 return pairCount;
38 }
39}
40
1class Solution {
2public:
3 long long countPairs(vector<int>& nums1, vector<int>& nums2) {
4 int n = nums1.size();
5
6 // Transform the problem: for each index i, calculate nums1[i] - nums2[i]
7 // We want to find pairs (i, j) where i < j and
8 // (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0
9 vector<int> differences(n);
10 for (int i = 0; i < n; ++i) {
11 differences[i] = nums1[i] - nums2[i];
12 }
13
14 // Sort the differences array to use two-pointer technique
15 sort(differences.begin(), differences.end());
16
17 // Use two pointers to count valid pairs efficiently
18 int left = 0;
19 int right = n - 1;
20 long long pairCount = 0;
21
22 // For each right pointer position, find all valid left positions
23 while (left < right) {
24 // Move left pointer forward while the sum is non-positive
25 while (left < right && differences[left] + differences[right] <= 0) {
26 ++left;
27 }
28
29 // All indices from left to right-1 form valid pairs with right
30 // Since differences[left] + differences[right] > 0 and array is sorted,
31 // all elements from left to right-1 will also satisfy the condition
32 pairCount += right - left;
33
34 // Move to the next right position
35 --right;
36 }
37
38 return pairCount;
39 }
40};
41
1/**
2 * Counts the number of valid pairs (i, j) where i < j and
3 * nums1[i] + nums1[j] > nums2[i] + nums2[j]
4 *
5 * The condition can be rearranged to:
6 * (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0
7 *
8 * @param nums1 - First array of numbers
9 * @param nums2 - Second array of numbers
10 * @returns The count of valid pairs
11 */
12function countPairs(nums1: number[], nums2: number[]): number {
13 const arrayLength: number = nums1.length;
14
15 // Transform the problem: create difference array where diff[i] = nums1[i] - nums2[i]
16 // This allows us to find pairs where diff[i] + diff[j] > 0
17 const differences: number[] = [];
18 for (let i = 0; i < arrayLength; i++) {
19 differences.push(nums1[i] - nums2[i]);
20 }
21
22 // Sort the differences array in ascending order
23 differences.sort((a: number, b: number) => a - b);
24
25 // Use two-pointer technique to count valid pairs
26 let pairCount: number = 0;
27 let leftPointer: number = 0;
28 let rightPointer: number = arrayLength - 1;
29
30 while (leftPointer < rightPointer) {
31 // Move left pointer right while sum is non-positive
32 while (leftPointer < rightPointer && differences[leftPointer] + differences[rightPointer] <= 0) {
33 leftPointer++;
34 }
35
36 // All elements between leftPointer and rightPointer form valid pairs with rightPointer
37 pairCount += rightPointer - leftPointer;
38
39 // Move right pointer left to check next element
40 rightPointer--;
41 }
42
43 return pairCount;
44}
45
Time and Space Complexity
Time Complexity: O(n × log n)
The dominant operation in this algorithm is the sorting of the nums
array, which takes O(n × log n)
time where n
is the length of the input arrays. The list comprehension to create the nums
array takes O(n)
time. The two-pointer traversal in the while loop also takes O(n)
time in total, as each element is visited at most twice (once by each pointer). Therefore, the overall time complexity is O(n × log n)
.
Space Complexity: O(n)
The algorithm creates a new array nums
of size n
to store the differences between corresponding elements of nums1
and nums2
. This is the primary space consumption. The sorting operation may use additional space depending on the implementation (Python's Timsort uses up to O(n)
auxiliary space in the worst case), but this doesn't change the overall space complexity. Therefore, the space complexity is O(n)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Forgetting to Handle the Index Order Constraint
A critical pitfall is misunderstanding how the sorting transformation affects the original index constraint i < j
. When we sort the difference array, we lose the original index information, which might seem problematic since the problem requires i < j
.
Why this seems like a problem:
- Original constraint: We need pairs
(i, j)
wherei < j
- After sorting, the elements are reordered, so we might think we're counting invalid pairs
Why it's actually not a problem:
The key insight is that we're counting unordered pairs from the sorted array, and each unordered pair corresponds to exactly one valid ordered pair in the original array. When we find indices left < right
in the sorted array that satisfy diff[left] + diff[right] > 0
, this represents some pair of original indices (i, j)
that would satisfy our condition - we just don't know which specific i
and j
they are, but we know such a pair exists.
2. Incorrect Counting Logic
Pitfall Code:
while left < right: if diff[left] + diff[right] > 0: count += 1 # Wrong! Only counts one pair left += 1 right -= 1
Why it's wrong: When diff[left] + diff[right] > 0
, due to the sorted nature of the array, ALL elements from left
to right - 1
can pair with right
to form valid pairs. The above code only counts one pair instead of right - left
pairs.
Correct approach:
while left < right: while left < right and diff[left] + diff[right] <= 0: left += 1 count += right - left # Count all valid pairs with current right right -= 1
3. Inefficient Inner Loop Implementation
Pitfall Code:
while left < right:
if diff[left] + diff[right] > 0:
# Count all valid pairs with current right
for k in range(left, right):
count += 1
right -= 1
else:
left += 1
Why it's inefficient: Using a for loop to count adds unnecessary time complexity. Since we know there are exactly right - left
valid pairs, we can add them directly.
4. Off-by-One Errors in Counting
Common mistakes:
- Adding
right - left + 1
instead ofright - left
(this would incorrectly count the pair(right, right)
) - Not properly handling the boundary when
left
reachesright
Correct boundary handling:
while left < right: # Stops when left == right (can't form a pair with itself) # ... rest of the logic count += right - left # Correct count: includes left but excludes right itself
5. Missing Edge Cases
Pitfall: Not considering arrays where all differences are non-positive or all are positive.
Solution: The two-pointer approach naturally handles these cases:
- If all differences ≤ 0: The inner while loop will advance
left
until it meetsright
, andcount
remains 0 - If all differences > 0: Every pair is valid, and the algorithm correctly counts them all
Test with edge cases:
# All negative differences nums1 = [1, 1, 1] nums2 = [2, 2, 2] # diff = [-1, -1, -1], result should be 0 # All positive differences nums1 = [3, 3, 3] nums2 = [1, 1, 1] # diff = [2, 2, 2], result should be 3 (all possible pairs)
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Don’t Miss This!