count = Counter(nums)
nums.sort(key=lambda x: (count[x],-x))
return nums

n = len(nums)
counter = Counter(nums)
buckets = [0] * (n + 1)

for num, freq in counter.items():
	if buckets[freq] == 0:
		buckets[freq] = [num]
	else:
		buckets[freq].append(num)    
ret = []
for i in range(n, -1, -1):
	if buckets[i] != 0:
		ret.extend(buckets[i])
	if len(ret) == k:
		break
return ret

class Heap:
    @staticmethod
    def heapify(arr):
        """Transform the arr to a min-heap"""
        n = len(arr)
        for i in range(n // 2 - 1, -1, -1):
            Heap._heapify_down(arr, n, i)

    @staticmethod
    def heappush(arr, value):
        """Adds value to the heap while keeping the heap property"""
        arr.append(value)
        Heap._heapify_up(arr, len(arr) - 1)

    @staticmethod
    def heappop(arr):
        """Remove and returns heap smallest element"""              
        root = arr[0]
        arr[0] = arr[-1]
        arr.pop()
        Heap._heapify_down(arr, len(arr), 0)
        return root

    @staticmethod
    def _heapify_down(arr, n, i):
        """Keep the min-heap property starting from position i going down in the tree"""
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and arr[left] < arr[smallest]:
                smallest = left
            if right < n and arr[right] < arr[smallest]:
                smallest = right
            if smallest != i:
                arr[i], arr[smallest] = arr[smallest], arr[i]
                i = smallest
            else:
                break

    @staticmethod
    def _heapify_up(arr, i):
        """Keep the min-heap property starting from position i going up in the tree"""
        while i != 0 and arr[(i - 1) // 2] > arr[i]:
            parent = i // 2
            arr[i], arr[parent] = arr[parent], arr[i]
            i = parent

hp = []
for i in range(len(stones)):
	hp.append(-1*stones[i])
heapq.heapify(hp)
        
while len(hp) > 1:
	x = heapq.heappop(hp)
	y = heapq.heappop(hp)
	if x != y:
		heapq.heappush(hp,-abs(x-y))

if len(hp) == 0:
	return 0
return -1*hp[0]

slow,fast = 0,0
while True:
    slow = nums[slow]
    fast = nums[nums[fast]]
    if slow == fast:
        break
slow1 = 0
while True:
    slow1 = nums[slow1]
    slow = nums[slow]
    if slow1 == slow:
        return slow1

res = 0
for n in nums:
    res = n ^ res
return res

d = {}
for i in range(len(nums)):
    if target-nums[i] in d:
        return [d[target-nums[i]],i]
    d[nums[i]] = i

l, r = 0, len(numbers)-1
while l < r:
    two_sum = numbers[l] + numbers[r]
    if two_sum < target:
        l += 1
    elif two_sum > target:
        r -= 1
    else:
        return [l+1,r+1]

nums.sort()
out = []
for i in range(len(nums)-2):
    if i > 0 and nums[i] == nums[i-1]:
        continue
    l, r = i+1,len(nums)-1
    while l < r:
        t_sum = nums[i] + nums[l] + nums[r]
        if t_sum < 0:
            l += 1
        elif t_sum > 0:
            r -= 1
        else:
            triplets = [nums[i],nums[l],nums[r]]
            out.append(triplets)
            while l < r and nums[l] == triplets[1]:
                l += 1
            while r > l and nums[r] == triplets[2]:
                r -= 1
return out

stack = []
if len(tokens) == 1:
	return int(tokens[0])
for token in tokens:
	if token not in ['+','-','*','/']:
		stack.append(token)
	else:
		a, b = int(stack.pop()), int(stack.pop())
		if token == '+':
			stack.append(b + a)
		if token == '-':
			stack.append(b - a)
		if token == '/':
			stack.append(int(b / a))
		if token == '*':
			stack.append(b * a)
return stack[0]

n = len(nums)
pref, suff = [1]*(n+1),[1]*(n+1)
for i in range(1,n+1):
	pref[i] = pref[i-1]*nums[i-1]
for i in range(n-1,-1,-1):
	suff[i] = suff[i+1] * nums[i]
out = []
for i in range(n):
	out.append(pref[i]*suff[i+1])
return out

l,r = 0,len(nums)-1
while l<=r:
    m = (l+r) // 2
    if nums[m] == target:
        return m
    if nums[m] > target:
        r = m - 1
    else:
        l = m + 1
return -1

m = len(matrix)
n = len(matrix[0])
left, right= 0, m*n-1
while left <= right:
    mid = (left + right) // 2
    mid_row, mid_col = mid // n, mid % n
    if matrix[mid_row][mid_col] == target:
        return True
    elif matrix[mid_row][mid_col] < target:
        left = mid + 1     
    else:
		right = mid - 1
return False

l, r = 0,len(nums)-1
while l < r:
    m = (l+r) // 2
    if nums[m] > nums[r]:
        l = m+1
    else:
        r = m
return nums[l]

l,r = 0,len(nums)-1
while l <= r:
    m = (l+r) //2
    if nums[m] == target:
        return m
    if nums[l] <= nums[m]: #left half is sorted
        if nums[l] <= target <= nums[m]:
            r = m-1
        else:
            l = m+1
    else:
        if nums[m] <= target <= nums[r]:
            l = m+1
        else:
            r = m-1
return -1

newList = None
while head:
	next = head.next
	head.next = newList
	newList = head
	head = next
return newList

newList = ListNode()
tail = newList
while list1 != None and list2 != None:
    if list1.val < list2.val:
        tail.next = list1
        list1 = list1.next
    else:
        tail.next = list2
        list2 = list2.next
        tail = tail.next
    if list1 != None:
        tail.next = list1
    elif list2 != None:
        tail.next = list2 
return newList.next

# find middle
slow, fast = head, head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# reverse second half
second = slow.next
prev = slow.next = None
while second:
    tmp = second.next
    second.next = prev
    prev = second
    second = tmp

# merge two halfs
first, second = head, prev
while second:
    tmp1, tmp2 = first.next, second.next
    first.next = second
    second.next = tmp1
    first, second = tmp1, tmp2

dummyNode = ListNode()
dummyNode.next = head
l = dummyNode
i = 0
r = dummyNode.next
while i < n:
    r = r.next
    i += 1
        
while r:
    l = l.next
    r = r.next
      
l.next = l.next.next
return dummyNode.next

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}    
        self.lru = Node(0,0)
        self.mru = Node(0,0)
        self.lru.next = self.mru
        self.mru.prev =  self.lru

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].value
        return -1
        
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key,value)
        self.insert(self.cache[key])

        if len(self.cache) > self.capacity:
            #remove and delete the LRU
            lru = self.lru.next
            self.remove(lru)
            del self.cache[lru.key]
        
	# Removes any node from linked list in O(1)
    def remove(self, node):
        prev,next = node.prev,node.next
        prev.next,next.prev = next,prev

	# Inserts new node from mru
    def insert(self,node):
        prev,next = self.mru.prev, self.mru
        prev.next = next.prev = node
        node.next, node.prev = next,prev

