Leetcode, Data structure and Algorithm

<<imports for typing>>

def decompress_RLE_list(nums: List[int]) -> List[int]:
    res = []
    for i in range(0, len(nums), 2):
        sub_lst = [nums[i+1] for j in range(nums[i])]
        res = res+sub_lst
    return res
print(decompress_RLE_list([1,1,2,3]))

[1, 3, 3]

lst1=[1,2,3]
lst2=[3,3,3]
print(lst1+lst2)

[1, 2, 3, 3, 3, 3]

<<imports for typing>>

def find_numbers(nums: List[int]) -> int:
    res = 0
    for ele in nums:
        if len(str(ele)) % 2 == 0:
            res += 1
    return res
print(find_numbers([1,2,3]))
print(find_numbers([11,2,3]))

0
1

<<imports for typing>>

def smaller_numbers_than_current(nums: List[int]) -> List[int]:
    import math
    sorted_nums = sorted(nums)

    smaller_counts = {}
    for i, e in enumerate(sorted_nums):
        smaller_counts[e] = min(smaller_counts.get(e, math.inf), i)

    res = []
    for num in nums:
        res.append(smaller_counts[num])

    return res
print(smaller_numbers_than_current([2,2,3,4,1]))

[1, 1, 3, 4, 0]

<<imports for typing>>

def process_queries(queries: List[int], m: int) -> List[int]:
    res = []

    p = list(range(1, m+1))
    p_copy = p.copy()
    for i, e in enumerate(queries):
        p_copy = p.copy()
        for j, e_p in enumerate(p_copy):
            if e_p == e:
                p.pop(j)
                p.insert(0, e_p)
                res.append(j)

    return res

print(process_queries([3,1,2,1],5))

[2, 1, 2, 1]

<<imports for typing>>

def process_queries(queries: List[int], m: int) -> List[int]:
    # the original code uses
    # def process(arr, idx), which is quite confusing
    # as we are trying to find the idx of an element
    def process(arr, elem):
        ans = arr.index(elem)
        arr.insert(0, arr.pop(ans))
        return ans

    m = [x for x in range(1, m+1)]
    return [process(m, i) for i in queries]

print(process_queries([3,1,2,1],5))

[2, 1, 2, 1]

<<imports for typing>>

def diagonal_sort(mat: List[List[int]]) -> List[List[int]]:
    import itertools

    m = len(mat)
    n = len(mat[0])
    res = [[None for i in range(n)] for j in range(m)]
    sorted_lst = sorted(itertools.chain(*mat))

    cur_col = 0
    cur_row = 0

    idx = 0
    while cur_col < n or cur_row < m:
        if cur_col < n:
            for moving_col in range(cur_col, n):
                res[cur_row][moving_col] = sorted_lst[idx]
                idx += 1

            # cur_row+1 so that it does not overwrite
            # the first data in the column
        if cur_row < m:
            for moving_row in range(cur_row+1, m):
                res[moving_row][cur_col] = sorted_lst[idx]
                idx += 1

        cur_col = min(n-1, cur_col+1)
        cur_row = min(m-1, cur_row+1)
        if cur_col == n-1 and cur_row == m-1 and res[m-1][n-1] is not None:
            break
    return res
