def Solution():
  def StoneGame(self, n, nums):
    # recursive way
    def helper(n):
      @lru_cache(None)  # auto memo in recursive call
      if n < 0: return 0  # base case
      optimal = float('inf')  # find optimal in DP formula
      for i in ...:
        optimal = min(help(n-i), optimal)  # recursive call
      dp[i] = nums[i] + optimal
			return dp[i]
   return helper(n)
		# iterative way 略

# kadane algo
# 53. Maximum Subarray
init:
  max_so_far = -inf
 	max_ending_here = -inf
for each i in a:
  max_ending_here += a[i]
  max_so_far = max(max_so_far, max_ending_here)
  max_ending_here = max(max_ending_here, 0)
return max_so_far

f[i][j] =
					when text1[i] == text2[j]		f[i-1][j-1]
  				otherwiese									max(f[i-1][j], f[i][j-1])

# transition function: f[i][j] =    f[i-1][j] if s1[i-1] == s3[i+j-1]
#                                   f[i][j-1] if s2[j-1] == s3[i+j-1]
#                                   False otherwise

f[i][j] = if word1[i-1] == word2[j-1]	dp[i][j] = dp[i-1][j-1]
					else 												1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])  # 删， 增， 改

f[i][j] = # direction don't care
					f[i-1][j-1] + f[i-1][j] when A[i] == B[j] (take)
  				f[i-1][j] otherwise (skip)

f[string][pattern]

f[empty][empty] = True; f[i][empty] = False; pairs of zero-matching * against empty string
for j in (2, len(pattern) + 1):  # first char of pattern shouldn't be *
  f[0][j] = f[0][j-2] and pattern[j-2] == '*'
  # 				^ last pair of * gets us to empty string
  #												^ this pair is a empty star pair

f[i][j] =   # we need to check B[j-1] if B[j] is *, transition is different when other direction
					when p[j] == '.' or s[i] == p[j]			f[i-1][j-1]
  				when p[j] == '*'
    												when p[j-1] = s[i] 	f[i-1][j] (consume one char)
      											otherwise						f[i][j-2] (zero match star)

f[string][pattern]

f[empty][empty] = True; f[i][empty] = False; pairs of zero-matching * against empty string
for j in (1, len(pattern) + 1):  # first char of pattern shouldn't be *
  f[0][j] = f[0][j-1] and pattern[j-1] == '*'
  # 				^ last pair of * gets us to empty string
  #												^ this pair is a empty star pair
f[i][j] =   
					when p[j] == '?' or s[i] == p[j]			f[i-1][j-1]
  				when p[j] == '*' 											f[i-1][j] or f[i][j-1]

def knapsack():
    int [N+1][W+1]
    dp[0][..] = 0
    dp[..][0] = 0
    for i in [1..N]:
    	for w in [1..W]:
    		dp[i][w] = max(物品i放入, 物品i不放入)
    return dp[N][W]

# find number of subset of an unordered list s.t. sum(subset) = target
def subsetSum(nums, S):
    dp = [0] * (S+1)  # dp[i] is the max number of ways to reach i
    dp[0] = 1
    for n in nums:
        for j in range(S + 1)[::-1]:
            if j - n >= 0:
                dp[j] += dp[j - n]  # the new way to get sum of j is to include n; and there're d[j - n] number of ways to do this
    return dp[-1]

# Coin Change MinCount
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount+1)
        dp[0] = 0
        for coin in coins:      
            if coin < amount: dp[coin] = 1
            for i in range(1, amount+1):
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        return dp[-1] if dp[-1] != float('inf') else -1

# 518. Coin Change 2
# Coin Change Combinations
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:					# <-- the order
            for i in range(1, amount + 1):  # <--
                if i - coin >= 0:
                    dp[i] += dp[i-coin]
        return dp[-1]

# Coin Change Permutation
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target+1):		# <-- the order
            for num in nums:				# <--
                if i - num >= 0:
                    dp[i] += dp[i-num]
        return dp[-1]

# backtracking
result = []
def bt(路径, 选择列表):
    if 满足条件:
        result.add(路径)
        return
   	for 选项 in 选择列表:
        make
        bt(路径, 选项列表)
        unmake

# human way of generating all subsets,
# building from a empty set:
# from left to right for each element, go to contain it
# recursive call starting from the next position
# go not contain it
def subsets(nums):
    n = len(nums)
    res = []
    def bt(start, tmp):
        res.append(list(tmp))   # res List[List[int]];
        for i in range(start, n):
            tmp += [nums[i]]
            bt(i + 1, tmp)
            tmp.pop()
    bt(0, [])
    return res
