1. Two Sum

• Difficulty: easy
• LeetCode: https://leetcode.com/problems/two-sum/
• Topics: Array, Hash Table

Solutions

Language	Approach	Time	Space	File
python	Map	O(n)	O(n)	python/map_solution.py

Map — python

Time: O(n)
Space: O(n)

python/map_solution.py

# Time: O(n)
# Space: O(n)

from typing import List

from task import Task


class MapSolution(Task):
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = dict()
        for i, num in enumerate(nums):
            if num in seen:
                return [seen[num], i]
            seen[target - num] = i
        raise ValueError('No solution')

Traces

Map

Map trace

Step 1

tar: 11
idx: 0 1 2 3
val: 2 4 7 8
   ^
map: []

Step 2

tar: 11
idx: 0 1 2 3
val: 2 4 7 8
     ^
map: 9=0

Step 3

tar: 11
idx: 0 1 2 3
val: 2 4 7 8
       ^
map: 9=0 7=1

Step 4

tar: 11
idx: 0 1 2 3
val: 2 4 7 8
         ^
map: 9=0 7=1
output: 1 2