nma

class Solution:
    
    def combine(self, n: int, k: int) -> List[List[int]]:
        nums = list(range(1, n + 1))
        combinations = [[]]
        
        for depth in range(0, k):
            new_combinations = []
            for combo in combinations:
                start_index = nums.index(combo[-1]) + 1 if len(combo) > 0 else 0

nma

class Solution:
    
    def permute(self, nums: List[int]) -> List[List[int]]:
        permutations = [[]]
    
        for choice in nums:
            new_permutations = []
            for perm in permutations:
                perm.append(choice)
                for j in range(len(perm)):

nma

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        
        low_price = prices[0]
        max_profit = 0
        
        for i in range(1, len(prices)):
            if prices[i] > low_price:

nma

@startuml
' uncomment the line below if you're using computer with a retina display
' skinparam dpi 300
!define Table(name,desc) class name as "desc" << (T,#FFAAAA) >>
' we use bold for primary key
' green color for unique
' and underscore for not_null
!define primary_key(x) <b>x</b>
!define unique(x) <color:green>x</color>
!define not_null(x) <u>x</u>

nma

from dataclasses import dataclass

@dataclass
class TraversalRecord:
  seen_nodes: int
  ancestor: BinaryTreeNode


def post_order_traversal_helper(node: BinaryTreeNode, n1: BinaryTreeNode, n2: BinaryTreeNode) -> TraversalRecord:
  '''

nma

def find_lca(n1: BinaryTreeNode, n2: BinaryTreeNode) -> BinaryTreeNode:
  def get_depth(node: BinaryTreeNode) -> int:
    depth = 0
    while node and node.parent:
      node = node.parent
      depth += 1
    return depth
  
  d1 = get_depth(n1)
  d2 = get_depth(n2)

nma

# n1.data <= n2.data
def find_lca(tree: BstNode, n1: BstNode, n2: BstNode) -> Optional[BstNode]:
  while tree:
    # both left and right child are greater than current node
    if n1.data > tree.data and n2.data > tree.data:
      tree = tree.right
    
    # both left and right child are less than the current node
    elif n1.data < tree.data and n2.data < tree.data:
      tree = tree.left

nma

def find_lca(n1: BinaryTreeNode, n2: BinaryTreeNode) -> Optional[BinaryTreeNode]:
  seen_on_path: Set[BinaryTreeNode] = set()
    
  while n1 or n2:
    # go up the tree at the same time
    
    if n1:
      # at every point check if we have already seen the node
      if n1 in seen_on_path:
        # first seen will be an ancestor

nma

def rob_houses(house: Tuple[int]) -> int:
   if len(house) == 0: return 0 
   if len(house) == 1: return house[0]

   criminal_gains = max(
      rob_houses(house[1:]),
      house[1] + rob_houses(house[2:])
   )

   return criminal_gains

nma

def rob_houses_mem(house: Tuple[int], mem: Dict[int, int]) -> int:
    if len(house) == 0: return 0 
    if hash(house) in mem:
        return mem[hash(house)]
    
    criminal_gains = max(
        rob_houses(house[1:], mem),
        house[1] + rob_houses(house[2:], mem)
    )