1. Data Structure and Algorithms (DSA)

# O(n) time | O(n) space
def twoNumberSum(array, targetSum):
    avail = set()
    for i,v in enumerate(array):
        if targetSum-v in avail:
            return [targetSum-v,v]
        else:
            avail.add(v)
    return []
    pass

# O(nlog(n)) time | O(1) space
def twoNumberSum(array, targetSum):
    array.sort()
    n = len(array)
    left = 0
    right = n-1
    while left<right:
        currSum = array[left]+array[right]
        if currSum==targetSum: return [array[left], array[right]]
        elif currSum<targetSum: left+=1
        elif currSum>targetSum: right-=1
    return []
    pass

# O(n^2) time | O(1) space
def twoNumberSum(array, targetSum):
    n = len(array)
    for i in range(n-1):
        for j in range(i+1,n):
            if array[i]+array[j] == targetSum:
                return [array[i],array[j]]
    return []
    pass

# O(n) time | O(1) space - where n is the length of the array
def isValidSubsequence(array, sequence):
    pArray = pSequence = 0
    while pArray < len(array) and pSequence < len(sequence):
        if array[pArray] == sequence[pSequence]:
            pArray+=1
            pSequence+=1
        else: pArray+=1
    return pSequence == len(sequence)
    pass

# O(n) time | O(n) space
def getNthFib(n):
    dp = [0,1]
    while len(dp)<n:
        dp.append(dp[-1]+dp[-2])
    return dp[n-1]
    pass

# O(n) time | O(1) space
def getNthFib(n):
    last_two = [0,1]
    count = 2
    while count < n:
        currFib = last_two[0] + last_two[1]
        last_two[0] = last_two[1]
        last_two[1] = currFib
        count += 1
    return last_two[1] if n>1 else last_two[0]
    pass

# O(n) time | O(d) space - where n is the total number of elements in the array,
# including sub-elements, and d is the greatest depth of "special" arrays in the array
def productSum(array, depth = 1):
    sum = 0
    for i,v in enumerate(array):
        if type(v) is list:
            sum += productSum(v, depth + 1)
        else:
            sum += v
    return sum*depth
    pass

# Count the frequency of each word, and 
# sort the words with a custom ordering relation 
# that uses these frequencies. Then take the best k of them.

# Time Complexity: O(N \log{N})O(NlogN), where NN is the length of words. 
# We count the frequency of each word in O(N)O(N) time, 
# then we sort the given words in O(N \log{N})O(NlogN) time.
# Space Complexity: O(N)O(N), the space used to store our uniqueWords.
def topKFrequentWords(words, k)-> List[str]:
    from collections import Counter
    wordsFreq = Counter(words)
    uniqueWords = list(wordsFreq.keys())
    uniqueWords.sort(key = lambda x: (-wordsFreq[x], x))
    return uniqueWords[:k]

# Time Complexity: O(N \log{k})O(Nlogk), where NN is the length of words. 
# We count the frequency of each word in O(N)O(N) time, then we add NN words to the heap, 
# each in O(\log {k})O(logk) time. Finally, we pop from the heap up to kk times. 
# As k \leq Nk≤N, this is O(N \log{k})O(Nlogk) in total.

# In Python, we improve this to O(N + k \log {N})O(N+klogN): our heapq.heapify operation and 
# counting operations are O(N)O(N), and 
# each of kk heapq.heappop operations are O(\log {N})O(logN).

# Space Complexity: O(N)O(N), the space used to store our wordsFreq.

# Count the frequency of each word, then add it to heap that stores the best k candidates. 
# Here, "best" is defined with our custom ordering relation, 
# which puts the worst candidates at the top of the heap. 
# At the end, we pop off the heap up to k times and reverse the result 
# so that the best candidates are first.

# In Python, we instead use heapq.heapify, which can turn a list into a heap in linear time, 
# simplifying our work.

def topKFrequentWords(words, k)-> List[str]:
    from heapq import heapify, heappop#, heappush
    from collections import Counter
    wordsFreq = Counter(words)
    heap = [(-freq, word) for word, freq in wordsFreq.items()]
    heapq.heapify(heap)
    return [heapq.heappop(heap)[1] for _ in range(k)]