Two Sum

Difficulty: Easy | Acceptance: 56.20% | Paid: No

Topics: Array, Hash Table

• Examples
• Constraints
• Brute Force
• Hash Map
• Two Pointers

Examples

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]

Constraints

- 2 <= nums.length <= 10^4 
- -10^9 <= nums[i] <= 10^9 
- -10^9 <= target <= 10^9 
- Only one valid answer exists. 

Brute Force

Intuition

Check every pair of elements to see if they sum to the target.

Steps

• Iterate through each element in the array.
• For each element, iterate through the rest of the array to find a complement that sums to the target.
• Return the indices of the two elements that sum to the target.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Complexity

• Time: O(n^2)
• Space: O(1)
• Notes: This approach checks all possible pairs which leads to quadratic time complexity.

Hash Map

Intuition

Use a hash map to store elements and their indices for faster lookup.

Steps

• Iterate through the array once.
• For each element, calculate its complement (target - element).
• Check if the complement exists in the hash map.
• If it does, return the current index and the index of the complement.
• If not, store the current element and its index in the hash map.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashmap = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hashmap:
            return [hashmap[complement], i]
        hashmap[num] = i
    return []

Complexity

• Time: O(n)
• Space: O(n)
• Notes: This approach uses extra space for the hash map but reduces time complexity to linear.

Two Pointers

Intuition

Sort the array and use two pointers from both ends to find the target sum.

Steps

• Create a list of pairs (value, original_index) to keep track of original indices.
• Sort this list based on values.
• Use two pointers, one at the start and one at the end of the sorted list.
• Adjust pointers based on whether the current sum is less than or greater than the target.
• When the sum matches the target, return the original indices.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    indexed_nums = [(num, i) for i, num in enumerate(nums)]
    indexed_nums.sort()
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = indexed_nums[left][0] + indexed_nums[right][0]
        if current_sum == target:
            return [indexed_nums[left][1], indexed_nums[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: This approach sorts the array which takes O(n log n) time. Space is used to store the indexed pairs.