#print(diagonal_sort([[2,1],[3,2],[3,2]]))
#print(diagonal_sort([[1,2,1],[3,2,4],[7,7,4]]))
#print(diagonal_sort([[3,3,1,1],[2,2,1,2],[1,1,1,2]]))
print(diagonal_sort(
    [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
))

[[1, 4, 5, 7, 8, 11], [11, 22, 23, 25, 25, 27], [14, 28, 36, 44, 45, 50], [15, 31, 52, 58, 66, 68], [17, 33, 55, 69, 75, 84]]

<<imports for typing>>

def diagonal_sort(mat: List[List[int]]) -> List[List[int]]:
    n = len(mat)
    m = len(mat[0])

    def sort_list(head: Tuple[int]) -> None:
        res = []
        x, y = head
        while x < n and y < m:
            res.append(mat[x][y])
            x+=1
            y+=1

        res.sort()
        res = iter(res)
        x, y = head
        while x < n and y < m:
            mat[x][y] = next(res)
            x+=1
            y+=1

    diagonal_heads = [(x, y) for x in range(n) for y in range(m)]

    for head in diagonal_heads:
        sort_list(head)
        
    return mat
print(diagonal_sort([[4,2,3],[1,3,4]]))
print(diagonal_sort([[2,1],[3,2],[3,2]]))
print(diagonal_sort([[1,2,1],[3,2,4],[7,7,4]]))
print(diagonal_sort([[3,3,1,1],[2,2,1,2],[1,1,1,2]]))
print(diagonal_sort(
    [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
))

[[3, 2, 3], [1, 4, 4]]
[[2, 1], [2, 2], [3, 3]]
[[1, 2, 1], [3, 2, 4], [7, 7, 4]]
[[1, 1, 1, 1], [1, 2, 2, 2], [1, 2, 3, 3]]
[[5, 17, 4, 1, 52, 7], [11, 11, 25, 45, 8, 69], [14, 23, 25, 44, 58, 15], [22, 27, 31, 36, 50, 66], [84, 28, 75, 33, 55, 68]]

def diagonal_sort(mat):
    m, n = len(mat), len(mat[0])

    def sort(i, j):
        ij = zip(range(i, m), range(j, n))
        vals = iter(sorted(mat[i][j] for i, j in ij))
        for i, j in ij:
            mat[i][j] = next(vals)

    for i in range(m): sort(i, 0)
    for j in range(m): sort(0, j)

    return mat

print(diagonal_sort([[4,2,3],[1,3,4]]))
print(diagonal_sort([[2,1],[3,2],[3,2]]))
print(diagonal_sort([[1,2,1],[3,2,4],[7,7,4]]))
print(diagonal_sort([[3,3,1,1],[2,2,1,2],[1,1,1,2]]))
print(diagonal_sort(
    [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
))

[[4, 2, 3], [1, 3, 4]]
[[2, 1], [3, 2], [3, 2]]
[[1, 2, 1], [3, 2, 4], [7, 7, 4]]
[[3, 3, 1, 1], [2, 2, 1, 2], [1, 1, 1, 2]]
[[11, 25, 66, 1, 69, 7], [23, 55, 17, 45, 15, 52], [75, 31, 36, 44, 58, 8], [22, 27, 33, 25, 68, 4], [84, 28, 14, 11, 5, 50]]

<<imports for typing>>
def num_teams(rating: List[int]) -> int:
    if len(rating) < 3:
        return 0

    from itertools import combinations

    count = 0
    for comb in combinations(rating, 3):
        if comb[0] < comb[1] < comb[2] or comb[0]>comb[1]>comb[2]:
            count += 1


    return count
print(num_teams([2,5,3,4,1]))
print(num_teams([2,1,3]))
print(num_teams([1,2,3,4]))
print(num_teams([0,1]))

3
0
4
0

<<imports for typing>>
def num_teams(rating: List[int]) -> int:
    ans = 0
    n = len(rating)

    biggerLeft, biggerRight = {}, {}

    for i in range(n-1):
        for j in range(i+1, n):
            if rating[i] < rating[j]:
                biggerRight[i] = biggerRight.get(i, 0) + 1
            elif rating[i] > rating[j]:
                biggerLeft[j] = biggerLeft.get(j, 0) + 1

    for i in range(n-1):
        for j in range(i+1, n):
            if rating[i] < rating[j]:
                ans += biggerRight.get(j, 0)
            elif rating[i] > rating[j]:
                ans += biggerLeft.get(i, 0)
    return ans
print(num_teams([2,5,3,4,1]))
print(num_teams([2,1,3]))
print(num_teams([1,2,3,4]))
print(num_teams([0,1]))

3
0
4
0

<<imports for typing>>

def calc_combinations(n: int, k: int) -> int:
    """
    n: total number of items
    k: number of items to be drawn
    """
    calculated = {}
    def factorial(n: int) -> int:
        if n == 0 or n == 1:
            return 1
        if n not in calculated.keys():
            calculated[n] = n * factorial(n-1)
        return calculated[n]

    if n < k :
        return 0
    return int(factorial(n)/factorial(k)/factorial(n-k))

def num_teams(rating: List[int], team_len: int = 3) -> int:
    ans = 0
    n = len(rating)

    biggerLeft, biggerRight = {}, {}

    for i in range(n-1):
        for j in range(i+1, n):
            if rating[i] < rating[j]:
                biggerRight[i] = biggerRight.get(i, 0) + 1
            elif rating[i] > rating[j]:
                biggerLeft[j] = biggerLeft.get(j, 0) + 1

    for i in range(n-1):
        for j in range(i+1, n):
            if rating[i] < rating[j]:
                # team_len-2 gives the remaining numbers that need to be drawn
                # from biggerRight.get(j, 0) given rating[i] and rating[j]
                ans += calc_combinations(biggerRight.get(j, 0), team_len-2)
            elif rating[i] > rating[j]:
                ans += calc_combinations(biggerLeft.get(i, 0), team_len-2)
    return ans
print(num_teams([2,7,8,9,10], 4))
print(num_teams([2,1,3]))
print(num_teams([1,2,3,4]))
print(num_teams([0,1]))

5
0
4
0

<<imports for typing>>

def find_duplicates(nums: List[int]) -> List[int]:
    res = []
    for n in nums:
        if nums[abs(n)-1] < 0:
            res.append(abs(n))
        else:
            nums[abs(n)-1] *= -1
    return res

print(find_duplicates([1,2,3,3]))

[3]

<<imports for typing>>

<<imports for typing>>

def subsets(nums: List[int]) -> List[List[int]]:
    from itertools import combinations, chain

    res = [combinations(nums, i) for i in range(1, len(nums) + 1)]
    return list(map(list, chain(*res))) + [[]]
print(subsets([1,2,3]))

[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3], []]

<<imports for typing>>

def subsets(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    output = []

    # nth_bit = "1000"
    nth_bit = 1<<n
    for i in range(2**n):
        # generate bit mask, from 0..00 to 1..11
        bitmask = bin(i | nth_bit)[3:]
        # append subset corresponding to that bit mask
        output.append([nums[j] for j in range(n) if bitmask[j] == '1'])

    return output
print(subsets([1,2,3]))

0b1000
000
0b1001
001
0b1010
010
0b1011
011
0b1100
100
0b1101
101
0b1110
110
0b1111
111
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

<<imports for typing>>

def rotate(matrix: List[List[int]]) -> None:
    import math
    n = len(matrix)
    def rotate_square(mat: List[List[int]], coor: Tuple[int]) -> None:
        row, col = coor
        target_val = mat[col][n-1-row]
        mat[col][n-1-row] = mat[row][col]

        row, col = col, n-1-row
        temp = mat[col][n-1-row]
        mat[col][n-1-row] = target_val

        row, col = col, n-1-row
        target_val = mat[col][n-1-row]
        mat[col][n-1-row] = temp

        row, col = col, n-1-row
        mat[col][n-1-row] = target_val

    for cur_row in range(math.ceil(n/2)):
        for cur_col in range(cur_row, n-cur_row-1):
            rotate_square(matrix, (cur_row, cur_col))

    print(matrix)

rotate([[1,2],[3,4]])
rotate([[1,2,3],[4,5,6],[7,8,9]])
rotate([[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]])

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

<<imports for typing>>

matrix[i][j], matrix[j][n - 1 - i], matrix[n - 1 - i][n - 1 - j], matrix[n - 1 - j][i] 
= matrix[n - 1 - j][i], matrix[i][j], matrix[j][n - 1 - i], matrix[n - 1 - i][n - 1 - j]

<<imports for typing>>

def min_distance(word1: str, word2: str) -> int:
    m = len(word1)
    n = len(word2)

    if m == 0:
        return n
    if n == 0:
        return m

    tbl = [[0 for j in range(n+1)] for i in range(m+1)]

    for i in range(m+1):
        for j in range(n+1):
            if i == 0:
                tbl[i][j] = j
            elif j==0:
                tbl[i][j] = i
            elif word1[i-1] == word2[j-1]:
                tbl[i][j] = tbl[i-1][j-1]
            else:
                tbl[i][j] = 1 + min(
                    tbl[i-1][j],
                    tbl[i][j-1],
                    tbl[i-1][j-1]
                )

    return tbl[m][n]

<<imports for typing>>

<<imports for typing>>

def max_profit(prices: List[int]) -> int:

    max_p = 0

    price_map = {}
    for i, p in enumerate(prices):
        if p not in price_map.keys():
            price_map[p] = i

    prices.sort()

    for p_buy in prices:
        d_buy = price_map[p_buy]
        for p_sell in reversed(prices):
            d_sell = price_map[p_sell]
            if p_buy<p_sell and d_buy < d_sell:
                max_p = max(max_p, p_sell-p_buy)
                break

    return max_p
print(max_profit([7,1,5,3,6,4]))
print(max_profit([7,6,5]))
print(max_profit([1,4,1,4,3,1]))

5
0
3

<<imports for typing>>

def max_profit(prices: List[int]) -> int:
    from math import inf
    minprice = inf
    maxprofit = 0

    for i in range(len(prices)):
        if prices[i] < minprice:
            minprice = prices[i]
        elif prices[i] - minprice > maxprofit:
            maxprofit = prices[i] - minprice

    return maxprofit
print(max_profit([1,2,3,4,5]))

4

def max_profit(prices) -> int:
    from math import inf
    
    n = len(prices)
    dp = [[0, 0] for i in range(n+1)]

    # starting price
    dp[0][0] = inf

    for i in range(1, n+1):
        dp[i][0] = min(dp[i-1][0], prices[i-1])
        dp[i][1] = max(dp[i-1][1], prices[i-1]-dp[i-1][0])

    return dp[n][1]
print(max_profit([1,2,3,4,5]))

4

<<imports for typing>>

def max_subarray(nums: List[int]) -> int:
    from math import inf
    n = len(nums)
    if n == 1:
        return nums[0]

    # this is actualy not needed
    # see General thoughts
    dp = [0 for i in range(n+1)]
    dp[0] = -inf

    for i in range(1, n+1):
        dp[i] =max(nums[i-1], nums[i-1] + dp[i-1])

    return max(dp)
print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))
print(max_subarray([-2,1]))

6
1

<<imports for typing>>

<<imports for typing>>

def max_subarray(nums: List[int]) -> int:
    from math import inf
    n = len(nums)
    if n == 1:
        return nums[0]

    cur_sum = -inf
    best_sum = cur_sum

    for i in range(1, n+1):
        cur_sum =max(nums[i-1], nums[i-1] + cur_sum)
        best_sum = max(best_sum, cur_sum)

    return best_sum
print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))
#print(max_subarray([-2,1]))