# if duplicates exists, sort it and skip duplicated elements
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums = sorted(nums)
        n = len(nums)
        def bt(start, tmp):
            res.append(list(tmp))
            for i in range(start, n):
                if i != start and nums[i-1] == nums[i]:
                    continue
                tmp.append(nums[i])
                bt(i + 1, tmp)
                tmp.pop()
        bt(0, [])
        return res

# similar way of bt, require that the len of array should be n
# don't choose an element if already included
	def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        def bt(tmp):
            if len(tmp) == n:
                res.append(list(tmp))
            for i in nums:
                if i in tmp: continue
                tmp.append(i)
                bt(tmp)
                tmp.pop()
        bt([])
        return res
# if duplicate exsits? sort !
# if z appear more than once, use z_1 then z_2 then z_3
# only add to list and call if z_i-1 is used --->
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        nums = sorted(nums)
        used_ = [False for _ in range(n)]
        def bt(tmp, used):
            if all(used):
                res.append(list(tmp))
            for i in range(n):
                if used[i] or (i != 0 and nums[i-1] == nums[i] and not used[i-1]):  # <---
                    continue
                used[i] = True
                tmp.append(nums[i])
                bt(tmp, used)
                used[i] = False
                tmp.pop()
        bt([], used_)
        return res
# combination, similar to subset?. only that require k elements instead
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def bt(start, tmp):
            if len(tmp) == k:
                res.append(list(tmp))
                return
            for i in range(start, n+1):
                tmp.append(i)
                bt(i + 1, tmp)
                tmp.pop()
        bt(1, [])
        return res

# similar to sieve of eratosthenes
# ban different location in a dfs run
def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        def dfs(queen: list, xy_diff, xy_sum):
            # queen[i] is the 2nd-dim(y) location of the queen
            # after putting a queen at (x, y), any location (i, j) s.t. i+j = x+y OR i-j = x-y OR j = y is banned
            x = len(queen)
            if x == n:
                res.append(queen)
                return
            for y in range(n):
                if y not in queen and x+y not in xy_sum and x-y not in xy_diff:
                    # don't backtrace, each dfs call is using a copy of the lists
                    # if a thread failed to sovle, it just stops by not calling further dfs
                    dfs(queen + [y], xy_diff + [x-y], xy_sum + [x+y])
        res = []
        dfs([],[],[])
        retval = []
        # output formatting, trivial
        for sol in res:
            tmp = []
            for y in sol:
                tmp.append('.' * y + 'Q' + '.' * (n-y-1))
            retval.append(list(tmp))
        # print(retval)
        return retval

def inorder(root):
  res, stack = [], []
  while root and stack:
    while root:
      stack.append(root)
      root = root.left
   	if not stack:
      return res
   	node = stack.pop()
    res.append(node.val)
    root.node.right
def preorder(root):
  if not root: return []
  res, stack = [], [root]
  while stack:
    node = stack.pop()
    res.append(node.val)
    if node.left:
      stack.append(node.left)
    if node.right:
      stack.append(node.right)
'''def postorder(root):
  res, stack = [], []
  while True:
    while root:
      if root.right:
        stack.append(root.right)
      stack.append(root)
      root = root.left()'''

# \remake
def preorder(root):
  res, stack = [], [root]
  while stack:
    root = stack.pop()
    res.append(root.val)
    if root.right: stack.append(root.right)
    if root.left:  stack.append(root.left)  # stack, next pop will be left
  return res

def inorder(root):  # inorder of BST is sorted ASC
    res, stack = [], []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        res.appned(root.val)
        root = root.right

def postorder(root):  
  # the post order is done by a reverse trick, following preorder way
  # root, right, left ==rev==> left, right, root
  res, stack = deque([]), [root]
  while stack:
    root = stack.pop()
    res.appendleft(root.val)  # always add to front
    if root.left: stack.append(root.left)
    if root.right: stack.append(root.right)
  return res

"""
This is the interface that allows for creating nested lists.
You should not implement it, or speculate about its implementation

class NestedInteger(object):
    def isInteger(self):
        # @return {boolean} True if this NestedInteger holds a single integer,
        # rather than a nested list.

    def getInteger(self):
        # @return {int} the single integer that this NestedInteger holds,
        # if it holds a single integer
        # Return None if this NestedInteger holds a nested list

    def getList(self):
        # @return {NestedInteger[]} the nested list that this NestedInteger holds,
        # if it holds a nested list
        # Return None if this NestedInteger holds a single integer
"""


class Solution(object):
    # @param {NestedInteger[]} nestedList a list of NestedInteger Object
    # @return {int} an integer
    def depthSum(self, nestedList):
        # Write your code here
        def dfs(nlist, depth) -> int:
            if not nlist:
                return 0
            res = 0
            for i in nlist:
                if i.isInteger():
                    res += depth * i.getInteger()
                else:
                    res += dfs(i.getList(), depth+1)
            return res
        if not nestedList:
            return 0
        return dfs(nestedList, 1)

