2-Array 2-Sum

You are given two non-empty arrays of integers, sorted_arr and unsorted_arr. The first one is sorted, but the second is not. The goal is to find one element from each array with sum 0. If you can find them, return an array with their indices, starting with the element in sorted_arr. Otherwise, return [-1, -1]. Use O(1) extra space and do not modify the input.

Example:

  • Input: sorted_arr = [-5, -4, -1, 4, 6, 6, 7], unsorted_arr = [-3, 7, 18, 4, 6]
  • Output: [1, 3] (We can use -4 from the sorted array and 4 from the unsorted array)
1def twoArrayTwoSum(sorted_arr: List[int], unsorted_arr: List[int]) -> List[int]:
2    def binary_search(arr, target):
3        l, r = 0, len(arr) - 1
4        while l <= r:
5            mid = (l + r) // 2
6            if arr[mid] == target: return mid
7            elif arr[mid] < target: l = mid + 1
8            else: r = mid - 1
9        return -1
10

11    for i, val in enumerate(unsorted_arr):
12        target = -val
13        idx = binary_search(sorted_arr, target)
14        if idx != -1:
15            return [idx, i]
16    return [-1, -1]
Previous
Valley Bottom
Next
Target Count Divisible By K
l
-5
0
-4
1
-1
2
4
3
6
4
6
5
r
7
6
target=3
unsortedVal=-3
Step 1 / 7
Step 1:
Iterate unsorted_arr. Val = -3. Target = 3. Search 3 in sorted_arr.
Pointers: l=0, r=6
Focus: default
target=3unsortedVal=-3