Own-YT Flashcards
LCA binary tree III. Given binary tree with references to left, right, and parents, find LCA of the two given nodes in binary tree
(similar solution to intersection of two linked lists)
def lowestCommonAncestor(self, a: 'Node', b: 'Node') -> 'Node':
pointerA, pointerB = a, b
while pointerA != pointerB:
pointerA = pointerA.parent if pointerA else b
pointerB = pointerB.parent if pointerA else a
return pointerAFind the Celebrity
Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.
Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.
Input:
2 // next n * (n - 1) lines
0 knows 1
1 does not know 0
Output: 1
Explanation:
Everyone knows 1,and 1 knows no one.
"""
The knows API is already defined for you.
@param a, person a
@param b, person b
@return a boolean, whether a knows b
you can call Celebrity.knows(a, b)
"""
class Solution:
# @param {int} n a party with n people
# @return {int} the celebrity's label or -1
def findCelebrity(self, n):
candidate = 0
#Step 1: Find the potential candidate as celebrity
for i in range(1, n):
#If knows, no longer can be candidate, so update new potential candidate
if Celebrity.knows(candidate, i):
candidate = i
#Step 2: Check that the candidate doesn't know anyone, and that everyone knows this candidate
#So if candidate knows someone, OR somehow doesn't know this candidate, then return -1
for i in range(n):
if i == candidate:
continue
if Celebrity.knows(candidate, i) or not Celebrity.knows(i, candidate):
return -1
return candidate
#O(n)
#O(1)Buildings With an Ocean View
Given an array of integers heights of length n, indicating that there are n buildings, heights[i] represents the height of the building at the corresponding position.
To the right of a building is the ocean, and for each building, if all buildings to the right of that building are strictly lower than it, then that building has a view of the ocean.
Returns a list of indexed subscripts of all buildings with an ocean view, in ascending order, with index subscripts starting at 0.
Input:
heights = [5, 2, 3, 4]
Output:
[0, 3]
Explanation:
Building No.1 is 2 in height and Building No.2 is 3 in height and is not strictly higher than the building to its right
from typing import (
List,
)
class Solution:
"""
@param heights: An integer array
@return: Indexs of buildings with sea view
"""
def find_buildings(self, heights: List[int]) -> List[int]:
# write your code here
res = []
maxHeight = -1
for i in range(len(heights) -1, -1, -1):
if heights[i] > maxHeight:
res.append(i)
maxHeight = heights[i]
return res[::-1]
#O(n)
#O(n) #resNumber of Visible People in a Queue
There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.
A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], …, heights[j-1]).
Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.
Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.
class Solution:
def canSeePersonsCount(self, heights: List[int]) -> List[int]:
res = [0] * len(heights)
stack = []
#stack will always include current height
#as long as I am taller than the people in the stack, I will pop and increment visible
#stack is thus monotonically increasing. we always pop smaller heights away,
#so each time we push onto stack it gets larger.
visible = 0
for i in range(len(heights) - 1, -1, -1):
while stack and heights[i] > stack[-1]:
stack.pop()
visible += 1
#Can see the last person who's taller than me
if stack:
visible += 1
res[i] = visible
stack.append(heights[i])
visible = 0 #reset visible
return res
#O(n)
#O(n)
Range Sum of BST
Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.
# 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 rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
res = 0
def dfs(root):
nonlocal res
if not root:
return
if low <= root.val <= high:
res += root.val
dfs(root.left)
dfs(root.right)
dfs(root)
return res
#O(n)
#O(h)Custom Sort String
You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.
Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.
Return any permutation of s that satisfies this property.
Input: order = “cba”, s = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in order, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in order, it can be at any position in the returned string. “dcba”, “cdba”, “cbda” are also valid outputs.
class Solution:
def customSortString(self, order: str, s: str) -> str:
counts = Counter(s)
res = []
for c in order:
if c in counts:
res.append(counts[c] * c)
del counts[c]
for c, count in counts.items():
res.append(c * count)
return "".join(res)
#O(n)
#O(n)Transpose Matrix
Given a 2D integer array matrix, return the transpose of matrix.
The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
ROWS, COLS = len(matrix), len(matrix[0])
res = [[0] * ROWS for r in range(COLS)]
for r in range(ROWS):
for c in range(COLS):
res[c][r] = matrix[r][c]
return res
#O(mn)
#O(mn)
Lowest Common Ancestor V
Given a binary tree with a root node root and an array nodes of objects of class TreeNode, you need to find the Lowest Common Ancestor (LCA, Lowest Common Ancestor) of all nodes in nodes and return it.
Where all the nodes in nodes exist in that binary tree and all the nodes in the binary tree have different values from each other.
root = {3,5,1,6,2,0,8,#,#,7,4}
nodes = [4,7]
2
from typing import (
List,
)
from lintcode import (
TreeNode,
)
"""
Definition of TreeNode:
class TreeNode:
def \_\_init\_\_(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root node of a binary tree.
@param nodes: An array of objects of class TreeNode.
@return: The lowest common ancestor of nodes.
"""
def lowest_common_ancestor(self, root: TreeNode, nodes: List[TreeNode]) -> TreeNode:
# --- write your code here ---
nodeSet = set(nodes)
def dfs(root):
if not root:
return
if root in nodeSet:
return root
leftSubtree = dfs(root.left)
rightSubtree = dfs(root.right)
if leftSubtree and rightSubtree:
return root
return leftSubtree or rightSubtree
return dfs(root)
#O(n)
#O(n) #for nodeSetDiagonal Traverse
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
ROWS, COLS = len(mat), len(mat[0])
up = True
res = []
curR, curC = 0, 0
while len(res) < ROWS * COLS:
if up:
while curR >= 0 and curC < COLS:
res.append(mat[curR][curC])
curR -= 1
curC += 1
if curC == COLS:
curR += 2
curC -= 1
else:
curR += 1
up = False
else:
while curR < ROWS and curC >= 0:
res.append(mat[curR][curC])
curR += 1
curC -= 1
if curR == ROWS:
curR -= 1
curC += 2
else:
curC += 1
up = True
return res
#O(mn)
#O(mn) or O(1) if not count result
Angle Between Hands of a Clock
Given two numbers, hour and minutes, return the smaller angle (in degrees) formed between the hour and the minute hand.
Answers within 10-5 of the actual value will be accepted as correct.
Input: hour = 12, minutes = 30
Output: 165
class Solution:
def angleClock(self, hour: int, minutes: int) -> float:
#360 degrees / 60 minutes * m minutes -> degrees in minutes
#Hours: base hour hand + how much we move between the hour hands
#360 degrees / 12 hours * h hours + (30 degrees / 1 hour) * (1 hour / 60 minutes) * (m minutes)
minutesDeg = 360 / 60 * minutes
hoursDeg = (360 / 12) * hour + (30 / 60) * minutes
diff = abs(hoursDeg - minutesDeg)
return min(diff, 360 - diff)
#O(1)
#O(1)Binary Tree Vertical Order Traversal
Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).
Input: {3,9,8,4,0,1,7}
Output: [[4],[9],[3,0,1],[8],[7]]
from typing import (
List, collections
)
from lintcode import (
TreeNode
)
"""
Definition of TreeNode:
class TreeNode:
def \_\_init\_\_(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of tree
@return: the vertical order traversal
"""
def vertical_order(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
# write your code here
minX, maxX = float('inf'), -float('inf')
q = collections.deque() #node, X value
q.append([root, 0])
xMap = collections.defaultdict(list) #maps x value to the nodes that fall under it
while q:
curNode, curX = q.popleft()
xMap[curX].append(curNode.val)
minX = min(minX, curX)
maxX = max(maxX, curX)
if curNode.left:
q.append([curNode.left, curX - 1])
if curNode.right:
q.append([curNode.right, curX + 1])
res = []
for x in range(minX, maxX + 1):
res.append(xMap[x])
return res
#O(n)
#O(n)
Find Leaves of Binary Tree
Given a binary tree, collect a tree’s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.
Input: {1,2,3,4,5}
Output: [[4, 5, 3], [2], [1]].
Explanation:
import collections
"""
Definition of TreeNode:
class TreeNode:
def \_\_init\_\_(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: the root of binary tree
@return: collect and remove all leaves
"""
def findLeaves(self, root):
#returns the layer that should be the parent's layer.
#If null, will return 0
#If leaf node, will PROCESS nodes at layer 0 (stores as layer 0) which is the max
#of children max(0, 0)
#THEN, returns to parent as layer 1. This means parent will process at layer 1
res = collections.defaultdict(list)
def dfs(root, layer):
if not root:
return 0
leftLayer = dfs(root.left, layer)
rightLayer = dfs(root.right, layer)
#Max: see the node example. Want the 1 to be layer 3
layer = max(leftLayer, rightLayer)
res[layer].append(root.val)
return layer + 1
dfs(root, 0)
#Lintcode weird stuff. Normally return res.values() works.
finalRes = []
for k, v in res.items():
finalRes.append(v)
return finalRes
#O(n)
#O(n)Add Bold Tag in String
Given a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.
Input:
s = “abcxyz123”
dict = [“abc”,”123”]
Output:
“<b>abc</b>xyz<b>123</b>”
from typing import (
List,
)
class Solution:
"""
@param s: a string
@param dict: a list of strings
@return: return a string
"""
def add_bold_tag(self, s: str, dict: List[str]) -> str:
# write your code here
boldStatus = [False] * len(s)
for word in dict:
for i in range(0, len(s) - len(word) + 1): #Python exclusion
if s[i: i + len(word)] == word:
for j in range(i, i + len(word)):
boldStatus[j] = True
res = []
i = 0
while i < len(s):
if boldStatus[i]:
res.append("<b>")
while i < len(s) and boldStatus[i]:
res.append(s[i])
i += 1
res.append("</b>")
else:
res.append(s[i])
i += 1
return "".join(res)
#O(n * w * avg length of w)
#O(n)Closest Binary Search Tree Value II
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Input:
{3,1,4,#,2}
0.275000
2
Output:
[1,2]
Explanation：
Binary tree {3,1,4,#,2}, denote the following structure:
3
/ \
1 4
\
2
from typing import (
List,
)
from lintcode import (
TreeNode,
)
import collections
"""
Definition of TreeNode:
class TreeNode:
def \_\_init\_\_(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the given BST
@param target: the given target
@param k: the given k
@return: k values in the BST that are closest to the target
we will sort your return value in output
"""
def closest_k_values(self, root: TreeNode, target: float, k: int) -> List[int]:
# write your code here
q = collections.deque([])
def dfs(root):
if not root:
return
dfs(root.left)
#middle stuff
if len(q) < k:
q.append(root.val)
else:
if abs(q[0] - target) >= abs(target - root.val):
q.popleft()
q.append(root.val)
else:
return
dfs(root.right)
dfs(root)
#Lintcode stuff.. should be able to return q normally
res = []
for val in q:
res.append(val)
return res
#O(n)
#O(n)Minimum Area Rectangle
You are given an array of points in the X-Y plane points where points[i] = [xi, yi].
Return the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes. If there is not any such rectangle, return 0.
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
pointSet = set()
for x, y in points:
pointSet.add((x, y))
res = float('inf')
for i in range(len(points)):
x1, y1 = points[i]
for j in range(i + 1, len(points)):
x2, y2 = points[j]
if x1 != x2 and y1 != y2 and (x2, y1) in pointSet and (x1, y2) in pointSet:
res = min(res, abs((x2 - x1) * (y2 - y1)))
return res if res != float('inf') else 0
#O(n ** 2)
#O(n)