class NestedIterator(object):

    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        self.stack = nestedList[::-1]

    def next(self):
        """
        :rtype: int
        """
        return self.stack.pop().getInteger()

    def hasNext(self):
        """
        :rtype: bool
        """
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            self.stack = self.stack[:-1] + top.getList()[::-1]
        return False

def inorderSuccessor(self, root, p):
        # write your code here
        # O(n) Ignore BST property:
        # keep a prev ptr to keep track of p, then we can search of node whose's prev is p
        # by inorder traversal
        curr, prev, stack = root, None, []
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            # curr = None
            curr = stack.pop()
            if prev and prev.val == p.val:
                return curr
            prev = curr
            curr = curr.right
        return None
        # O(h)
        def findmin(p):
            while p.left:
                p = p.left
            return p
        if not root or not p: return None
        if p.right:
            return findmin(p.right)
        else:
            ans = None
            while root:
                if p.val == root.val:
                    return ans
                if p.val > root.val:
                    root = root.right
                else:
                    ans = root
                    root = root.left
            return None

# 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 recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        pred = None
        wrong = [None] * 2
        def inorder(root):
            nonlocal pred, wrong
            if not root: return
            # traverse tree and set predecessor
            left = inorder(root.left)
            # login goes here
            # if we don't have more mistakes in the following traversal, then pred and root are both wrong
            # else, only pred is wrong
            if pred and pred.val >= root.val:  
                if wrong[0] and wrong[1]:
                    wrong[1] = root
                else:
                    wrong = [pred, root]  
            pred = root
            right = inorder(root.right)

        inorder(root)
        wrong[0].val, wrong[1].val = wrong[1].val, wrong[0].val

def bfs(start: Node, target: Node) -> int:
    q, visited, step = deque([start]), set([start]), 0
   	while q:
        sz = len(q)
        for i in range(sz):
            cur = q.popleft()
            if cur == target:
                return step
            for x in cur.neighbor():
                if not x in visited:
                    q.append(x)
                    visited.add(x)
         step += 1

def twoEndBfs(start: Node, target: Node) -> int:
    beginQ, endQ, visited, step = deque([start]), deque([end]), set([start]), 0
    while beginQ and endQ:
        nextQ = deque([])
        sz = len(beginQ)
        for i in range(sz):  # 展开
            cur = beginQ.popleft()
            for x in cur.neighbor():
                if x in endQ:  # endQ and startQ intersects
                    return step + 1
                if not x in visited:
                    nextQ.append(x)
        if len(endQ) < len(nextQ):  # performe reverse BFS from end if it's better
        	beginQ = endQ
            endQ = nextQ
        else:
            beginQ = endQ
        step += 1
    return 0

def topologicalSort(graph dag):
    t = []  # dag in topo order
    q, indegree = deque([]), dict()  # stack, queue, whatever order
    for u, v in dag.edge():
    	indegree[v] += 1
    q.add([i for i in indegree if indegree[i] == 0])
    while q:
        cur = q.popleft()
        for nei in cur.neighbor():
            indegree[nei] -= 1
            if indegree[nei] == 0:
            	t.append(nei)
                q.append(nei)
	return t  # if len(t) != dag.vertex() then some cycle of isolated component exists

# adjcency list easy way
graph = defaultdict(list)  # Map<Node, List<Node>>
for u, v in edge:
    graph[u].append(v)
# adjcency list formal way
class AdjNode:
    def __int__(self, data):
        self.vertex = data
        self.next = None
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [None] * self.V
    def add_edge(self, src, dest):
        node = AdjNode(dest)
        node.next = self.graph[src]
        self.graph[src] = node
        ## if undirected         
        # node = AdjNode(src)
        # node.next = self.graph[dest]
        # self.graph[dest] = node

s = 0
e = len - 1
while(s <= e):
    mid = s + (e - s) // 2
    if(nums[mid] < target):
        start = mid + 1
    else:
        end = mid - 1
# after termination end and start ptr are swapped, end = start - 1

# easy
class DisjointSet():
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] != x:
            # simple path compression
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
   	def union(self, x, y):   
        if self.find(x) == self.find(y): return
        parent[self.find(x)] = self.find(y)

# union by rank; worst case tree height is O(logN)
# runtime is O(log*N)
class DisjointSet:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y) -> bool:
        rootx, rooty = self.find(x), self.finb(y)
        if rootx == rooty: return False
        if self.rank[rootx] < self.rank[rooty]:
            self.parent[rootx] = self.parent[rooty]
       	elif self.rank[rootx] > self.rank[rooty]:
            self.parent[rooty] = self.parent[rootx]
        else:
            self.parent[rootx] = rooty
            self.rank[rooty] += 1
        return True

