K Largest Elements
class Solution:
# @param A : list of integers
# @param B : integer
# @return a list of integers
def solve(self, A, B):
import heapq as hp
hp.heapify(A)
for i in range(len(A)-B):
hp.heappop(A)
return A
Profit Maximisation
import heapq
class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def solve(self, A, B):
cost = 0
A = [-el for el in A]
heapq.heapify(A)
for i in range(B):
smallest = A[0]
heapq.heapreplace(A, A[0] + 1)
cost += abs(smallest)
return cost
Perfect example to understand hashing using dict
Distinct Numbers in Window
class Solution:
# @param A : list of integers
# @param B : integer
# @return a list of integers
def dNums(self, A, B):
seen = {}
res = list()
ptrs = [None]*len(A)
for i in range(B):
seen[A[i]] = i
res.append(len(seen))
for i in range(B, len(A)):
if seen[A[i-B]]==i-B:
del seen[A[i-B]]
seen[A[i]] = i
res.append(len(seen))
return res
Solving maxheap logic using minheap from heapq
from heapq import *
class Solution:
# @param A : integer
# @param B : list of integers
# @return an integer
def nchoc(self, A, B):
h = [-b for b in B]
heapify(h)
s = 0
for _ in range(A):
chocs = -heappop(h)
s = (s + chocs) % 1000000007
heappush(h, -(chocs // 2))
return s
1) The maximum number of nodes at level ‘l’ of a binary tree is 2l.
2) The Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1.
3) In a Binary Tree with N nodes, minimum possible height or the minimum number of
levels is Log2(N+1).
4) A Binary Tree with L leaves has at least | Log2L |+ 1 levels.
5) In Binary tree where every node has 0 or 2 children, the number of leaf nodes is
always one more than nodes with two children.
6) In a non empty binary tree, if n is the total number of nodes and e is the total
number of edges, then e = n-1
Kth Smallest Element In Tree
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param A : root node of tree
# @param B : integer
# @return an integer
def kthsmallest(self, A, B):
left_branch = []
while A:
left_branch.append(A)
A = A.left
for _ in range(B):
rtn = left_branch.pop()
node = rtn.right
while node:
left_branch.append(node)
node = node.left
return rtn.val
Burn a Tree
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param A : root node of tree
# @param B : integer
# @return an integer
def solve(self, A, B):
def bottom_up(node, starting):
if not node: return 0, False # think 2 nodes total:
root -> initial
if node.val == starting: return 1, True # initial leaf; leaaf
always return 1
time_left, burn_left = bottom_up(node.left, starting)
time_right, burn_right = bottom_up(node.right, starting)
burn = burn_left or burn_right # if not include
initial burn leaf:
if not burn: return 1 + max(time_left, time_right), False # return
subtree depth
curr = time_left + time_right # initial leaf to curr + other
side depth
if self.time < curr: self.time = curr # need check each nodes in
main_path !!!
return 1 + (time_left if burn_left else time_right), True
import sys
sys.setrecursionlimit(10**4) # as 2 <= number of nodes <= 10 ^ 5
self.time = 0
bottom_up(A, B) # A: root, B: initial leaf
return self.time
Max Depth of Binary Tree
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param A : root node of tree
# @return an integer
def maxDepth(self, A):
if not A:
return 0
return 1 + max(self.maxDepth(A.left), self.maxDepth(A.right))
Sorted Array To Balanced BST
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param A : tuple of integers
# @return the root node in the tree
def sortedArrayToBST(self, A):
if len(A) == 0:
return None
mid = len(A)/2
root = TreeNode(A[mid])
root.left = self.sortedArrayToBST(A[:mid])
root.right = self.sortedArrayToBST(A[mid+1:])
return root
# A function to do inorder tree traversal
def printInorder(root):
if root:
# First recur on left child
printInorder(root.left)
# then print the data of node
print(root.val),
# now recur on right child
printInorder(root.right)
# A function to do postorder tree traversal
def printPostorder(root):
if root:
# First recur on left child
printPostorder(root.left)
# the recur on right child
printPostorder(root.right)
# now print the data of node
print(root.val),
# A function to do preorder tree traversal
def printPreorder(root):
if root:
# First print the data of node
print(root.val),
# Then recur on left child
printPreorder(root.left)
# Finally recur on right child
printPreorder(root.right)
DFS and BFS :
def dfs(self, node, par = None):
if node:
node.par = par
self.dfs(node.left, node)
self.dfs(node.right, node)
def bfs(self, src, x):
if(src):
if(src.val == x):
self.target = src
self.bfs(src.left, x)
self.bfs(src.right, x)
vertical traversal of nodes
class Solution:
# @param A : root node of tree
# @return a list of list of integers
def verticalOrderTraversal(self, A):
if A == None:
return []
queue = [(A,0)]
ans = {} # dict x -> [values] for current level
# Iterate by level, so values are properly stacked.
while queue:
queue2 = []
for node, x in queue:
ans.setdefault(x,[]).append(node.val)
if node.left is not None:
queue2.append((node.left, x-1))
if node.right is not None:
queue2.append((node.right, x+1))
queue = queue2
return [ans[x] for x in sorted(ans.keys())]
Get the path to the node from the root:
def getPath(self,root, value):
if root==None:
return []
if root.val == value :
return [root]
left = self.getPath(root.left, value)
right = self.getPath(root.right, value)
if right:
return [root] + right
if left:
return [root] + left
return []
Diagnol traversal:
select a node and store its left child node and add go towards right leaf node
class Solution:
# @param A : root node of tree
# @return a list of integers
def solve(self, A):
res = []
roots = [A]
while len(roots)>0:
new_roots = []
for node in roots:
while node is not None:
new_roots.append(node.left)
res.append(node.val)
node = node.right
roots = new_roots
return res
Right view of Binary tree
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param A : root node of tree
# @return a list of integers
def solve(self, A):
result = []
previous = [A]
while previous:
result.append(previous[-1].val)
current = []
for node in previous:
if node.left:
current.append(node.left)
if node.right:
current.append(node.right)
previous = current
return result
