willwangcc

# Time: O(N) where N is the number of keys in the input dictionary 
# Space: O(N) since the ouput dict is asymptotically as big as the input dict

def flatten_dictionary(dictionary):
  pass # your code goes here
  flat_dict = {}
  flat_dict_helper("", dictionary, flat_dict)
  return flat_dict

def flat_dict_helper(inital_key, dictionary, flat_dict):

willwangcc

# Time: O(N log(N))
# Space: O(1)

'''
[2, 100, 50, 120, 1000] newBudget = 190 
1000, 120, 100, 50, 2, 0
120, 120, 100, 50, 2, 0
100, 100, 100, 50, 2, 0
50, 50, 50, 50, 2, 0
2, 2, 2, 2, 2, 0

willwangcc

# 349. Intersection of Two Arrays
# Time: O(n)
# Space: O(n)

'''
             i
[1, 1, 2, 2, 3, 5]
[2, 2, 5]
       j
'''

willwangcc

# Time:  O(E+nlogn), where E is the length of flights
# Space: O(n), the size of the heap 
# Reference: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/

'''
# Dijkstra's algorithm 
If we continually extend our potential flightpaths in order of cost, we know once we've reached the destination dst that it was the lowest cost way to get there. 
'''
import collections
class Solution(object):

willwangcc

# Time: O(E∗K), where E is the length of flights.
# Space: O(n), the space used to store cur and pre
# Reference: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/


# Bellman-ford algorithm
class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, K):
        """
        :type n: int

willwangcc

class Solution(object):
    def racecar(self, target):
        """
        :type target: int
        :rtype: int
        """
        curstep = set([])
        curstep.add((0,1))
        allstep = set([])
        allstep.add((0,1))

willwangcc

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


# Before vs After 

#####################################
## Before
#####################################
 

willwangcc

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


# Before vs After 

#####################################
## Before
#####################################
 

willwangcc

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


# Before vs After 

#####################################
## After
#####################################
 

willwangcc

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


# Before vs After 

#####################################
## After
#####################################