class DisjointSet():
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n  
    def find(self, x):
        if self.parent[x] != x:
            # simple path compression
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
   	def union(self, x, y):   
        # weight optimized: to reduce the number of parent changing in path compression, always merge small subtree into large one
        rootx , rooty = self.find(x), self.find(y)
        if rootx == rooty: return False  # x and y already in one set, loop detected
        if self.size[rooty] <= self.size[rootx]:
            self.parent[rooty] = rootx
            self.size[rootx] += self.size[rooty]
        else:
            self.parent[rootx] = rooty
            self.size[rooty] += self.size[rootx]
        return True  #x and y unioned successfully

# Amortized O(n^2). Each element in isConnected call union/find.
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        dsu = DSU(n)
        for i in range(n):
            for j in range(i):
                if i == j or isConnected[i][j] == 0: continue
                dsu.union(i, j)
        res = 0
        for i in range(n):
            if dsu.find(i) == i:
                res += 1
        return res

class DSU:
    def __init__(self, n):
        self.p = [i for i in range(n)]
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self,x , y):
        if self.find(x) == self.find(y): return
        self.p[self.find(x)] = self.find(y)

class DisjointSet():
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootx, rooty = self.find(x), self.find(y)
        if rootx == rooty: return False
        if self.size[rooty] <= self.size[rootx]:
            self.parent[rooty] = rootx
            self.size[rootx] += self.size[rooty]
        else:
            self.parent[rootx] = rooty
            self.size[rooty] += self.size[rootx]
        return True
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        ds = DisjointSet(n)
        for u, v in edges:
            if not ds.union(u, v):
                return False
        root = ds.find(0)
        return all([ds.find(i) == root for i in range(1, n)])

# https://www.lintcode.com/problem/number-of-airplanes-in-the-sky/
def countOfAirplanes(self, airplanes):
    # write your code here
    up, down = [], []
    for i in airplanes:
        up.append(i.start)
        down.append(i.end)
    up.sort()
    down.sort()
    i, j = 0, 0
    plane = res = 0
    while i < len(up) and j < len(down):
        if up[i] >= down[j]:
            plane -= 1
            j += 1
        else:
            plane += 1
            res = max(res, plane)
            i += 1
    return res
# https://leetcode.com/problems/insert-interval/
# https://leetcode.com/problems/merge-intervals/

# VIP 1272 remove interval
def removeInterval(intervals, toBeRemoved):
  res = []
  for i in intervals:
    if i[1] <= toBeRemoved[0] or i[0] >= toBeRemoved[1]:  # no overlap
      res.append(i)
    else:
      if i[0] < toBeRemoved[0]:  # left end extra remaining
        res.append([i[0], toBeRemoved[0]])
      if i[1] > toBeRemoved[1]:  # right end extra remaining
        res.append([toBeRemoved[1], i[1]])
  return res
#https://leetcode.com/problems/the-skyline-problem/

from sortedcontainers import SortedDict
class MyCalendarThree:

    def __init__(self):
        self.planes = SortedDict()

    def book(self, start: int, end: int) -> int:
        if start not in self.planes:
            self.planes[start] = 0
        if end not in self.planes:
            self.planes[end] = 0
        self.planes[start] += 1
        self.planes[end] -= 1
        cnt = 0
        res = 0
        for val in self.planes.values():
            cnt += val
            res = max(res, cnt)
        return res

# next greater element Ex: [2,1,2,4,3] -> [4,2,4,-1,-1]
# add element in reverse order into a stack. Earlier elements can find the CLOSEST 'nexts'
# when we find an elem that is small and far, it can't be part of the sol
# Ex [x, x, 4, 3, 5, y]
#    <---------------- when adding 4, 3 can be removed; after this step stack = [4, 5]
# notice that elements smaller can be removed from the stack in order to keep a ASC stack
# ASC stack: when popping next elem from stack it is always larger
# in this case, if the popped element is not large enough, we can keep popping to look for a larger element that is far away

def nextGreaterElement(nums):
  n = len(nums)
  stack, res = [], [0] * n
  for i in range(n)[::-1]:
    while stack and nums[i] >= stack[-1]: stack.pop()
    res[i] = stack[-1] if stack else -1
    stack.append(nums[i])
  return res

# 239 Sliding window maximum
# https://www.lintcode.com/problem/362/
# Optimization 1: Heap, lazy removal sliding window  O(nlogn)
# keep a maxheap to keep track of the maximum value of scanned windows
# instead of removing left ptr element, we discard head of max heap if it's too far away
def maxSlidingWindow(nums, k):
    heap = []
    res = []
    for i in range(k):
        heapq.heappush(heap, (nums[i], i))
    res.append(heap[-1][0])
    for i in range(k, len(nums)):
        heapq.heappush(heap, (nums[i], i))
        while heapq[-1][1] <= i - k:
        	heapq.pop(-1)
        res.append(heap[-1][0])

