We denote a string as s
s.split(delimiter)- O(n)s.replace(str1, str2, k)- O(n*k) or O(n) if k is omitted- replaces the first
kinstances ofstr2asstr1 - Note: Since Python strings are immutable, we can delete substrings by doing
s.replace(str1, "", n)
- replaces the first
Let l be a list and k be an integer
l[:k]= start at indexkand go to the endl[-k:]= start from thek-th to last element and go to the end
n = len(nums)
for i in range(n - 1, -1, -1):
print(nums[i]) cnt = Counter(nums)
sorted_cnt = sorted(cnt.items(), key=lambda x : x[1], reverse=True) - rank - position in an in-order traversal
- diameter - length of the longest path between any two nodes in a tree. may or may not pass through the root.
Defined between two nodes, p and q, as the lowest node in T that has both p and q as descendants
- Note: A node can be a descendant of itself
If T is a binary tree
def lca(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root:
return None
if root == p or root == q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right:
return root
return left or rightclass TreeNode:
def __init__(self, val):
self.val = val
self.left = self.right = Noneclass Node:
def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
if children is None:
children = []
self.val = val
self.children = childrenfrom typing import Optional, List
from collections import deque
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
ans = []
while q:
level = []
for i in range(len(q)):
current = q.popleft()
level.append(current.val)
if current.left:
q.append(current.left)
if current.right:
q.append(current.right)
ans.append(level)
return ans- insert - O(log n)
- get min/max - O(1)
- extract min/max - O(log n)
- update - O(log n) if we have the index, else O(n)
- build - O(n)
heapify(iterable)- O(n)heappush(iterable, x)- O(log n)heappop(iterable)- O(log n)heapushpop(iterable, x)- O(log n)nsmallest(k, iterable, key)- O(n log k)nlargest(k, iterable, key)- O(n log k)- k: The number of largest elements to return.
- iterable: The input data we are selecting from.
- key: A function that determines the value to compare when finding the largest elements. Example usage: Top K Largest Elements
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if len(nums) == k:
return nums
cnt = Counter(nums)
return heapq.nlargest(k, cnt.keys(), key=cnt.get)key=cnt.get- Thecnt.getfunction retrieves the frequency count of each key.heapq.nlargest()uses this frequency count to determine the "largest" elements.
Typically represented as an array
- Complete binary tree
- Every level is completely filled, with the exception of the last row, which is filled from left to right
- Heap property
- Min Heap: Each node is less than or equal to its children
- Max Heap: Each node is greater than or equal to its children
For a given node at index i, we can find...
- left child: 2*i+1
- right child: 2*i+2
- parent: (i - 1) // 2
Typically used to solve problems that are "find k something" such as
kth smallest,kth largest,kth most frequent,kth less frequent
- Average case: O(n)
- Worst case: O(n^2)
- Select a pivot and form partitions
- Run the partitioning algorithm only on the side that contains our "top" k-th element
- Any number XORed with itself cancels out
- Useful for this problem: Single Number
- Order of operations does not matter, meaning:
from collections import Counterfrom collections import defaultdict