def invertTree(self, root):
    if not root:
        return
    root.left, root.right = root.right,root.left
    self.invertTree(root.left)
    self.invertTree(root.right)
    return root

def dfs(root):
	if not root:
		return 0
	hl = dfs(root.left)
	hr = dfs(root.right)
	return 1 + max(hl, hr)
return dfs(root)

def dfs(root):
    if not root:
        return (True,0)
    b1,h1 = dfs(root.left)
    b2,h2 = dfs(root.right)
    if b1 and b2 and abs(h1-h2)<=1:
        return (True,max(h1,h2)+1)
    else:
        return (False,max(h1,h2)+1)   
return dfs(root)[0]

def dfs(root1,root2):  
    if not root1 and not root2:
        return True
    if not root1 and root2:
        return False
    if root1 and not root2:
        return False
    a = dfs(root1.left,root2.left)
    b = dfs(root1.right,root2.right)
	return root1.val == root2.val and a and b
return dfs(p,q)

if not root1 and not root2:
    return True
if not root1 and root2:
    return False
if root1 and not root2:
    return False

if not root1 or not root2:
	return root1 == root2

def sameTree(root1,root2):
    if not root1 and not root2:
        return True
    if not root1 and root2:
        return False
    if not root2 and root1:
        return False
    l = sameTree(root1.left, root2.left)
    r = sameTree(root1.right, root2.right)
    return l and r and root1.val == root2.val