# consider case: [1, 2, 3, 4]; k = 3,
# [1, 2, 3] => 3
# [2, 3, 4] => 4, notice that '2' don't need to be checked
# consider case: [1, 1, 1, 1, 1, 4, 5], k = 6
# [1, 1, 1, 1, 1, 4] => 4
# [1, 1, 1, 1, 4, 5] => 5, notice that smaller elements can be thrown away ==> DESC Montonic Deque
	def maxSlidingWindow(nums, k):
            n = len(nums)
            q = collections.deque([])  # index
            res = []
            for i in range(n):
                while q and i - q[0] >= k: q.popleft()  # lazy remove
                while q and nums[q[-1]] <= nums[i]: q.pop()
                q.append(i)
                if i - k + 1 >= 0: res.append(nums[q[0]])
            return res

# 队列的最大值
# https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
# design a queue with offer, pop, and get_max in O(1)
# get_max returns the max value in queue
class MaxQueue:

    def __init__(self):
        self.queue = collections.deque([])
        self.max_queue = collections.deque([])

    def max_value(self) -> int:
        if not self.max_queue:
            return -1-
        return self.max_queue[0]

    def push_back(self, value: int) -> None:
        self.queue.append(value)
        while self.max_queue and self.max_queue[-1] < value:
            self.max_queue.pop()
        self.max_queue.append(value)

    def pop_front(self) -> int:
        if not self.queue:
            return -1
        if self.max_queue[0] == self.queue[0]:
            self.max_queue.popleft()
        return self.queue.popleft()

# quicksort, best case T(n) = O(n) + 2 O(n/2) + ...= nlgn
# worst case T(n) = T(n) + T(n-1) + ... = n^2
def quickSort(arr, low, high):
    if low >= high: return
    pv = partition(arr, low, high)
    quickSort(arr, low, pv-1)
    quickSort(arr, pv+1, high)

def partition(arr, low, high):
    wall = low
    pivot = arr[high]
    for i in range(low, high):
        # make sure left of wall is nonstrictly smaller than pivot
        if arr[i] <= pivot:
            arr[wall], arr[i] = arr[i], arr[wall]
            wall += 1
    arr[high], arr[wall] = arr[wall], arr[high]

# inversion pairs:
# find all the pairs st. nums[i] > num[j] and i < j
# a large number that has a small index
# 3 1 2 -> 31, 32
# 8 4 2 1 -> 84, 82, 81, 42, 41, 21
# start with merge sort, we count the number of such pairs in the merging step
def mergesortCount(arr, l, r):
	cnt = 0
  if l < r:
    m = (l + r) // 2
    count += mergesortCount(arr, l, m)
    count += mergesortCount(arr, m+1, r)
    count += mergeCount(arr, l, m, r)
def mergeCount(arr, l, m, r):
  left = arr[l:m+1]
  right = arr[m+1:r+1]
  i = j = k = 0
 	swap = 0
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      arr[k] = left[i]
      k += 1; i += 1
    else:
      arr[k] = right[j]
      k += 1; j += 1
      swap += m - (l + r) + 1
  return swap
# master theorem
T(n) = a T(n/b) + O(n^c)
c^crit = log_b(a)
1. c < c_crit, leaf-heavy => O(n^c_crit)
2. c = c_crit, comparable -> rewrite f(n) part into O(n^c log^k n) => O(n^crit log^(k+1) n)
3. c > c_crit, root_heavy => O(n^c)

1.T(n) = 8T(n/2) + 1000n^2 => O(n^3)
2.T(n) = 2(T/2) + 10n => O(nlogn)
3.T(n) = 2(T/2) + n^2 => O(n^2)

# given a string containing only vowels
# for each ending points of a valid subarray, we can always define a right bound st s[i:j] is valid subarray
# where i in [0, bound]
class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        v = set('aeiou')
        def valid(d):
            return all([d[vv] >= 1 for vv in v])
        def allfive(word):
            res = left = 0
            n = len(word)
            d = defaultdict(int)
            for i in range(n):
                d[word[i]] += 1
                while d[word[left]] > 1:   
                    d[word[left]] -= 1
                    left += 1
                if valid(d):
                    res += left + 1
            return res  

        ans = 0
        prev = -1
        for i in range(len(word)):
            if word[i] not in v:
                if prev == -1:
                    prev = i
                    continue
                else:
                    ans += allfive(word[prev+1: i])
                    prev = i
        ans += allfive(word[prev+1: len(word)])
        return ans

# Sliding window not applicable
# weak optimization from O(N^3) -> O(N^2)

