Katkat
Back

Count Cross-Array Pairs with a Target Sum

VisaSoftware Engineer I · Online Assessment
MediumSoftware Engineer IOnline AssessmentCoding & Algorithms

Last updated

Tests linear-time frequency-map counting across two independent arrays to find pairs that sum to a target, properly accounting for duplicates and 64-bit integer overflow.

Problem Statement

You are given two integer arrays, nums1 and nums2, and an integer target.

Your task is to compute the total number of index pairs (i, j) such that nums1[i] + nums2[j] == target, where 0 <= i < len(nums1) and 0 <= j < len(nums2).

If either array contains duplicate elements, each distinct index pair (i, j) that satisfies the condition must be counted separately.

Function Signature

def count_target_pairs(nums1: list[int], nums2: list[int], target: int) -> int:
    pass

Input and Output Format

  • Input:
    • nums1: A list of integers.
    • nums2: A list of integers.
    • target: An integer.
  • Output:
    • A 64-bit integer representing the total count of valid pairs (i, j).

Constraints

  • 0 <= len(nums1), len(nums2) <= 10^5
  • -10^9 <= nums1[i], nums2[j] <= 10^9
  • -2 * 10^9 <= target <= 2 * 10^9

Examples

Example 1

Input: nums1 = [1, 2, 2, 3], nums2 = [4, 3, 3, 1], target = 5
Output: 5
Explanation:
Valid pairs (i, j) where nums1[i] + nums2[j] == 5 are:
- nums1[0] (1) + nums2[0] (4) = 5
- nums1[1] (2) + nums2[1] (3) = 5
- nums1[1] (2) + nums2[2] (3) = 5
- nums1[2] (2) + nums2[1] (3) = 5
- nums1[2] (2) + nums2[2] (3) = 5
Total valid pairs = 5.

Example 2

Input: nums1 = [-3, 0, 5], nums2 = [3, -5, 0], target = 0
Output: 3
Explanation:
- nums1[0] (-3) + nums2[0] (3) = 0
- nums1[1] (0) + nums2[2] (0) = 0
- nums1[2] (5) + nums2[1] (-5) = 0
Total valid pairs = 3.

Edge Cases to Consider

  • Either nums1 or nums2 is empty (the answer should be 0).
  • Arrays containing large negative or positive values.
  • The total count of pairs exceeding 2^31 - 1 (e.g., two arrays of size 10^5 where all elements sum to target will yield 10^10 pairs).

Hints

Hint 1

A brute-force comparison of all pairs takes O(N * M) time, which will exceed the time limit for arrays up to 10^5 elements.

Hint 2

For each value x in nums1, the matching value required from nums2 is target - x.

Hint 3

Precompute the frequency of each value in one array using a hash map, then iterate through the other array (or hash map) to sum matching pair counts in O(N + M) time.

Follow-up questions

  • How would you solve this problem if both arrays were already sorted in ascending order and you had strict O(1) auxiliary space limits?
  • If nums2 is stored on disk across multiple chunks because it is too large to fit in memory, how would you adapt your approach?
  • How does the solution change if we need to return unique value pairs (val1, val2) instead of index pairs (i, j)?