def dfs(root,subRoot)->bool:
    if not root:
        return False
    if sameTree(root, subRoot):
        return True
    l = dfs(root.left, subRoot)
    r = dfs(root.right, subRoot)
    return l or r
return dfs(root,subRoot)

if not root:
    return []
q = deque([root])
out = []
while q:
    elem = []
    for i in range(len(q)):
        e = q.popleft()
        if e.left:
            q.append(e.left)
        if e.right:
            q.append(e.right)
        elem.append(e.val)
    out.append(elem)
return out

if not root:
    return 
d = deque([root])
out = []
while d:
    l = []
    for i in range(len(d)):
        n = d.popleft()
        if n.left:
            d.append(n.left)
        if n.right:
            d.append(n.right)
        l.append(n.val)
    out.append(l[-1])
return out

diameter = [0]
def dfs(root):
    if not root:
        return 0       
    l = dfs(root.left)
    r = dfs(root.right)
    diameter[0] = max(diameter[0],l+r)
    return 1+ max(l,r) 
dfs(root)
return diameter[0]

def dfs(root, v, path):      
	if not root:
        return False
    path.append(root.val)
    if root.val == v:
        return True
    fl = dfs(root.left, v, path)
    if fl:
        return True
    fr = dfs(root.right, v, path)
    if fr:
        return True
    path.pop()
    return False

p1, p2 = [], []
dfs(root,p.val,p1)
dfs(root,q.val,p2)
i = 0
ret = None
while i < len(p1) and i < len(p2):
    if p1[i] != p2[i]:
        break
    ret = p1[i]
    i+=1
return TreeNode(ret)