6

<<imports for typing>>

def climb_stairs(n: int) -> int:
    dp = [0 for i in range(n+1)]

    dp[0], dp[1] = 1, 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
print(climb_stairs(4))

5

<<imports for typing>>

def climb_stairs(n: int) -> int:
    sqrt5=pow(5, 1/2)
    fibn = pow((1+sqrt5)/2, n+1)-pow((1-sqrt5)/2,n+1)
    return int(fibn/sqrt5)
print(climb_stairs(5))

8

<<imports for typing>>

def min_cost_climbing_stairs(cost: List[int]) -> int:
    from math import inf
    n = len(cost)
    min_cost = [inf for i in range(n)]

    min_cost[0], min_cost[1] = cost[0], cost[1]
    for i in range(2, n):
        min_cost[i] = min(min_cost[i-1], min_cost[i-2])+cost[i]

    return min(min_cost[n-1], min_cost[n-2])
print(min_cost_climbing_stairs([1, 100, 1,1,1,100,1,1,100,1]))

6

<<imports for typing>>

def min_cost_climbing_stairs(cost: List[int]):
    f1 = f2 = 0
    for x in reversed(cost):
        f1, f2=x+min(f1, f2), f1

    return min(f1, f2)
print(min_cost_climbing_stairs([10,14,10]))

14

<<imports for typing>>

def min_cost_climbing_stairs(cost: List[int]) -> int:
    from math import inf
    n = len(cost)

    mc1, mc2 = cost[0], cost[1]

    for i in range(2, n):
        mc1, mc2 = mc2, min(mc1, mc2)+cost[i]

    return min(mc1, mc2)
print(min_cost_climbing_stairs([1, 100, 1,1,1,100,1,1,100,1]))

6

