Find a Target Sum Using Two Sorted Arrays
Company: Squarepoint
Role: Risk Technology Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Given two arrays sorted in nondecreasing order and a target, return whether there
is a pair containing one value from each array whose sum equals the target.
### Constraints & Assumptions
- Each array contains at most 500,000 32-bit signed integers.
- Either array may be empty and values may repeat.
- Use signed 64-bit addition in Java and C++ to avoid 32-bit overflow.
- The target is an integer in the attainable two-addend range `[-4,294,967,296, 4,294,967,294]`; every input and computed sum is within `+/-2^53`, so Python integers and JavaScript numbers are exact as well.
### Clarifications
- Exactly one element must come from each array.
- Only a boolean is required.
- Input order is guaranteed; no sorting is needed.
### Examples
```text
a = [-5, 1, 4, 10]
b = [2, 3, 8]
target = 7
output = true # 4 + 3
```
### Hints
```hint Start at opposite extremes
The smallest value in one array and largest in the other give a sum that can be adjusted monotonically.
```
```hint Move only one pointer
A sum below the target needs a larger left value; a sum above it needs a smaller right value.
```
Quick Answer: Determine whether two sorted arrays contain one value each that sum to a target using opposite-end pointers and overflow-safe arithmetic.
Given two arrays sorted in nondecreasing order and an integer target, return whether there is a pair containing exactly one value from each array whose sum equals the target. Either array may be empty, values may repeat, and no sorting is needed. Use signed 64-bit addition in Java and C++ so adding two signed 32-bit values cannot overflow.
Constraints
- Each input array has at most 500000 signed 32-bit integers.
- Both arrays are sorted in nondecreasing order.
- Either array may be empty, and values may repeat.
- Exactly one element must come from each array.
- The target is in [-4294967296, 4294967294].
- Use signed 64-bit addition in Java and C++.
Examples
Input: ([-5, 1, 4, 10], [2, 3, 8], 7)
Expected Output: True
Explanation: The cross-array pair 4 and 3 sums to 7.
Input: ([], [1, 2, 3], 3)
Expected Output: False
Explanation: A pair cannot be formed when one array is empty.
Hints
- Start at the smallest value in one array and the largest value in the other.
- A sum below the target needs a larger left value; a sum above it needs a smaller right value.