Day 5. two sum with two pointers

Problem Set

167. Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

first attempt

• use two pointers
• increment both from left side
• rightP is always same or bigger than leftP+1
• when I can't find matching rightP for the target, increase the leftP+1 and update rightP starting value as well (rightP = leftP + 1)

Pseudo code

1. leftP = 0, rightP = leftP+1
2. first loop: leftP increments from 0 to numbers.length - 2
3. for each leftP, find rightP from the rest of the array. 
4. second loop: rightP starts from leftP+1, and checks until the end of array. 
5. if sum = target, return
6. if sum != target, keep increasing rightP
7. if you don't find any, increase leftP++ and repeat another round.

Problem

• time limit exceeded
• it is inefficient. almost like a double for loop.

Solution

• How to make a better use of two pointers?
• Use non-decreasing order array wisely
• It means smaller value is on left, bigger value is on right
• Let's start pointers from the other ends, not adjacent (next to each other)
• We can check the sum of two pointers and compare with the target

1. if sum > target, the sum has to decrease. So move the rightP(bigger value positions) to left(--)
2. if sum < target, the sum has to increase. So move the leftP(smaller value positions) to right(++)

• This reduces the amount of pointers movement and loops very significantly.

Helpful links

• https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/solutions/2128501/two-pointers-visual-explanation-java/?envType=study-plan&id=algorithm-i

Relevant problem sets

653. Two Sum IV - Input is a BST
1099. Two Sum Less Than K