# Problem

- Given an array of integers that is already
**sorted in ascending order**, find two numbers such that they add up to a specific target number.

- The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

- Note:

- Your returned answers (both index1 and index2) are not zero-based.

- You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

# Thought Process

- create two pointers: head=0 and tail=n-1
- since the array is already sorted, start with sum = nums[head] + nums[tail]
- if sum == target, return head+1, tail+1 (since not zero based)
- if sum < target, move head up, head
~~= 1, new sum = nums[head]~~nums[tail] - if sum > target, move tail down, tail -= 1, new sum = nums[head] + nums[tail]
- since we cannot use the same element twice, if head == tail, break loop and return false if the target is not found

# White Board

Below is the white board:

# Code

```
class Solution:
def two_sum(self, nums, target):
i, j = 0, len(nums) - 1
while i < j:
sum = nums[i] + nums[j]
if sum == target:
return (i+1, j+1)
elif sum < target:
i += 1
else:
j -= 1
return False
def test_two_sum():
import random
random.seed(42)
nums = random.sample(range(1, 100), 20)
print("Original Array: ")
print(nums)
nums = sorted(nums)
print("Sorted Array: ")
print(nums)
target = random.sample(range(1,100),1)[0]
print("Target: ", target)
ts = Solution().two_sum(nums, target)
print("Solution: ")
print(ts)
test_two_sum()
```

Original Array: [82, 15, 4, 95, 36, 32, 29, 18, 14, 87, 70, 12, 76, 55, 5, 28, 30, 65, 78, 72] Sorted Array: [4, 5, 12, 14, 15, 18, 28, 29, 30, 32, 36, 55, 65, 70, 72, 76, 78, 82, 87, 95] Target: 26 Solution: (3, 4)

# Complexity

- Time complexity is O(log(n)), two pointers loop from head and tail at the same time
- Space complexity is O(1), as I didn't create new spaces

# Optimization

I think what I provided is the optimal solution. I took advantage of the property that the array is already sorted. No need to optimize for the sake of optimizing.