We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Pairs in Two Arrays

Number: 2036

Difficulty: Medium

Paid? Yes

Companies: Shopee

Problem Description

Given two integer arrays nums1 and nums2, both of length n, count the number of pairs of indices (i, j) such that i < j and nums1[i] + nums1[j] > nums2[i] + nums2[j].

Key Insights

  • Transform the inequality: rewrite nums1[i] + nums1[j] > nums2[i] + nums2[j] as (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0.
  • Create a new array diff where diff[i] = nums1[i] - nums2[i].
  • The problem reduces to counting pairs (i, j) with i < j such that diff[i] + diff[j] > 0.
  • Sorting the diff array helps us leverage binary search or two-pointer techniques to efficiently count valid pairs.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and binary search operations. Space Complexity: O(n) for storing the diff array.

Solution

We first compute the difference array diff, where each element diff[i] represents the difference between nums1[i] and nums2[i]. The original inequality then becomes diff[i] + diff[j] > 0 for indices i < j. After sorting diff, for every diff[i] (iterating from the smallest), we can quickly use binary search to find the first index where the elements satisfy diff[j] > -diff[i]. The count of valid pairs for diff[i] will be the total elements to the right of that index. Summing these counts gives the final answer. This method avoids brute-force O(n^2) checking, instead reducing complexity with sorting and binary search.

Code Solutions

def countPairs(nums1, nums2):
    # Compute the difference array
    diff = [a - b for a, b in zip(nums1, nums2)]
    # Sort the diff array
    diff.sort()
    
    import bisect
    n = len(diff)
    pair_count = 0
    # For each element in diff, find the first index with value greater than -current diff
    for i in range(n):
        # Find insertion index for -diff[i] in sorted list such that diff[j] > -diff[i]
        pos = bisect.bisect_right(diff, -diff[i])
        # Count pairs from max(i+1, pos) to end (ensuring j > i)
        j = max(i + 1, pos)
        pair_count += n - j
        
    return pair_count

# Example usage:
nums1 = [2, 1, 2, 1]
nums2 = [1, 2, 1, 2]
print(countPairs(nums1, nums2))  # Output: 1
← Back to All Questions