# Links

Go to my solution

Go to the question on LeetCode

# My Thoughts

**What I Learned**

I learned how to complete the two sum question with the best time and space complexity.

**Comments**

Unfortunately, questions like this make me feel unaccomplished because seeing far better complexities makes it feel like I could’ve done better. But in this question, you have to choose between one or the other, and it is impossible to simultaneously rank in the 100% for both.

# Data Structure Description

**Hash Map/Dictionary -** A data structure that stores a collection of keys, each mapped to their respective values. Each key may only appear once.

**Enumerate -** A function that takes in a list and returns a generator that outputs the appropriate (index, element at index) tuple as it is iterated. It yields after every iteration meaning it only stores one element at a time making it O(1) space complexity.

**Visual Examples**

A visual showing the tuples within an enumerate generator, click to view

# Fast Solution Statistics

**Time Complexity**

O(n) - In the worst case, we must iterate through n-1 elements in the list, resulting in the O(n) time complexity since we ignore the addition/subtraction of n by constants.

**Space Complexity**

O(n) - In the worst case, we must store n-1 elements in the dictionary, resulting in the O(n) space complexity since we ignore the addition/subtraction of n by constants.

**Runtime Beats**

100% of other submissions

**Memory Beats**

56.20% of other sumbissions

# Fast Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# (key) number : (value) index
solu = {}
# enumerate returns one element at a time as needed
# in tuples representing the (index, element at index)
# this way, we can squeeze out a bit more space complexity
for i, n in enumerate(nums):
# n + target-n = target
# using this formula, we can search the dictionary to see if
# target-n exists in the dictionary
if target-n in solu:
# If it does, then return its index and the current numbers
return[solu[target-n],i]
# If the solution has not been found, insert n into the dict.
solu[n] = i

# Compact Solution Statistics

**Time Complexity**

O(n^{2}) - We perform an O(n) operation within a for loop, O(n), resulting in the O(n^{2}) time complexity.

**Space Complexity**

O(1) - We will, at most, store two extra values, and that number is independent of n, resulting in the O(1) space complexity.

**Runtime Beats**

33.10% of other submissions

**Memory Beats**

100% of other sumbissions

# Compact Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)): # O(n)
for j in range(i+1,len(nums)): # O(n)
if nums[i] + nums[j] == target:
return [i,j]
'''Enumerator solution
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for index1, num1 in enumerate(nums):
for index2, num2 in enumerate(nums):
if index2 <= index1:
continue
elif target - num1 == num2:
return [index1,index2]
'''