- 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.
- 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.
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.
- 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
Below is the white board:
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)
- 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
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.