ThomasHigginson

def generateMatrix(self, n: int) -> List[List[int]]:
    numLayers = (n+1)//2
    ret = [[0]*n for x in range(0, n)]
    cnt = 1
    for layer in range(0, numLayers):
        # Fill the top row of layer
        for i in range(layer, n-layer):
            ret[layer][i] = cnt
            cnt += 1

ThomasHigginson

def findMin(self, nums: List[int]) -> int:
    if len(nums) == 1 or nums[0] < nums[len(nums)-1]:
        return nums[0] # Our two base cases
    
    left, right = 0, len(nums)-1
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] > nums[mid+1]: # Case 1 Inflection Point
            return nums[mid+1]

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
    

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

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

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

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

# 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

# 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

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)