# given a string containing only elements with cnt > 2
# for ending points of a valid subarray, a bound could not be defined
# Ex: 2 3 3 3 2;    2 3 3 3 2
#       ^   ^ 		^       ^
#       |   |       |       |
# left pointer don't behave like sliding window
from collections import defaultdict
def func(A):
    result = 0
    for i in range(0,len(A)):
        counter = 0
        hashmap = defaultdict(int)
        for j in range (i, len(A)):
            hashmap[A[j]] += 1
            if hashmap[A[j]] == 2:
                counter += 1
            if counter != 0 and counter == len(hashmap):
                result += 1
    return result

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
  def invalid(hashmap, k):
    # valid or invalid, determine if hashmap defines a valid window
    # valid: trim left to find a smallest window that is still valid
    # invalid: trim left to find a largest sub-window that is valid
    # Valid Ex: len(hashmap.keys()) == k; each all(haspmap.values() >= k); etc
    return len(hashmap) > k
  hashmap = dict()
  left, res = 0, 0
  for i in range(len(s)):  
    c = s[i]
    if c in hashmap: hashmap[c] += 1
    else: hashmap[c] = 1
    while invalid(hashmap, k):     # <- record the result here 'while valid trim to minimize'
      left_c = s[left]
      hashmap[left_c] -= 1
      if hashmap[left_c] == 0:
        del hashmap[left_c]
      left += 1
    res = max(res, i - left + 1)  # <- record the result here 'while invalid trim'
  return res
# follow up: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/discuss/80044/Java-O(nlogk)-using-TreeMap-to-keep-last-occurrence-Interview-%22follow-up%22-question!

## https://leetcode.com/problems/subarray-sum-equals-k/
def subarraySum(self, nums: List[int], k: int) -> int:
    n = len(nums)
    sum_ = 0  # prefix sum takes sum of 0-i
    hashmap = defaultdict(int)  # hashmap[0] = (prefix_j, freq), prefix_j where j < i, freq appearance
    hashmap[0] += 1  # account for subarrays nums[0:x]
    res = 0
    for num in nums:
        sum_ += num
        res += hashmap[sum_ - k]
        hashmap[sum_] += 1
	return res

## https://www.lintcode.com/problem/range-addition/discuss
# lazy propagation
def getModifiedArray(self, length, updates):
        # Write your code here
        action = [0] * length
        for (start, end, val) in updates:
            action[start] += val
            if end + 1 < length: action[end+1] -= val
        rolling = 0
        res = []
        for i in action:
            rolling += i
            res.append(rolling)
        return res

# 297
# Use preorder traversal to do the serialization step
# The resulting string has the form
# | Root | Left Subtree | Right Subtree |
# Use recursion to deserialize that string

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        # preorder traversal
        if not root: return "#"
        return str(root.val) + "," + self.serialize(root.left) + "," + self.serialize(root.right)


    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        def helper(data):
            s = data.popleft()
            if s == "#": return None
            root = TreeNode(int(s))
            root.left = helper(data)
            root.right = helper(data)
            return root
        return helper(collections.deque(data.split(',')))

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_word = False
class Trie:

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

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for c in word:
            if not node.children[ord(c) - ord('a')]:
                node.children[ord(c) - ord('a')] = TrieNode()
            node = node.children[ord(c) - ord('a')]
        node.is_word = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for c in word:
            if not node.children[ord(c) - ord('a')]:
                return False
            node = node.children[ord(c) - ord('a')]
        return node.is_word

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for c in prefix:
            if not node.children[ord(c) - ord('a')]:
                return False
            node = node.children[ord(c) - ord('a')]
        return True


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

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left

    def next(self) -> int:
        node = self.stack.pop()
        cur = node.right
        while cur:
            self.stack.append(cur)
            cur = cur.left
        return node.val

    def hasNext(self) -> bool:
        return bool(self.stack)

# number of island
# DFS
dirs = [[0,1], [0,-1], [1,0], [-1,0]]
def dfs(x, y):
  if x < 0 or y < 0 or x >= len(grid) or y > len(grid[0]) or grid[x][y] != '1': return
  grid[x][y] = '0'
  for dir in dirs:
    dfs(x+dir[0], y+dir[1])
# DFS iterative
def dfs(x, y):
  if x < 0 or y < 0 or x >= len(grid) or y > len(grid[0]) or grid[x][y] != '1': return
  stack = [(x, y)]
  while stack:
    i, j = stack.pop()
    if i < 0 or j < 0 or i >= len(grid) or j > len(grid[0]) or grid[i][j] != '1': continue
    grid[i][j] = '0'
    for dir in dirs:
      q.append((i+dir[0], j+dir[1]))
# BFS
def bfs(x, y):
  if x < 0 or y < 0 or x >= len(grid) or y > len(grid[0]) or grid[x][y] != '1': return
  q = deque([(x,y)])
  while q:
    i, j = q.popleft()
    if i < 0 or j < 0 or i >= len(grid) or j > len(grid[0]) or grid[i][j] != '1': continue
    grid[i][j] = '0'
    for dir in dirs:
      q.append((i+dir[0], j+dir[1]))