<<imports for typing>>

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.nums = sorted(nums, reverse=True)

    def add(self, val: int) -> int:
        for i in range(len(self.nums)):
            if val > self.nums[i]:
                self.nums.insert(i, val)
                break

        else:
            self.nums.append(val)

        return self.nums[self.k-1]

k=3
arr=[4,5,8,2]
obj = KthLargest(k, arr)
print(obj.add(3))
print(obj.add(5))
print(obj.add(10))
print(obj.add(9))
print(obj.add(4))

4
5
5
8
8

<<imports for typing>>

import heapq
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.arr = []
        self.n = k
        for i in nums: self._push(i)

    def _push(self, val: int):
        if len(self.arr) == self.n:
            top = heapq.heappop(self.arr)
            if top > val:
                heapq.heappush(self.arr, top)
            else:
                heapq.heappush(self.arr, val)

        else:
            heapq.heappush(self.arr, val)

    def add(self, val: int) -> int:
        self._push(val)
        return self.arr[0] if len(self.arr) else None

nums = [10,9,8,7]
k=3
obj = KthLargest(k, nums)
val=6
param_1 = obj.add(val)
print(param_1)

8

<<imports for typing>>

class KthLargest:
    import heapq

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.arr = nums
        heapq.heapify(self.arr)
        self._chop_off_queue()

    def add(self, val: int) -> int:
        heap_top = 0

        # always keep heap size = k
        # Top element = kth largest element
        if len(self.arr) < self.k:
            heapq.heappush(self.arr, val)
        else:
            heapq.heappushpop(self.arr, val)

        return self.arr[heap_top]


    def _chop_off_queue(self):
        while len(self.arr) > self.k:
            # heappop() pops the smallest element
            heapq.heappop(self.arr)

<<imports for typing>>

def find_kth_largest(nums: List[int], k: int) -> int:
    return sorted(nums)[k-1]
print(find_kth_largest([3,2,1,5,6,4], 2))

2

<<imports for typing>>

import random

def kth_largest(arr: List[int], k: int) -> int:
    def partition(arr, lo, hi):
        pivot = arr[hi]
        i = lo

        for j in range(lo, hi):
            if arr[j] > pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1

        arr[i], arr[hi] = arr[hi], arr[i]
        return i
    
    def quickselect(arr: List[int],lo, hi, k) -> int:
        rand_pivot_idx = random.randrange(lo, hi+1)
        arr[hi], arr[rand_pivot_idx] = arr[rand_pivot_idx], arr[hi]
        par = partition(arr, lo, hi)
        
        if par == k - 1:
            return arr[par]
        elif par > k-1:
            return quickselect(arr, lo, par-1, k)
        return quickselect(arr, par+1, hi, k)
    
    return quickselect(arr, 0, len(arr)-1, k)

print(kth_largest([3,2,1,5,6,4], 3))

4

<<imports for typing>>

<<imports for typing>>

import heapq

def k_closest_points(points: List[List[int]], K: int) -> List[List[int]]:
    def get_distance(x, y) -> float:
        return (x**2+y**2)

    if len(points) == K:
        return points

    pq = []

    # this takes O(n)
    # because it is essentially heapify()
    for point in points:
        distance = get_distance(*point)
        heapq.heappush(pq, (distance, point))

    return [heapq.heappop(pq)[1] for i in range(K)]

print(k_closest_points([[1,3],[2,-2]], 2))
print(k_closest_points([[1,3],[2,-2], [2,-3]], 2))
print(k_closest_points([[3,3],[5,-1], [-2,4], [3,4]], 3))

[[1, 3], [2, -2]]
[[2, -2], [1, 3]]
[[3, 3], [-2, 4], [3, 4]]

<<imports for typing>>
class Solution(object):
    def kClosest(self, points, K):
        dist = lambda i: points[i][0]**2 + points[i][1]**2

        def sort(i, j, K):
            # Partially sorts A[i:j+1] so the first K elements are
            # the smallest K elements.
            if i >= j: return

            # Put random element as A[i] - this is the pivot
            k = random.randint(i, j)
            points[i], points[k] = points[k], points[i]

            mid = partition(i, j)
            if K < mid - i + 1:
                sort(i, mid - 1, K)
            elif K > mid - i + 1:
                sort(mid + 1, j, K - (mid - i + 1))

        def partition(i, j):
            # Partition by pivot A[i], returning an index mid
            # such that A[i] <= A[mid] <= A[j] for i < mid < j.
            oi = i
            pivot = dist(i)
            i += 1

            while True:
                while i < j and dist(i) < pivot:
                    i += 1
                while i <= j and dist(j) >= pivot:
                    j -= 1
                if i >= j: break
                points[i], points[j] = points[j], points[i]

            points[oi], points[j] = points[j], points[oi]
            return j

        sort(0, len(points) - 1, K)
        return points[:K]

<<imports for typing>>

def top_k_frequent(nums: List[int], k: int) -> List[int]:
    def partition(arr, low, high):
        pivot = arr[high]
        i = low
        for j in range(low, high):
            if arr[j][1] >= pivot[1]:
                arr[j], arr[i] = arr[i], arr[j]
                i += 1

        arr[i], arr[high] = arr[high], arr[i]
        return i

    def quickselect(arr, low, high, k: int) -> List[int]:

        par = partition(arr, low, high)

        if par == k-1:
            return arr[:k]
        elif par < k-1:
            return quickselect(arr, par+1, high, k)
        else:
            return quickselect(arr, low, par-1, k)
        
    temp = {}
    for i in nums:
        temp[i] = temp.get(i, 0) + 1
        arr = [(k, v) for k, v in temp.items()]
    return [i[0] for i in quickselect(arr, 0, len(arr)-1, k)]

