0001. Two Sum

Problem Category:: Array, Hash table Neetcode Category:: Arrays and Hashing

https://leetcode.com/problems/two-sum/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

Optimal

Dictionary

We want to maintain a mapping of each element to its index, and require quick lookup - therefore a Hash table based data structure should be used (e.g.: Dictionary)

Python implementation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {} # Uses hash table - num as key, index as value
        for idx in range(len(nums)):
            complement = target - nums[idx]
            if complement in dic: # Searches keys
                return [idx, dic[complement]] # Index of the compliment is stored as dict value
            else:
                dic[nums[idx]] = idx # Store in dict, key is the num, value is index

• Time complexity: $O(n)$ - one traversal, $O(1)$ average lookups
• Space complexity: $O(n)$ - dictionary

Others

Brute force

$O(n^2)$ nested for loop to check all

Python implementation

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

Notes

• Sorting the list, even when keeping track of the original indices, doesn’t help us improve from $O(n^2)$ as the two numbers that sum to target are not necessarily adjacent to each other when sorted