def numIslands(grid: List[List[str]]) -> int:
  cnt = 0
  for i in range(len(grid)):
    for j in range(len(grid[0])):
      if grid[i][j] == '1':
        dfs(i, j)  / bfs(i, j)
      	cnt += 1
  return cnt

# sort to sovle duplicates
# + two pointer
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # faster than hashset, easier to deduplicate
        res = []
        nums.sort()
        n = len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i-1] == nums[i]: continue  # deduplicate
            s, e = i+1, n-1
            target = -nums[i]
            while s<e:
                if nums[s] + nums[e] == target:
                    res.append([nums[i], nums[s], nums[e]])
                    s += 1
                    while s<e and nums[s] == nums[s-1]:  # deduplicate
                        s += 1
                elif nums[s] + nums[e] < target:
                    s += 1
                else:
                    e -= 1
        return res

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 4sum -> enumerate (i, j) * 2sum
        n = len(nums)
        nums.sort()
        res = []
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i-1]: continue  # deduplicate: prev round is the same i
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j-1]: continue  # deduplicate: prev round is the same j
                sum2 = target - nums[i] - nums[j]
                s, e = j + 1, n - 1
                while s < e:
                    if nums[s] + nums[e] == sum2:
                        res.append([nums[i], nums[j], nums[s], nums[e]])
                        s += 1  # move both ptr
                        e -= 1
                        while s < e and nums[s] == nums[s-1]: s += 1  # move till not equal
                        while s < e and nums[e] == nums[e+1]: e -= 1
                    elif nums[s] + nums[e] > sum2:
                        e -= 1
                    else:
                        s += 1
        return  res

    # Brute force
    for (int a = 0; a < A.size(); a++)
        for (int b = 0; b < B.size(); b++)
            for (int c = 0; c < C.size(); c++)
                for (int d = 0; d < D.size(); d++)    
                     if (A[a] + B[b] = - C[c] - D[d])
                        ...

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        n = len(nums1)
        ab = defaultdict(int)
        for i in nums1:
            for j in nums2:
                ab[i + j] += 1
        res = 0
        for m in nums3:
            for n in nums4:
                res += ab[- m - n]
        return res

# only find the number of ways
class Solution:
    """
    @param A: An integer array
    @param k: A positive integer (k <= length(A))
    @param target: An integer
    @return: An integer
    """
    def kSum(self, A, k, target):
        # write your code here
        n = len(A)
        # dp[m][n][q]: number of ways to get a sum of q when chosing n element from A[:m]
        dp = [[[0 for _ in range(target+1)] for _ in range(k+1)] for _ in range(n+1)]
        for i in range(n+1): dp[i][0][0] = 1
        for i in range(1, n+1):
            for j in range(1, k+1):
                for t in range(target+1):
                    dp[i][j][t] = 0
                    if t >= A[i-1]:
                        dp[i][j][t] = dp[i-1][j-1][t-A[i-1]]
                    dp[i][j][t] += dp[i-1][j][t]
        return dp[n][k][target]

# Method 1: brute force subset
class Solution:  
    """
    @param A: an integer array
    @param k: a postive integer <= length(A)
    @param target: an integer
    @return: A list of lists of integer
    """
    def kSumII(self, A, k, target):
        # write your code here
        res = []
        n = len(A)
        A.sort()
        def dfs(i, tmp, sum_):
            if len(tmp) == k:
                if sum_ == target:
                    res.append(tmp)
                return
            if i == n or sum_ > target:
                return
            for j in range(i, n):
                if A[j] > target: break
                dfs(j+1, tmp + [A[j]], sum_ + A[j])
        dfs(0, [], 0)
        return res

# Method 2: recursive k-sum (layer by layer, reduce to 2 sum)  O(Nk)
class Solution:
    """
    @param A: an integer array
    @param k: a postive integer <= length(A)
    @param target: an integer
    @return: A list of lists of integer
    """
    def kSumII(self, A, k, target):
        # write your code here
        A.sort()
        return self.ksum(A, k, target)

    def ksum(self, A, k, target):
        res = []
        if k == 1:
            return [] if target not in A else [[target]]
        if k == 2:
            return self.twosum(A, target)
        # pruning trick: if smallest value is too larget or largest value too smaller, just break
        # if A[0] * k > target or A[-1] * k < target:
        #     return []
        for i in range(0, len(A) - k + 1):
            if i > 0 and A[i] == A[i-1]: continue
            subset = self.kSumII(A[i+1:], k - 1, target - A[i])
            for sub in subset:
                res.append([A[i]] + sub)
        return res

    def twosum(self, nums, target):  
        # assume sorted nums, allows duplicate
        # returns twosum combinations
        res = []
        s , e = 0, len(nums) - 1
        while s < e:
            if nums[s] + nums[e] == target:
                res.append([nums[s], nums[e]])
                s += 1
                e -= 1
                while nums[s] == nums[s-1]: s += 1
                while nums[e] == nums[e+1]: e -= 1
            elif nums[s] + nums[e] < target:
                s += 1
            else:
                e -= 1
        return res

