Find a Target Sum Using Two Sorted Arrays

Problem Statement

Given two sorted arrays of integers arr1 and arr2, and an integer target, determine whether there exists an element a from arr1 and an element b from arr2 such that a + b == target.

Both input arrays are sorted in non-decreasing order. Your solution must run in O(m + n) time, where m and n are the lengths of arr1 and arr2 respectively, and use O(1) extra space. Additionally, your implementation must be safe against 64-bit signed integer overflow.

Function Signature

def has_target_pair(arr1: list[int], arr2: list[int], target: int) -> bool:
    pass

Input & Output Format

• Input: Two lists of integers arr1 and arr2, each sorted in non-decreasing order, and a single integer target.
• Output: Return True if there exist a in arr1 and b in arr2 such that a + b == target, otherwise return False.

Constraints

• 0 <= len(arr1), len(arr2) <= 10^6
• -2^63 <= arr1[i], arr2[j], target <= 2^63 - 1
• Memory limit: O(1) auxiliary space
• Time limit: O(len(arr1) + len(arr2))

Examples

Example 1

Input: arr1 = [1, 3, 5, 8], arr2 = [2, 4, 9, 11], target = 13
Output: True
Explanation: Choosing 2 from arr1 and 11 from arr2 gives 2 + 11 = 13 (or choosing 4 from arr2 and 9 does not match 13, but arr1[3] + arr2[1] = 8 + 4 = 12; arr1[0] + arr2[3] = 1 + 11 = 12; arr1[2] + arr2[1] = 5 + 8 not present; here arr1[3] = 8, arr2[0] = 2 gives 10, arr1[1] = 3, arr2[2] = 9 gives 12, arr1[3] + arr2[0] = 10, but 2 in arr2 + ... wait: arr1[1] + arr2[2] = 3 + 9 = 12; arr1 = [1, 3, 5, 8], arr2 = [2, 4, 9, 11], target = 13 -> 4 + 9? 4 is in arr2, 9 is in arr2. Notice 2 + 11 = 13 is within arr2 alone. But arr1 has 2? No, arr1 has [1, 3, 5, 8]. If target is 14: 3 + 11 = 14 or 5 + 9 = 14.

Let's provide verified values:

Input: arr1 = [1, 3, 5, 8], arr2 = [2, 4, 9, 11], target = 14
Output: True
Explanation: arr1[1] + arr2[3] = 3 + 11 = 14 (also arr1[2] + arr2[2] = 5 + 9 = 14).

Example 2

Input: arr1 = [-10, -3, 0, 4], arr2 = [-5, 1, 7], target = -15
Output: True
Explanation: arr1[0] + arr2[0] = -10 + (-5) = -15.

Example 3

Input: arr1 = [1, 2, 3], arr2 = [4, 5, 6], target = 20
Output: False
Explanation: The maximum possible sum is 3 + 6 = 9, so no pair can sum to 20.

Edge Cases

• Either arr1 or arr2 is empty (should return False).
• Extreme values near INT64_MAX or INT64_MIN where directly computing arr1[i] + arr2[j] would overflow a 64-bit signed integer.
• Duplicate values in either array.