def sliding_window(args):
    # Step 1: init
    s = 0                               # slow pointer
    cache = collections.Counter(nums)   # cache

    # Step 2: iterate
    for f in range(len(nums)):          # fast pointer
        # Step 2.1 expand
        cache[f] -= 1

        # Step 2.2 shrink
        while condition(f):             # condition state
            cache[s] += 1
            s += 1

    # Step 3: return whatever the question asks for
    return cache[-1]

# Find First True (i.e., assume `lefts=False, rights=True`)
while l < r:
    if condition: r = mid   # If True, ans is on the left (inclusive), so we go left.
    else: l = mid+1         # If False, ans is on the right, so we go right.

# Find Last True (i.e., assume `lefts=True, rights=False`)
while l < r:
    if condition: l = mid   # If True, answer is on the right (inclusive), so we go right.
    else: r = mid-1         # If not, answer is on the left, so we go left.

def binary_search(nums) -> int:
    def condition(mid) -> bool:
        pass

    l,r = 0,len(nums)-1     # NOTE: Pay attention to edge cases. Sometimes we need to change this boundary.
    while l < r:
        mid = l+(r-l)//2
        if condition(mid): r = mid
        else: l = mid+1
    return l

def DP(args):
    # Step 1: Init
    dp = [0]*(n+1)          # DP table
    dp[0] = 1               # base case

    # Step 2: Iterate
    for i in range(1, n+1):
        dp[i] = dp[i-1]+1   # state transition

    # Step 3: Return end case
    return dp[n]

# 739. Daily Temperatures
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    ans = [0]*len(temperatures)
    s = []  # store indices of monotonically decreasing temps
    for i,t in enumerate(temperatures):
        while s and temperatures[s[-1]] < t:  # if a higher temp is met
            ans[s[-1]] = i-s[-1]              # update ans
            s.pop()                           # pop till no higher temp
        s.append(i)                           # append unanswered index to stack
    return ans

def dfs_pre(node):
    if is_end_case(): return True
    if break_condition(): return False
    ###### ACTION HERE ######
    ###### ACTION ENDS ######
    dfs_pre(node.left)
    dfs_pre(node.right)

def dfs_in(node):
    if is_end_case(): return True
    if break_condition(): return False
    dfs_in(node.left)
    ###### ACTION HERE ######
    ###### ACTION ENDS ######
    dfs_in(node.right)

def dfs_post(node):
    if is_end_case(): return True
    if break_condition(): return False
    dfs_post(node.left)
    dfs_post(node.right)
    ###### ACTION HERE ######
    ###### ACTION ENDS ######

def bfs(node):
    if not node: return
    q = collections.deque([node])
    while q:
        node = q.popleft()
        ###### ACTION HERE ######
        ###### ACTION ENDS ######
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

# 295. Find Median from Data Stream
class MedianFinder:
    def __init__(self):
        self.small = [] # heap for the smaller half (negative so that min heap works)
        self.large = [] # heap for the larger half

    def addNum(self, num: int) -> None: # O(logn)
        # It doesn't really matter which one has one more value than the other. But be consistent during interview.
        # In this case, we allow "small" to store one more value than "large" when #nums is odd.
        if len(self.small)==len(self.large):                                 # if #nums is now even
            heapq.heappush(self.small, -heapq.heappushpop(self.large, num))  # push new num to "large", pop the smallest from "large", put it in "small"
        else:
            heapq.heappush(self.large, -heapq.heappushpop(self.small, -num)) # push new num to "small", pop the largest from "small", put it in "large"

    def findMedian(self) -> float:      # O(1)
        if len(self.small)==len(self.large):        
            return (self.large[0]-self.small[0])/2
        else:
            return -self.small[0]

graph = ...
visited = set()

def dfs_recursive(n):
    visited.add(n)
    ###### ACTION HERE ######
    ###### ACTION ENDS ######
    for neighbor in graph[n]:
        if neighbor not in visited:
            dfs(neighbor)

