Leetcode 1 - Two Sum
Explanation for Leetcode 1 - Two Sum problem, and its solution in Python.
Problem
Example:
1
2
3
4
5
6
7
8
9
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]
Approach
Brute force approach is to check every possible pair of numbers in the list and return the indices if the sum of the pair equals to the target. However, this approach has O(n^2) time complexity, as we need to check every possible pair.
A better approach is to check for complement of each number and we can do this by using a hash map to store the number and its index. Then, we can iterate through the list and check if the complement of the current number exists in the hash map. If it does, we return the indices of the current number and its complement.
Visual representation of the approach:
1
2
3
4
5
6
nums = [2,7,11,15], target = 9
hash_map = {}, complement = 9 - 2 = 7
complement 7 is not in hash_map, so we add 2 to hash_map with its index,
hash_map = {2: 0}, complement = 9 - 7 = 2
complement 2 is in hash_map, so we return [0, 1]
Here’s the code implementation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# initialize hash map
hash_map = {}
# iterate through the list
for i, n in enumerate(nums):
complement = target - n
if complement in hash_map:
return [hash_map[complement], i]
hash_map[n] = i
# if no solution is found, return an empty list
return []
Time Complexity and Space Complexity
The time complexity is $ O(n) $ since we’re iterating through the list once and checking for complement in the hash map.
The space complexity is $ O(n) $ since we’re using a hash map to store the numbers and their indices.