Two Sum

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

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²) - We perform an O(n) operation within a for loop, O(n), resulting in the O(n²) 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

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]
'''