# eratosthenes prime finding
def eratosthenes(n):
    IsPrime = [True] * (n + 1)
    for i in range(2, int(n ** 0.5) + 1):
        if IsPrime[i]:
            for j in range(i * i, n + 1, i):
                IsPrime[j] = False
    return [x for x in range(2, n + 1) if IsPrime[x]]
if __name__ == "__main__":
    print(eratosthenes(120))

# inorder iterative

# 1024 AND 1326
class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        res = st = curEnd = 0
        clips.sort()
        n = len(clips)
        i = 0
        while i < n:
            if st >= time:
                return res
            if clips[i][0] > st:
                return -1
            while i < n and clips[i][0] <= st:
                curEnd = max(curEnd, clips[i][1])
                i += 1
            res += 1
            st = curEnd
        return res if st >= time else -1

# Method 1: Union Find
# Graph format: edge list
# Ex:
def validTree(n, edges):
    dsu = DSU(n)
    for edge in edges:
        if not dsu.union(edge[0], edge[1]):
            return False
    return len(edges) == n-1

# Method 2: dfs, find back edge
# Graph format: adjacency list
def isCyclic(graph: defaultdict(list)):
    n = len(graph)
    visited = [False] * n
    for v in graph:
        if not visited[v]:
            if isCyclicUtil(i, -1):
                return True

    def isCyclicUtil(cur, parent):
        visited[cur] = True
        for nei in graph[cur]:
            if not visited[nei]:
                if isCyclicUtil(nei, cur):
                    return True
            else:
                if nei != parent:  # ignore trivial back edge between parent and cur 0 <-> 1
                    return True

# topological sort with DFS
def isDAG(n, graph):
    visited = [0] * n
    for v in range(vertice):
        if visited[v] == 0:
            if not dfs(v):
                return False
def dfs(v):
    visited[v] = 1 # 1=visiting
    for nei in graph[v]:
        if visited[nei] == 1:
            return False
        if visited[nei] == 0:  #0=unvisited
            dfs(nei)
    visited[v] = 2  # 2=visited    
# topological sort with BFS (kahn's algo 入度表)

graph = [[0 for _ in range(N)] for _ in range(N)]  # AdjMatrix
visited = set()
distance = [float('inf')] * N
distance[0] = 0
for i in range(N):
  nextClosest = -1
  for j in range(N):
    if j not in visited:  # 在剩余vertex 里面 找到最小路径的vertex
      if nextClosest == -1 or distance[j] < distance[nextClosest]:
        nextClosest = j
    visited.add(nextClosest)
      for y in range(N):
        if y not in visited:
          distance[y] = min(distance[y], graph[nextClosest][y])

# https://www.youtube.com/watch?v=jsmMtJpPnhU
def lazyPrim(graph, n, start=0) -> int:
	# given a graph with n vertices, find the min spanning tree rooted at start
    # Prim's Algo (greedy)
    # graph = defaultdict()  # AdjList size=N, graph[i] -> (nei, weight)
    pq = []  # edge = (weight, src, dst)
    visited = set()
    def addEdge(node):
		visited.add(node)
        # iterate all outgoing edges of node
        for nei in graph[node]:
            if nei not in visited:
                heappush(pq, (nei[1], node, nei[0]))
	addEdge(start)
  	mstEdges = []  # should be of size |V| - 1
  	mstCost = 0
  	while pq and len(mstEdges) != n-1:
    	z,x,y = heapq.pop(pq)
    	if y in visited:
      		continue
    	mstCost += z
    	mstEdges.append((z,x,y))
		addEdge(y)
    if len(mstEdges) != n - 1:
    	return None, None  # graph is not connected
	return mstEdges, mstCost

# vertex按distance顺序被visited，visited后distance就确定了
# 当发现一个vertex的distance减少时，vertex会重复进pq，此时distance较小的会先被visit，较大的会被跳过
def dijikstra(graph,s, n):
    visited = [False] * n
    distance = [float('inf')] * n
    distance[s] = 0
    pq = []
    heappush(pq, (distance[s], s))
    while pq:
        dist, node = heappop(pq)
        if visited[node]: continue
        visited[node] = True   
        for nei, w in graph[node]:
            if not visited[nei] and dist + w < distance[nei]:
                distance[nei] = dist + w
                heappush(pq, (distance[nei], nei))