ThomasHigginson

def maxArea(self, height: List[int]) -> int:
    i = 0
    j = len(height) - 1
    maxArea = -inf
    currMax = -inf
    
    while i < j:
        currMax = min(height[i], height[j]) * (j - i)
        maxArea = max(currMax, maxArea)
        

ThomasHigginson

def threeSum(self, nums: List[int]) -> List[List[int]]:
    if len(nums) < 3: # Requires 3 for a pair of 3
        return []
    elif len(nums) == 3 and sum(nums) == 0: # Naive case; check sum of 3 elements
        return [nums]

    nums = sorted(nums) # O(nlogn)

    solutions = []
    i = 0

ThomasHigginson

def twoSum(self, nums: List[int], target: int) -> List[int]:
    number2Index = {} # Lookup table for observed number to it's index

    # 1. Get a given numbers complement
    # 2. If it's in number2Index, then it's complement
    # exists, and return it's index along with the complement's index
    # 3. Otherwise, add this number as a key, and it's index as the value
    for idx, num in enumerate(nums):
        numComplement = target - num
        if numComplement in number2Index:

ThomasHigginson

# This is the Dynamic Programming Solution/Approach
# Find the tallest left and tallest right for each index, then solve for the
# water each position will add to the total.

def trap(self, height: List[int]) -> int:
    maxLefts, maxRights = [0] * len(height), [0] * len(height)
    
    # init values
    maxLefts[0] = height[0]
    maxRights[len(height)-1] = height[len(height)-1]

ThomasHigginson

# This is the 2 pointer Solution/Approach
# It utilizes the fact that the amount of water a position
# can contain is bounded by the smallest wall to its left and right
# If the left < right, then we KNOW that it can contain whatever
# amount of water with respect to the height of the left wall (the smaller wall).
# and vice versa

def trap(self, height: List[int]) -> int:
    leftMax, rightMax, ans = 0, 0, 0
    left, right = 0, len(height)-1

ThomasHigginson

maxLefts, maxRights = [0] * len(height), [0] * len(height)

# Maxs set to edges
maxLefts[0] = height[0]
maxRights[len(height)-1] = height[len(height)-1]

i, j = 1, len(height)-2
while i < len(height):
    maxLefts[i] = max(maxLefts[i-1], height[i]) # Check this height to max height to left
    maxRights[j] = max(maxRights[j+1], height[j]) # Check this height to max height to right

ThomasHigginson

ans = 0
for i in range(0, len(height)):
    ans += max(0, min(maxLefts[i], maxRights[i]) - height[i]) # Dont want to add negatives

return ans

ThomasHigginson

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: # Base case
            return 0
        
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

ThomasHigginson

# Iterative DFS solution using a stack
def maxDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
        
    stack = [(root, 1)] # (Node, depth of Node)
    maxDepth = 1
    
    while stack:
        node, depth = stack.pop()

ThomasHigginson

# Iterative DFS solution using a stack
def maxDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
        
    dque = deque([root])
    nodes_at_curr_depth = len(dque)
    depth = 1