def dfs(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1
    tree = TreeNode(root1.val + root2.val)
    tree.left = dfs(root1.left, root2.left)
    tree.right = dfs(root1.right, root2.right)
    return tree
return dfs(root1, root2)

res = [root.val]
def dfs(root):
    if not root:
        return 0
    leftMax = dfs(root.left)
    rightMax = dfs(root.right)
    leftMax = max(leftMax, 0)
    rightMax = max(rightMax, 0)
    res[0] = max(res[0], root.val + leftMax + rightMax)
    return root.val + max(leftMax, rightMax)
dfs(root)
return res[0]

result = []
def dfs(i,sub):
    if i == len(nums):
        result.append(sub.copy())
        return
    sub.append(nums[i])
    dfs(i+1,sub)
    sub.pop()
    dfs(i+1,sub)

dfs(i+1,sub + [nums[i]])

res = []
def dfs(permutation):
    if len(permutation) == len(nums):
        res.append(permutation.copy())
        return
    for i in range(len(nums)):
        if not nums[i] in permutation:
            permutation.append(nums[i])
            dfs(permutation)
            permutation.pop()
dfs([])
return res

res = []
def dfs(i,sa):
    if sum(sa) == target:
        res.append(sa.copy())
        return
    if sum(sa) > target:
        return    
    for j in range(i,len(candidates)):
		sa.append(candidates[j])
        dfs(j,sa)
		sa.pop()
dfs(0,[])
return res

res = []
sub = []
nums.sort()
def backtrack(i):
    if i == len(nums):
        res.append(sub.copy())
        return
    sub.append(nums[i])
    backtrack(i+1)
    sub.pop()
    while i + 1 < len(nums) and nums[i] == nums[i + 1]:
        i += 1
    backtrack(i+1)
backtrack(0)
return res

UNVISITED = 0
CURRENTLY_VISITING = 1
VISITED = 2
states = [0] * numCourses
def dfs(i):
    if states[i] == VISITED:
        return True
    states[i] = CURRENTLY_VISITING
    for v in adjList[i]:
        if states[v] == CURRENTLY_VISITING:
            return False
        a = dfs(v)
         if not a:
            return False
    states[i] = VISITED
    return True

for i in range(numCourses):
    if not dfs(i):
        return False
return True

def bfs(i,j):
    q = deque([(i,j)])
    grid[i][j] = '0'
    while q:
        r,c = q.popleft()
        if r+1 in range(len(grid)) and grid[r+1][c] == '1':
            q.append((r+1,c))
            grid[r+1][c] = '0'
        if r-1 in range(len(grid)) and grid[r-1][c] == '1':
            q.append((r-1,c))
            grid[r-1][c] = '0'
        if c+1 in range(len(grid[0])) and grid[r][c+1] == '1':
            q.append((r,c+1))
            grid[r][c+1] = '0'
        if c-1 in range(len(grid[0])) and grid[r][c-1] == '1':
            q.append((r,c-1))
            grid[r][c-1] = '0' 
count = 0
for i in range(len(grid)):
	for j in range(len(grid[0])):
        if grid[i][j] == '1':
            bfs(i,j)
            count +=1
return count

rows, cols= len(board), len(board[0])
def dfs(r,c): 
    if (r<0 or r==rows or c<0 or c==cols or board[r][c]!="O"):
        return 
    board[r][c]="T"
    dfs(r+1,c)
    dfs(r-1,c)
    dfs(r,c+1)
    dfs(r,c-1)
#(DFS)capture unsurrounded region(0->T)
for r in range(rows):
    for c in range(cols):
        if board[r][c]=="O" and (r==0 or r==rows-1 or c==0 or c==cols-1):
            dfs(r,c)
#capture surrounded region(0->x)
for r in range(1,rows-1):
    for c in range(1,cols-1):
        if board[r][c]=="O":
            board[r][c]="X" 
#uncapture unsurrounded region(T->0)
for r in range(rows):
    for c in range(cols):
        if board[r][c]=="T":
            board[r][c]="O"

adjList = defaultdict(list)
for e in prerequisites:
    adjList[e[1]].append(e[0])

states = [0] * numCourses
def dfs(i):
    if states[i] == 2:
        return True
    states[i] = 1
    for v in adjList[i]:
        if states[v] == 1:
            return False
        a = dfs(v)
        if not a:
            return False
    states[i] = 2
    return True

for i in range(numCourses):
    if not dfs(i):
        return False
return True

adj_list = defaultdict(list)
for p in prerequisites:
    adj_list[p[1]].append(p[0])
        
in_degrees = [0] * numCourses
for p in prerequisites:
    in_degrees[p[0]] += 1
        
q = deque()
for i in range(numCourses):
    if in_degrees[i] == 0:
        q.append(i)
out = []
while q:
    v = q.popleft()
    out.append(v)
    for n in adj_list[v]:
        in_degrees[n] -= 1
        if in_degrees[n] == 0:
            q.append(n)
if len(out) == numCourses:
    return out
else:
    return []

procedure IntervalSchedule (1,2,...,n)
	candidate <- {1,2,...,n}
	out <- {}
	while candidate
		k <- interval that ends first
		out <- out U {k}
		candidate <- candidate - {k}
		remove from candidate all the intervals incompatible with k
	return out

intervals.sort(key = lambda x: x[1])
out = [intervals[0]]
t = intervals[0][1]
for i in range(1,len(intervals)):
    if intervals[i][0] >= t:
		out.append(intervals[i])
        t = intervals[i][1]
return out

intervals.sort(key = lambda x: x[1])
t = intervals[0][1]
out = 0
for i in range(1,len(intervals)):
    if intervals[i][0] >= t:
        t = intervals[i][1]
    else:
        out += 1
return out

def coinChange(change, coins):
	S = {}
	while change > 0:
		c = largest coins[i]: coins[i] <= r
		if no such c:
			return no solution
		change = change - c
		S = S + {c}
	return S

def coinChange(change, coins):
	out = []
	coins.sort()
	while r > 0 and coins:
		c = coins.pop()
		if c >= change:
			change = change - c
			out.append(c)
	if r == 0:
		return out
	else:
		return no solution