Facebook Pixel

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:

  1. i < j (the first index must be strictly less than the second index)
  2. nums1[i] + nums1[j] > nums2[i] + nums2[j] (the sum of elements from nums1 at positions i and j must be greater than the sum of elements from nums2 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 if 2 + 1 > 1 + 2 (which is 3 > 3, false)
  • For pair (0, 2): Check if 2 + 2 > 1 + 1 (which is 4 > 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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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 as nums[l] + nums[r] <= 0. This finds the first position where nums[l] + nums[r] > 0.

  • Count valid pairs: Once we find a valid l, all indices from l to r-1 paired with index r form valid pairs. That's r - 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, then nums[k] + nums[r] > 0 for all l ≤ k < r (since the array is sorted and nums[k] ≥ nums[l])
  • By fixing r and finding the smallest valid l, we can count all valid pairs with right endpoint r 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 Evaluator

Example 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 to r-1 paired with r 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 and r = 1, so l < r is false
  • Loop terminates

Final Answer: 4

Verification with Original Arrays: The 4 valid pairs in terms of original indices are:

  1. Indices (1,2): 1 + 4 > 3 + 1 → 5 > 4 ✓
  2. Indices (0,2): 3 + 4 > 2 + 1 → 7 > 3 ✓
  3. Indices (0,3): 3 + 2 > 2 + 1 → 5 > 3 ✓
  4. 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) where i < 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 of right - left (this would incorrectly count the pair (right, right))
  • Not properly handling the boundary when left reaches right

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 meets right, and count 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)
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More