167. Two Sum

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)
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(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.