Rainwater trials

brackets.py

pairs = {
    ")": "(",
    "}": "{",
    "]": "[",
}

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in pairs.values():
                stack.append(c)
            else:
                try:
                    if stack.pop() != pairs[c]:
                        return False
                except IndexError:
                    return False

        return len(stack) == 0
        

set_matrix_zeros.py

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        columns = set()
        rows = set()
        
        for row_index, row in enumerate(matrix):
            for col_index, value in enumerate(row):
                if value == 0:
                    columns.add(col_index)
                    rows.add(row_index)
                
        for row_index, row in enumerate(matrix):
            for col_index, _ in enumerate(row):
                if row_index in rows or col_index in columns:
                    matrix[row_index][col_index] = 0
                    
                    

solution1.py

class Solution1:
    def trap(self, heights: list[int]) -> int:       
        lefts = {}  # {0:0, 1: 1, 2: 3, }
        rights = {}  # {0:N, 1: N-1}
        left = 0
        right = len(heights) - 1
        while left < len(heights):
            add_bounds(heights[left], lefts, left)
            add_bounds(heights[right], rights, right)
            left += 1
            right -= 1
            
        water = 0
        level = 1
        while level in lefts and level in rights:
            for i in range(lefts[level], rights[level] + 1):
                if heights[i] < level:
                    water += 1
            
            level += 1
            
        return water
    
def add_bounds(level, bounds, index):
    for i in range(level + 1):
        if i not in bounds:
            bounds[i] = index

solution2.py

class Solution:
    def trap(self, heights: list[int]) -> int:
        lefts = [0] * len(heights)
        rights = [0] * len(heights)
        
        lefts[0] = heights[0]
        for index in range(1, len(heights)):
            lefts[index] = max(heights[index], lefts[index - 1])
        
        rights[-1] = heights[-1]
        for index in range(len(heights) - 2, 0, -1):
            rights[index] = max(heights[index], rights[index + 1])
            
        water = 0
        for index, height in enumerate(heights):
            max_height = min(lefts[index], rights[index])
            water += max(max_height - height, 0)
            
        return water

time_to_buy.py

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = prices[0]
        max_profit = 0
        for price in prices:
            max_profit = max(max_profit, price - min_price)
            min_price = min(min_price, price)
        return max_profit

trie.py

from dataclasses import dataclass, field

@dataclass
class Node:
    children: dict[str, "Node"] = field(default_factory=dict)
    final: bool = False
        

class Trie:
    def __init__(self):
        self.root = Node()     

    def insert(self, word: str) -> None:
        node = self.root
        for letter in word:
            if letter in node.children:
                node = node.children[letter]
            else:
                new_node = Node()
                node.children[letter] = new_node
                node = new_node 
        node.final = True

    def search(self, word: str) -> bool:
        node = self.root
        for letter in word:
            if letter in node.children:
                node = node.children[letter]
            else:
                return False
        return node.final

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for letter in prefix:
            if letter in node.children:
                node = node.children[letter]
            else:
                return False
        return True
        


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

validate_bst.py

import math
# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        values = []
        self._visit_node(root, values)
        for i in range(len(values) - 1):
            if values[i] >= values[i+1]:
                return False
        return True
        
    def _visit_node(self, node: Optional[TreeNode], values):
        if node is not None:
            self._visit_node(node.left, values)
            values.append(node.val)
            self._visit_node(node.right, values)
            
   
class Solution2:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        return self._check_tree(root.left, root.val, -math.inf) and self._check_tree(root.right, math.inf, root.val)
        
    def _check_tree(
        self, node: Optional[TreeNode], maximum: int, minimum: int
    ) -> bool:
        if node is None:
            return True
        if node.val >= maximum or node.val <= minimum:
            return False
        return self._check_tree(node.left, node.val, minimum) and self._check_tree(node.right, maximum, node.val)