Algorithm I Day 3 Two Pointers 167. Two Sum II - Input Array is Sorted

day-3-two-pointers-167-two_sum_ii_input_array_is_sorted.md

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

=end

Time Complexity: O(n) Space Complexity: O(1)

Source