Sorting then two pointers versus a hash
Updated
Unsorted two-sum: hash complements in O(n) time O(n) extra, or sort then inward pointers in O(n log n) time O(1) extra (plus sort stack). Sorted input already: just the pointers, O(n) time O(1) extra.
What to focus on
Need original indices: hash, or sort (value, index) pairs. Need O(1) extra and mutation/sort allowed: sort + pointers. Intersection of two sorted arrays: pointers, not a hash. Unsorted input is in play because that is the choice.
Worked examples
hash
a = [4, 1, 9], t=10- see 4 need 6
- see 1 need 9
- see 9 have 1
Result: hit, O(n) time O(n) extra
sort then pointers
a = [4, 1, 9], t=10, sort to [1, 4, 9]- sort O(n log n)
- L=0 R=2, 1+9=10 hit
- two ints extra
Result: hit, O(n log n) time O(1) extra
already sorted
a = [1, 4, 9], b = [4, 7, 9], intersect- pointers emit 4, 9
- no hash
Result: O(n+m) time O(1) extra
Try it
Write twoSum(a, t). a is an array of integers, sorted or not. t is the pair sum. L and R are indices after a sort, or a hash stores complements. Run hash two-sum and sort+pointers. Print time and extra space of each. Then intersect [1, 4, 9] with [4, 7, 9] using pointers. For a = [4, 1, 9] t=10, and for a = [1, 4, 9], b = [4, 7, 9] intersect.
a has length ≥ 2. A target pair exists. b is sorted when intersecting.