Count Cross-Array Pairs with a Target Sum

Question

The question asks the candidate to write a function that counts the number of pairs from two different arrays that sum up to a given target value.

Codemia · Accepted Answer

To solve the problem of counting pairs from two arrays that sum to a target value, we first need to clarify the requirements. We are given two arrays, `array1` and `array2`, and a target sum. Our goal is to find all unique pairs `(a, b)` such that `a` is from `array1` and `b` is from `array2`, and their sum equals the target.

We can use a hash set to store the required complements for each element in the first array. This allows us to check in constant time whether there exists a corresponding element in the second array that can form a pair with the current element from the first array. The steps are as follows:

1. Initialize a hash set to store the required complements.
2. Iterate through `array1` and for each element `a`, calculate the complement as `target - a` and add it to the hash set.
3. Iterate through `array2` and for each element `b`, check if `b` exists in the hash set. If it does, we have found a valid pair.

Here is a Python implementation of the described approach:

```python
def count_pairs(array1, array2, target):
    complements = set()
    count = 0

# Step 1: Store complements from array1
    for a in array1:
        complements.add(target - a)

# Step 2: Check for pairs in array2
    for b in array2:
        if b in complements:
            count += 1

return count
```

This code efficiently counts the pairs by leveraging the hash set for quick lookups.

The time complexity of this solution is O(n + m), where `n` is the length of `array1` and `m` is the length of `array2`. This is because we iterate through both arrays once. The space complexity is O(n) due to the storage of complements in the hash set. This approach is efficient and scales well with larger arrays.

It is important to consider edge cases such as:
1. Empty arrays: The function should return 0 if either array is empty.
2. No valid pairs: The function should correctly return 0 if no pairs sum to the target.
3. Duplicate elements: The function should handle duplicates correctly, counting pairs only when they form valid combinations.

Count Cross-Array Pairs with a Target Sum

Visa

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

Visa Software Engineer I Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string