Logic: The approach to this question differs to that of the classic Two Sum problem in that we have some direction with how we want to search for our target.
Since the array is sorted, we can make some general observations:
Smaller sums would come from the left half of the array Larger sums would come from the right half of the array Therefore, using two pointers starting at the end points of the array, we can choose to increase or decrease our current sum however we like. Pay attention to the example below:
The basic idea is that: If our current sum is too small, move closer to the right. If our current sum is too large, move closer to the left.
That's really all there is to it! Since the array is sorted and we're guarranteed that there exists an answer, we have everything we need to start coding :)
How would I come up with this during an interview? In an interview, whenever you're given a question where the input array is sorted, here are some super useful things to consider:
- Binary Search
- Two (or three) pointers
- A sliding window
- Traversing from the right
Make sure to write down a couple examples and try experimenting with these approaches. Even understanding that these approaches may aid in finding an answer with a sorted array, you're showing your interviewer that you have a good understanding of the array datastructure. Be mindful of negative values and duplicates as you're experimenting!
Code:
# @param {Integer[]} numbers
# @param {Integer} target
# @return {Integer[]}
def two_sum(numbers, target)
left = 0 # left pointer
right = numbers.size - 1 # right pointer
while numbers[left] + numbers[right] != target
if numbers[left] + numbers[right] > target
right -= 1
else
left += 1
end
end
[left + 1, right + 1]
end
=begin
few test cases
[2,7,11,15]
9
[2,3,4]
6
[-1,0]
-1
[5,25,75]
100
=endTime Complexity: O(n)
Space Complexity: O(1)