TwoSum (Two Pointers Way)

Same problem with TwoSum (HashTable way). This is more beneficial given that the array is sorted.

Problem

Problem: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

Solution

For this one we apply the concept of Two pointers. In which we have a left and right in a sorted array.

We move:

• left++ if the sum is too small. The reason why is because nums[left] is in the smaller side and thus moving up will bring the sum bigger.
• right-- if the sum is too big. For the same reason, nums[right] is in the bigger side therefore result into the sum smaller.

class App():
    def twoSumSorted(self, arr: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while numbers[left] + numbers[right] != target:
            if (numbers[left] + numbers[right] > target):
                right -= 1
            else: 
                left += 1
        
        return [left + 1, right + 1]

Time Complexity: $O(nlogn)$

• Sorting is $O(nlogn)$
• Traversing 2 pointers is $O(n)$
  Space Complexity: $O(1)$

[!danger]
Note that for this, we required that the array has to be sorted in the question. If it's not sorted in the question and we sort outselves, we might adjust the index