print(top_k_frequent([1,1,1,2,2,3], 2))
print(top_k_frequent([1,1,1,2,2,3,3,3], 2))

[1, 2]
[1, 3]

<<imports for typing>>

def top_k_frequent(nums, k):
    from collections import Counter
    import heapq

    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

print(top_k_frequent([1,1,1,2,3,2], 2))

[1, 2]

from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    return [i[0] for i in count.most_common(k)]
print(top_k_frequent([1,2,1,1,24,2], 2))

[1, 2]

<<imports for typing>>

import collections
from datetime import datetime
import heapq

class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.users_tweets = collections.defaultdict(list)
        self.users_followers = collections.defaultdict(set)
        self.users_followees = collections.defaultdict(set)
        self.users_newsfeeds = collections.defaultdict(list)

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        # if this userId is new
        # ta must follow taself
        self.users_followees[userId].add(userId)
        self.users_followers[userId].add(userId)
        # add tweet to the userId
        tweet = datetime.now(tz=None), tweetId
        self.users_tweets[userId].append(tweet)
        # update newsfeeds of the followers
        for user in self.users_followers[userId]:
            heapq.heappush(self.users_newsfeeds[user], tweet)
            

    def getNewsFeed(self, userId: int) -> List[int]:
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        """

        num_total_tweets = len(self.users_newsfeeds[userId])
        num_tweets = 10 if num_total_tweets > 10 else num_total_tweets

        res = heapq.nlargest(num_tweets, self.users_newsfeeds[userId])

        return [i[1] for i in res]

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        # Only follow if followee is not followed by us
        if followeeId not in self.users_followees[followerId]:
            self.users_followees[followerId].add(followeeId)
            self.users_followers[followeeId].add(followerId)

            # get the tweets from new followee
            for tweet in self.users_tweets[followeeId]:
                heapq.heappush(self.users_newsfeeds[followerId], tweet)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        # Do not unfollow oneself
        if followeeId == followerId:
            return
        # Only unfollow if followee is followed by us
        if followeeId in self.users_followees[followerId]:

            # remove followee (unfollow)
            self.users_followees[followerId].remove(followeeId)
            # remove follower (unfollow)
            self.users_followers[followeeId].remove(followerId)
            # remove tweets from folowee
            for tweet in self.users_tweets[followeeId]:
                self.users_newsfeeds[followerId].remove(tweet)

            heapq.heapify(self.users_newsfeeds[followerId])
            

# Your Twitter object will be instantiated and called as such:
obj = Twitter()

obj.postTweet(1, 5)
param_2 = obj.getNewsFeed(1)
print(param_2)
obj.follow(1, 2)
param_2 = obj.getNewsFeed(1)
print(param_2)
obj.postTweet(2, 6)
param_2 = obj.getNewsFeed(1)
print(param_2)
obj.unfollow(1, 2)
param_2 = obj.getNewsFeed(1)
print(param_2)

[5]
[5]
[6, 5]
[5]

<<imports for typing>>

<<imports for typing>>

def swim_in_water(grid: List[List[int]]) -> int:
    n = len(grid)
    visited_pos : Set[Tuple[int]] = set()

    # row, col
    last_pos = (0, 0)
    visited_pos.add(last_pos)
    def avail_poses(last_pos: Tuple[int]) -> List[Tuple[int]]:
        res = []
        for row_offset in [-1, 0, 1]:
            for col_offset in [-1, 0, 1]:
                row = last_pos[0] + row_offset
                col = last_pos[1] + col_offset
                if 0 <= row < n and 0 <= col < n and (row, col) not in visited_pos and grid[row][col] <= t:
                    res.append((row, col))

        return res

    def swim(last_pos: Tuple[int]) -> Tuple[int]:
        ele = n+1
        return_pos = last_pos
        for pos in avail_poses(last_pos):
            if grid[pos[0]][pos[1]] <= ele:
                ele = grid[pos[0]][pos[1]]
                return_pos = pos
                
        return return_pos

    for t in range(0, n**2):
        print(t)
        last_pos = swim(last_pos)
        visited_pos.add(last_pos)
        print(last_pos)
        if last_pos == (n-1, n-1):
            return t

#print(swim_in_water([[0,2],[1,3]]))
print(swim_in_water([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]))

0
(0, 0)
1
(0, 1)
(0, 1)
2
(0, 2)
(0, 2)
3
(0, 3)
(0, 3)
4
(0, 4)
(0, 4)
5
(1, 4)
(1, 4)
6
(1, 4)
7
(1, 4)
8
(1, 4)
9
(1, 4)
10
(1, 4)
11
(1, 4)
12
(1, 4)
13
(1, 4)
14
(1, 4)
15
(2, 3)
(1, 4)
16
(2, 3)
(2, 4)
(1, 4)
17
(2, 3)
(2, 4)
(1, 4)
18
(2, 3)
(2, 4)
(1, 4)
19
(2, 3)
(2, 4)
(1, 4)
20
(2, 3)
(2, 4)
(1, 4)
21
(1, 3)
(2, 3)
(2, 4)
(1, 4)
22
(1, 3)
(2, 3)
(2, 4)
(1, 4)
23
(1, 3)
(2, 3)
(2, 4)
(1, 4)
24
(1, 3)
(2, 3)
(2, 4)
(1, 4)
None

<<imports for typing>>

def swim_in_water(grid: List[List[int]]) -> int:
    n = len(grid)

    # row, col
    last_pos = (0, 0)
    visited_poses = set()
    def avail_poses(last_pos: Tuple[int], cur_t: int) -> List[Tuple[int]]:
        offsets = (
            (-1, 0),
            (0, 1),
            (1, 0),
            (0, -1)
        )
        res = []

        for row_offset, col_offset in offsets:
            row = last_pos[0] + row_offset
            col = last_pos[1] + col_offset
            if 0 <= row < n and 0 <= col < n and (row, col) not in visited_poses and grid[row][col] <= cur_t:
                res.append((row, col))

        return res

    def swim(cur_pos: Tuple[int], cur_t: int) -> int:
        if cur_pos == (n-1, n-1):
            return cur_t

        while len(avail_poses(cur_pos, cur_t)) == 0:
            cur_t += 1

        print(cur_pos)
        print(cur_t)
        for pos in avail_poses(cur_pos, cur_t):
            visited_poses.add(pos)
            return swim(pos, cur_t)

    return swim(last_pos, 0)

print(swim_in_water([[0,2],[1,3]]))
#print(swim_in_water([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]))

(0, 0)
1
(1, 0)
1
(0, 0)
2
(0, 1)
3
3

<<imports for typing>>

from math import inf

def swim_in_water(grid: List[List[int]]) -> int:
    def adjacent_cells(pos: Tuple[int]) -> List[Tuple[int]]:
        offsets = (
            (-1, 0),
            (0, 1),
            (1, 0),
            (0, -1)
        )
        res = []

        for row_offset, col_offset in offsets:
            row = pos[0] + row_offset
            col = pos[1] + col_offset
            if 0 <= row < n and 0 <= col < n:
                res.append((row, col))
        return res

    n = len(grid)
    min_times = [[inf for i in range(n)] for j in range(n)]
    min_times[0][0] = 0

    for row in range(n):
        for col in range(n):
            if (row, col) != (0, 0):
                min_times[row][col] = min(
                    [abs(grid[row][col]-grid[adj_row][adj_col]) + min_times[adj_row][adj_col] for adj_row, adj_col in adjacent_cells((row, col))]
                )
                
    return min_times[n-1][n-1]

#print(swim_in_water([[0,2],[1,3]]))
print(swim_in_water([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]))

[[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [36, 33, 30, 27, 16], [37, 37, 34, 31, 20], [38, 39, 40, 41, 34]]

<<imports for typing>>

from math import inf

def swim_in_water(grid: List[List[int]]) -> int:
    def adjacent_cells(pos: Tuple[int]) -> List[Tuple[int]]:
        offsets = (
            (-1, 0),
            (0, 1),
            (1, 0),
            (0, -1)
        )
        res = []

        for row_offset, col_offset in offsets:
            row = pos[0] + row_offset
            col = pos[1] + col_offset
            if 0 <= row < n and 0 <= col < n:
                res.append((row, col))
        return res

    def min_distance(pos, dist):
        min_dist = inf
        min_index = None
        for row, col in adjacent_cells(pos):
            dist = abs(grid[row][col] - grid[pos[0]][pos[1]])
            if  (row, col) not in dist and dist < min_dist:
                min_dist = dist
                min_index = (row, col)

        return min_index
            

    n = len(grid)
    dist = dict()

    # The set of visited vertices
    visited = set()
    # The set of unvisited vertices
    unvisited = set()

    # set all other distances to infinity
    for row in range(n):
        for col in range(n):
            dist[(row, col)] = inf
            unvisited.add((row, col))

    dist = {(0, 0): 0}

    while len(unvisited) != 0:


    return dist[(n-1, n-1)]


#print(swim_in_water([[0,2],[1,3]]))
print(swim_in_water([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]))

<<imports for typing>>

import heapq

def swim_in_water(grid: List[List[int]]) -> int:
    visited, heap = set(), [(grid[0][0], 0, 0)]
    time, n = 0, len(grid)

    # The idea to use heap is that:
    # 1. It keeps a list of possible cells to take, and
    # 2. The cell with the minimum cost/elevation is stored at the top
    # 3. At the start of every iteration, every cell in the heap has been seen before,
    #    meaning that there is at least one path from (0, 0) to that cell

    # Intuitively, we always want to choose the cell with the minimum elevation.
    # 
    while heap:
        cur, x, y = heapq.heappop(heap)
        visited.add((x, y))
        time = max(time, cur)

        if x == y == n-1:
            return time
        for i, j in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=i<=n-1 and 0<=j<=n-1 and (i, j) not in visited:
                heapq.heappush(heap, (grid[i][j], i, j))

        print(cur)
        print(heap)

    return -1
print(swim_in_water([[8,2, 7], [3,4, 6], [1, 5, 0]]))

8
[(2, 0, 1), (3, 1, 0)]
2
[(3, 1, 0), (4, 1, 1), (7, 0, 2)]
3
[(1, 2, 0), (4, 1, 1), (4, 1, 1), (7, 0, 2)]
1
[(4, 1, 1), (4, 1, 1), (7, 0, 2), (5, 2, 1)]
4
[(4, 1, 1), (5, 2, 1), (7, 0, 2), (5, 2, 1), (6, 1, 2)]
4
[(5, 2, 1), (5, 2, 1), (6, 1, 2), (6, 1, 2), (5, 2, 1), (7, 0, 2)]
5
[(0, 2, 2), (5, 2, 1), (5, 2, 1), (6, 1, 2), (7, 0, 2), (6, 1, 2)]
8

<<imports for typing>>

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def calculator():
    total = 0
    bit = None
    num = "" # every path uses the same num in the calculator generator, so this is messed up

    while True:
        bit = yield

        if bit is None:
            # We must terminate the coroutine normally
            # to return a value.
            # If we do try...except GeneratorExit, we will not be able to return a value later
            break
        elif bit == "leaf":
            total += int(num, 2)
            num = num[:-1]
        else:
            num = num + str(bit)

    return total

def dele_gen():
    global results
    while True:
        results = yield from calculator()


results = 0
calc = dele_gen()
next(calc)
def traverse(node, calc):
    if node:
        calc.send(node.val)
        if node.left is None or node.right is None:
            calc.send("leaf")
        else:
            traverse(node.left, calc)
            traverse(node.right, calc)
    else:
        calc.send("")
        
l_1 = TreeNode(0)
r_0 = TreeNode(1)
l = TreeNode(0, l_1, r_0)
r = TreeNode(1)
root = TreeNode(1, l, r)
traverse(root, calc)
calc.send(None)
print(results)

11

<<imports for typing>>

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sum_root_to_leaf(root) -> int:
    if not root:
        return 0

    res = []

    def helper(node, path):
        if node.left is None and node.right is None:
            res.append(path + str(node.val))
            return
        
        if node.left:
            helper(node.left, path + str(node.val))

        if node.right:
            helper(node.right, path+str(node.val))


    helper(root, "0b")
    return sum([int(p, 2) for p in res])
l_1 = TreeNode(0)
r_0 = TreeNode(1)
l = TreeNode(0, l_1, r_0)
r = TreeNode(1)
root = TreeNode(1, l, r)
print(sum_root_to_leaf(root))

12

<<imports for typing>>


def unique_occurrences(arr: List[int]) -> bool:
    occurs = {}
    for i in arr:
        occurs[i] = occurs.get(i, 0) + 1

        
    uniques = set(occurs.values())
    return len(uniques) == len(occurs.values())

arr = [1,2,2,1,1,3]
arr = [2,2,1,1,3]
print(unique_occurrences(arr))

False

<<imports for typing>>

<<imports for typing>>
class MyHashMap:
    class Node:

        def __init__(self, val: int, key: int, parent: 'Node'=None, child: 'Node'=None):
            self._val = val
            self._key = key
            self._parent = parent
            self._child = child

        @property
        def val(self):
            return self._val
        @val.setter
        def val(self, val):
            self._val = val

        @property
        def key(self):
            return self._key

        @key.setter
        def key(self, key):
            self._key = key

        @property
        def child(self):
            return self._child

        @child.setter
        def child(self, child: 'Node'):
            self._child = child

        @property
        def parent(self):
            return self._parent

        @parent.setter
        def parent(self, parent: 'Node'):
            self._parent = parent
            

    @staticmethod
    def gen_nodes(root: 'Node'):
        node = root
        while node:
            yield node
            node = node.child

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.arr = [self.Node(-1, -1) for i in range(10000)]
        
    def _get_nodes(self, key: int):

        hash_value = self._hash_func(key)
        return self.gen_nodes(self.arr[hash_value])

    def put(self, key: int, value: int) -> None:
        """
        value will always be non-negative.
        """

        nodes = self._get_nodes(key)
        for node in nodes:
            if node.key == key:
                node.val = value
                break
        else:
            node.child = self.Node(value, key, node)

    def get(self, key: int) -> int:
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        """
        nodes = self._get_nodes(key)
        for node in nodes:
            if node.key == key:
                return node.val

        return -1
    

    def remove(self, key: int) -> None:
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        """
        
        nodes = self._get_nodes(key)
        for node in nodes:
            if node.key == key:
                if node.child:
                    node.child.parent = node.parent
                    
                node.parent.child = node.child

    @staticmethod
    def _hash_func(key: int) -> int:
        """
        Hashes key
        """
        return key // 100

obj = MyHashMap()
obj.put(100, 123)
print(obj.get(100))
obj.put(101, 124)
obj.put(101, 1024)
print(obj.get(101))
obj.put(102, 125)
print(obj.get(102))
obj.remove(102)
print(obj.get(102))
print(obj.get(101))
print(obj.get(103))

123
1024
125
-1
1024
-1

<<imports for typing>>

node = None
for node in nodes:
    if node.key == key:
        node.val = value
        break

# this is a slight modification of my solution
node.child = self.Node(value, key, node)

<<imports for typing>>



class Trie:
    class TrieNode:

        def __init__(self, is_end=False, num_children=26):
            self.is_end = is_end
            self.num_children = num_children
            self.links = [None for i in range(self.num_children)]

        @property
        def is_end(self):
            return self._is_end

        @is_end.setter
        def is_end(self, val):
            self._is_end = val


        def contains_key(self, ch: str) -> bool:
            return self.links[ord(ch)-ord('a')] is not None

        def get(self, ch: str) -> 'TrieNode':
            return self.links[ord(ch) - ord('a')]

        def put(self, ch: str, node: 'TrieNode') -> None:
            self.links[ord(ch) - ord('a')] = node

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = self.TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for ch in word:
            if not node.contains_key(ch):
                node.put(ch, self.TrieNode())
                
            node = node.get(ch)
            
        # set the last node.is_end to True
        node.is_end = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.search_prefix(word)
        return (node is not None) and node.is_end
    

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.search_prefix(prefix)
        return node is not None


    def search_prefix(self, prefix: str) -> TrieNode:
        node = self.root
        for ch in prefix:
            if node.contains_key(ch):
                node = node.get(ch)
            else:
                return None

        return node
    

# Your Trie object will be instantiated and called as such:
obj = Trie()
word="apple"
obj.insert(word)
param_2 = obj.search(word)
print(param_2)
word="app"
obj.insert(word)
param_2 = obj.search(word)
print(param_2)
prefix="apt"
param_3 = obj.startsWith(prefix)
print(param_3)
param_2 = obj.search("aa")
print(param_2)

True
True
False
False

<<imports for typing>>

<<imports for typing>>

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        def helper(node) -> None:
            nonlocal running_sum
            if node.right:
                helper(node.right)

            node.val += running_sum
            running_sum = node.val

            if node.left:
                helper(node.left)

        running_sum = 0
        helper(root)
        return root

<<imports for typing>>

<<imports for typing>>

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    def gen_node(lst: ListNode):
        yield lst
        node = lst
        while node.next:
            node = node.next
            yield node

    if l1 == None:
        return l2

    if l2 == None:
        return l1

    gen_l1 = gen_node(l1)
    gen_l2 = gen_node(l2)

    res = []

    for node in gen_l1:
        res.append(node)

    for node in gen_l2:
        res.append(node)

    res = sorted(res, key=lambda node: node.val)
    for i, node in enumerate(res):
        if i == len(res) - 1:
            break
        node.next = res[i+1]

    res[-1].next = None

    return res[0]
            
l1_1 = ListNode(4)
l1_2 = ListNode(2, l1_1)
l1_3 = ListNode(1, l1_2)
l2_1 = ListNode(4)
l2_2 = ListNode(3, l2_1)
l2_3 = ListNode(1, l2_2)

print(mergeTwoLists(l1_3, l2_3).next.next.next.val)

3

<<imports for typing>>

<<imports for typing>>

<<imports for typing>>

/-------\
| arr(i)|
|       |
\-------/
/         \
/           \
/             \
/-------\               /-------\
| max   |               | max   |
| heap  |               | heap  |
\-------/               \-------/

def max_heapify(A, i, heap_size) -> None:

    # A is 0-indexed
    l = 2*i+1
    r = 2*i+2

    largest = i
    if l < heap_size and A[l]>A[i]:
        largest = l
    if r < heap_size and A[r]>A[largest]:
        largest = r

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        # after exchanging A[i] and A[largest]
        # the subtree now rooted at A[largest] might violate the max-heap property
        # thus we need to heapify it
        # at the end, the value of the original A[i] will float down
        # as many heights as possible
        max_heapify(A, largest, heap_size)

# The children of the root node must be already max-heaps
A = [4,14,13,10,1,12]
max_heapify(A, 0, len(A))
print(A)

[14, 10, 13, 4, 1, 12]

<<max-heapify>>
def build_max_heap(A, heap_size) -> None:

    # we simply skip all leaves
    # because they are max-heaps with one element
    for i in range((len(A)//2-1), -1, -1):
        max_heapify(A, i, heap_size)

#A = [4,14,7]
#build_max_heap(A, len(A))
#print(A)

[14, 4, 7]

<<build-max-heap>>

def heapsort(A):

    # As the name suggests,
    # build a max-heap out of array A.
    # We have the largest number at root
    # after this
    build_max_heap(A, len(A)-1)

    # Keep changing root and the last element
    # max_heapify() guarantees that
    # the largest element pops to the root
    for i in range(len(A)-1, 0, -1):
        # heap_size is i
        A[0], A[i] = A[i], A[0]
        max_heapify(A, 0, i)

A=[3,13,2,123,4,1]        
heapsort(A)
print(A)

[14, 10, 7, 4, 1, 12]
[1, 2, 3, 4, 13, 123]

<<imports for typing>>
<<partitioning the array>>

def quicksort(arr, low, high):
    if low < high:
        par_idx = partition(arr, low, high)
        quicksort(arr, low, par_idx-1)
        quicksort(arr, par_idx+1, high)

A = [2,1,4,5]
quicksort(A, 0, len(A)-1)
print(A)

[1, 2, 4, 5]

def partition(arr, low, high):
    """
    This function takes last element as pivot, places the pivot element at its
    correct position in sorted array, and places all smaller elements to the left of
    the pivot, and all greater elements to the right of the pivot.

    This partitions the arr in-place. Thus the for loop seems hard to understand.
    """
    pivot = arr[high]
    # arr[low:i+1] is the smaller elements segment 
    # that are <= pivot

    # i is the idx of the last smaller element
    i = low - 1 
    # After each the iteration:
    # arr[low:i+1] are smaller elements.
    # arr[i+1:j] are larger elements.
    # arr[j:high] are unchecked elements.
    # arr[high] is the pivot
    for j in range(low, high):
        # if current element is smaller than
        # or equal to pivot
        # This means we can add another element
        # to the smaller elements segment
        if arr[j] <= pivot:
            # increment index of smaller element
            # because we found one smaller element at arr[j]
            # and is going to exchange it with arr[i]
            i += 1
            # if j>i, that means arr[i] > pivot
            # we need to exchange that with arr[j].
            # otherwise, there is no need to exchange 
            # arr[j] and arr[i]
            # however, this condition can be ignored,
            # as it does not slow down the operation
            if j>i:
                arr[i], arr[j] = arr[j], arr[i]

    # exchange the smallest element in the larger segment
    # with the pivot
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

class max_priority_queue:

    def __init__(self, nums: List[int]):
        self.q = max_heapify(nums, 0, len(nums)-1)

    def heap_max(self):
        return self.q[0]

    def heap_extract_max(self):
        if len(self.q) < 1:
            raise Exception
        m = self.q[0]
        self.q[0] = self.q[len(self.q)-1]
        self.max_heapify(self.q, 1, self.q[0]-1)

    @staticmethod
    def max_heapify(arr, i, heap_size):
        pass