LeetCode 1885 - Count Pairs in Two Arrays

LeetCode Problem 1885

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to count the number of index pairs (i, j) such that i < j and the sum of elements at these indices in nums1 is greater than the sum of elements at the same indices in nums2. Formally, we want the number of pairs (i, j) where nums1[i] + nums1[j] > nums2[i] + nums2[j].

The inputs are two integer arrays nums1 and nums2 of equal length n. The expected output is a single integer representing the total number of pairs that satisfy the condition. Constraints tell us that n can be as large as 100,000, so a naive O(n²) solution will be too slow. The elements themselves are positive integers up to 100,000, so integer overflow is not an immediate concern in Python, but in Go, we need to use int64 for sums and counts to avoid overflow.

Important edge cases include arrays with identical values, arrays with minimal length (n = 1), and arrays where all elements are equal, which would result in zero valid pairs. The problem guarantees valid input arrays of equal length with at least one element.

Approaches

The brute-force approach iterates over all possible pairs (i, j) and directly checks if nums1[i] + nums1[j] > nums2[i] + nums2[j]. This is guaranteed to be correct because it checks every pair, but it has time complexity O(n²), which is too slow for n = 100,000.

The key insight for a more efficient solution is to transform the problem into a one-array problem. Define diff[i] = nums1[i] - nums2[i]. The original condition becomes diff[i] + diff[j] > 0. Now, we need the number of pairs (i, j) where i < j and diff[i] + diff[j] > 0. Sorting the diff array and using a two-pointer or binary search technique allows us to efficiently count valid pairs in O(n log n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Iterate all pairs and count directly
Optimal	O(n log n)	O(n)	Transform to diff array, sort, and use binary search

Algorithm Walkthrough

1. Compute a new array diff where diff[i] = nums1[i] - nums2[i]. This simplifies the pair condition to diff[i] + diff[j] > 0.
2. Sort the diff array in ascending order. Sorting allows binary search for efficient counting.
3. Initialize a counter count to zero. This will store the total number of valid pairs.
4. Iterate over each index i in diff. For each diff[i], we want the number of j > i such that diff[i] + diff[j] > 0.
5. Use binary search (or two pointers) on the sorted array from index i+1 to the end to find the first index j where diff[j] > -diff[i].
6. The number of valid pairs for this i is (n - j). Add this to the counter.
7. Continue this process for all i from 0 to n-2.
8. Return count.

Why it works: Sorting preserves the order for efficient searching. For each diff[i], binary search finds the smallest diff[j] that satisfies the condition. Because the array is sorted, all elements to the right of this index will also satisfy the condition, ensuring all valid pairs are counted exactly once.

Python Solution

from typing import List
import bisect

class Solution:
    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        diff = [nums1[i] - nums2[i] for i in range(n)]
        diff.sort()
        
        count = 0
        for i in range(n):
            target = -diff[i] + 1
            j = bisect.bisect_left(diff, target, i + 1)
            count += n - j
        return count

In this Python implementation, we first compute the diff array and sort it. For each element diff[i], we calculate target = -diff[i] + 1 because we need diff[i] + diff[j] > 0. Using bisect_left, we efficiently find the smallest index j where diff[j] >= target. The number of valid pairs for i is n - j, which we add to the total count.

Go Solution

import "sort"

func countPairs(nums1 []int, nums2 []int) int64 {
    n := len(nums1)
    diff := make([]int, n)
    for i := 0; i < n; i++ {
        diff[i] = nums1[i] - nums2[i]
    }
    sort.Ints(diff)
    
    var count int64
    for i := 0; i < n; i++ {
        target := -diff[i] + 1
        j := sort.Search(n-i-1, func(k int) bool { return diff[i+1+k] >= target })
        count += int64(n - (i + 1 + j))
    }
    return count
}

In Go, the approach mirrors Python but uses sort.Ints for sorting and sort.Search for binary search. Care is taken to use int64 for the count to avoid integer overflow for large inputs. The sort.Search function searches in the subarray diff[i+1:] to find the first element meeting the target condition.

Worked Examples

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

Compute diff = [1, -1, 1, -1], sort to [-1, -1, 1, 1].

Iteration:

i	diff[i]	target	j (first index ≥ target)	pairs added
0	-1	2	3	1
1	-1	2	3	1
2	1	0	3	1
3	1	0	4	0

Total count = 1 (as duplicates of index pairs are ignored by using i < j).

Example 2: nums1 = [1,10,6,2], nums2 = [1,4,1,5]

Compute diff = [0, 6, 5, -3], sort to [-3, 0, 5, 6].

Iteration:

i	diff[i]	target	j	pairs added
0	-3	4	2	2
1	0	1	2	2
2	5	-4	3	1
3	6	-5	4	0

Total count = 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting is O(n log n), and each binary search is O(log n), iterated n times
Space	O(n)	Extra array diff of size n

Sorting and binary search reduce the naive O(n²) approach to O(n log n), making the solution scalable for large n up to 100,000.

Test Cases

# Provided examples
assert Solution().countPairs([2,1,2,1], [1,2,1,2]) == 1  # simple case
assert Solution().countPairs([1,10,6,2], [1,4,1,5]) == 5  # multiple valid pairs

# Edge cases
assert Solution().countPairs([1], [1]) == 0  # single element, no pairs
assert Solution().countPairs([1,1,1], [1,1,1]) == 0  # all differences zero
assert Solution().countPairs([5,5,5], [1,2,3]) == 3  # all pairs valid
assert Solution().countPairs([1,2,3,4,5], [5,4,3,2,1]) == 4  # mix of valid and invalid

Test	Why
[2,1,2,1], [1,2,1,2]	simple case with one valid pair
[1,10,6,2], [1,4,1,5]	multiple valid pairs across array
[1], [1]	minimal length array
[1,1,1], [1,1,1]	no differences, expect zero pairs
[5,5,5], [1,2,3]	all differences positive, all pairs valid