def dfs_iterative():
    for key in graph:                   # make sure every node gets a chance (some nodes aren't connected)
        if key in visited: continue     # prevent cycle
        s = collections.deque([key])
        while s:
            n = s.pop()
            visited.add(n)
            ###### ACTION HERE ######
            ###### ACTION ENDS ######
            for neighbor in graph[n]:
                if neighbor not in visited:
                    s.append(neighbor)

graph = ...
visited = set()

def bfs():
    for key in graph:                   # make sure every node gets a chance (some nodes aren't connected)
        if key in visited: continue     # prevent cycle
        q = collections.deque([key])
        while q:
            n = q.popleft()
            visited.add(key)
            ###### ACTION HERE ######
            ###### ACTION ENDS ######
            for neighbor in graph[n]:
                if neighbor not in visited:
                    q.append(neighbor)

parent = [i for i in range(n)]
rank = [1 for _ in range(n)]

def find(x):
    """
    If not root, keep finding the root of the curr parent and set it as the new parent.
    """
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x,y):
    """
    If same parent, then they are in the same set already.
    If diff parents,
        higher rank will be the parent.
        if same rank, add one below the other.
    """
    rx,ry = find(x),find(y)
    if rx == ry: return
    if rank[rx] > rank[ry]:
        parent[ry] = rx
    else:
        parent[rx] = ry
        if rank[rx] == rank[ry]:
            rank[ry] += 1

# update parents once again
parent = [find(i) for i in range(n)]

def topologicalSort(graph):
    n = len(graph)
    indegree = [0]*n
    q = collections.deque()
    visited = set()

    # if graph is not usable, reformat it
    ...

    # compute indegree
    for _,vs in graph.items():
        for v in vs:
            indegree[v] += 1
    
    # get 0-indegree nodes
    for i in range(n):
        if indegree[i] == 0:
            q.append(i)

    # loop queue
    while q:
        node = q.popleft()
        ###### ACTION HERE ######
        ###### ACTION ENDS ######
        visited.add(node)
        for neighbor in graph[n]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
    
    return

def dijkstra(graph,start,end):
    heap = [(0,start)]
    visited = set()

    # true Dijkstra
    while heap:
        (p,n) = heapq.heappop(heap)         # get node & path
        if n == end: return p               # return path when found
        if n in visited: continue           # prevent cycle
        visited.add(n)                      # prevent cycle
        for v,w in graph[n]:                # check neighbor
            heapq.heappush(heap,(p+w,v))
    return -1

def floyd_warshall(graph):
    # init
    N = len(graph)
    dist = [[float("inf")]*N for _ in range(N)]
    
    # set it identical as graph
    for i in range(N):
        for j in range(N):
            dist[i][j] = graph[i][j] # assume graph is 2d matrix
    
    # true Floyd Warshall
    for k in range(N):          # intermediate node
        for i in range(N):      # start node
            for j in range(N):  # end node
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])  # the triangle rule
    
    return dist

def primsMST(graph):
    ans = 0
    visited = set()
    heap = [(0,0)] # (edge,node)

    # true Prim
    while len(visited) < len(graph):                # #edges should not exceed #nodes
        e,n = heapq.heappop(heap)                   # get node & edge
        if n in visited: continue                   # prevent cycle
        ans += e                                    # add edge to ans
        visited.add(node)                           # prevent cycle
        for new_e,new_n in graph[n]:                # check neighbor
            if new_n not in visited:
                heapq.heappush(heap, [new_e,new_n])
    return ans

def KruskalMST(graph):
    MST = []
    parent = [i for i in range(n)]
    rank = [1 for _ in range(n)]
    i = 0   # index for sorted edges in graph
    
    # sort graph by edge weight
    graph = sorted(graph, key=lambda x:x[1])
  
    # true Kruskal
    while len(MST) < len(graph)-1:  # #edges should not exceed #nodes
        u,w,v = graph[i]            # get nodes & edge
        x,y = find(u),find(v)       # get parents
        if x != y:                  # prevent cycle
            MST.append([u,w,v])     # append to MST
            union(x,y)              # now they are connected
        i += 1                      # on to the next edge in graph