Decide two pointers versus a hash set
Updated
Hash when order is useless and you need membership or complements in one unsorted pass. Two pointers when the arrays are sorted (or you will sort), or when you compact in place, or when extra space must be O(1).
What to focus on
Unsorted two-sum → hash. Sorted two-sum or merge/intersect of two sorted arrays → pointers. Need original indices after a sort → hash, or sort (value, i) pairs. Unsorted input is in play because that is the choice.
Worked examples
hash
a = [4, 1, 9], t=10 unsorted two-sum- complements 6, 9, 1
- seen set hits 1 at 9
Result: hash, O(n) extra
pointers
a = [1, 4, 9], b = [4, 7, 9], intersect- both sorted
- no set
Result: two pointers
either
a = [4, 1, 9], t=10, may sort- sort to [1, 4, 9] then L,R
- or hash without sorting
Result: pointers if O(1) extra, hash if O(n) time
Try it
Write classify(a). a is an array of integers, sorted or not. Hash for unsorted membership. Two pointers for sorted arrays or O(1) extra. Print hash or two pointers and why. Return nothing. For a = [4, 1, 9] t=10, a = [1, 4, 9] vs b = [4, 7, 9] intersect, and the same two-sum after sorting.
a has length ≥ 2. A target pair exists. b is sorted when intersecting.