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