1. Two Sum

read.md

Two Sum

Question on Leetcode - Easy

Approach

There were three approaches taken to solve this question.

1. Use of two for-loops.
2. I call it the x = z - y (from the equation x + y = z).
3. Two pointer approach.

The two pointer approach was the approach used. In this approach, the array is first sortted from the lowest to the highest number. Then, two pointers are placed at the extremes of the array. In a while loop (left < right), the current sum will be taken and be compared to the target number. If this number isn't the current number, the following would happen:

• If the current number obtained is less than the target, the left pointer will be moved by one step to the right.
• If the current number obtained is more than the target, the right pointer will be moved by one step to the left.

In the end, the indexes of the numbers making up the target will be returned. If a match isn't gotten, an empty array will be returned.

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums.sort()
        left, right = 0, len(nums) - 1
        while left < right:
            curr = nums[left] + nums[right]
            if curr == target:
                return [left, right]
            elif curr < target:
                left += 1
            elif curr > target:
                right -= 1
        return []

Complexity

• Time complexity: O(nlogn) because of the sorting.
• Space complexity: O(1). A constant space is used.