solve

problem

This was the first problem I did that I needed a bit of help, but once I saw that max_path state should be kept as a global variable, it made the coding much easier. I also needed the hint for max(left, 0); 0 implying that we don't take the left.

Will need to review this problem.

from typing import Optional
# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_path = -1001
        self.dfs(root)
        return self.max_path
    
    # returns maxEdge
    def dfs(self, node) -> int:

        if not node:
            return 0

        left = max(self.dfs(node.left), 0)
        right = max(self.dfs(node.right), 0)
        self.max_path = max(self.max_path, left + right + node.val)
        
        return max(left + node.val, right + node.val)

problem

Same as the last problem. We only want to add when there's no left or right node. State is kept by function.

from typing import Optional
# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)
    
    def dfs(self, node, currSum) -> int:

        if node == None:
            return 0
        
        if node.left == None and node.right == None:
            return int(str(currSum) + str(node.val))
        
        else:
            currSum = str(currSum) + str(node.val)
            return self.dfs(node.left, currSum) + self.dfs(node.right, currSum)

Problem

DFS, simple question: only check when we are at a leaf node (somehow my solution was top 99% in terms of both time and space complexity)

from typing import Optional
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        return self.dfs(root, currSum=0, targetSum=targetSum)

    def dfs(self, root, currSum, targetSum) -> bool:

        if not root:
            return False
        
        if not root.left and not root.right:
            if root.val + currSum == targetSum:
                return True

        else:
            currSum = root.val + currSum
            return self.dfs(root.left, currSum, targetSum) or self.dfs(root.right, currSum, targetSum)

problem

I understand the solution but it's a bit difficult for me to come up on the spot. Need review.

from typing import Optional
# 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 flatten(self, root: Optional[TreeNode]) -> None:
        self.dfs(root)
    
    def dfs(self, root):
        if not root:
            return None
        
        left = self.dfs(root.left)
        right = self.dfs(root.right)

        if left:
            left.right = root.right
            root.right = root.left
            root.left = None
        
        if right:
            return right
        elif left:
            return left
        return root

Still taking it easy. It's a binary tree week and just taking it easy because I'm tired.

problem

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root):
        self.process_row([root])
        return root
    
    def process_row(self, row_list):
        next_row = []
        for n in row_list:
            if n == None:
                continue
            if n.left:
                next_row.append(n.left)
            if n.right:
                next_row.append(n.right)
        
        if not next_row:
            return

        for i, n in enumerate(next_row[:len(next_row)-1]):
            n.next = next_row[i+1]

        self.process_row(next_row)

It's MLK day, here's some more binary tree questions

preorder and inorder: problem

from typing import Optional
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

        if not preorder:
            return None

        val = preorder[0]

        split_index = -1
        for i, v in enumerate(inorder):
            if v == val:
                split_index = i

        left_preorder = preorder[1:1+split_index]
        right_preorder = preorder[1+split_index:]
        left_inorder = inorder[0:split_index]
        right_inorder = inorder[split_index+1:]

        return TreeNode(
            val = val,
            left = self.buildTree(left_preorder, left_inorder),
            right = self.buildTree(right_preorder, right_inorder)
        )

inorder and postorder: problem

from typing import Optional
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        val = postorder[-1]
        split_index = -1
        for i, v in enumerate(inorder):
            if v == val:
                split_index = i
        left_inorder = inorder[0:split_index]
        right_inorder = inorder[split_index+1:]
        left_postorder = postorder[0:split_index]
        right_postorder = postorder[split_index:len(postorder)-1]

        return TreeNode(
            val=val,
            left=self.buildTree(left_inorder, left_postorder),
            right=self.buildTree(right_inorder, right_postorder)
        )

It's still the weekend so taking it easy. Some binary tree questions.

problem

from typing import Optional
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.is_mirror(root.left, root.right)
    
    def is_mirror(self, p, q):
        if p is None and q is None:
            return True
        elif p is not None and q is None:
            return False
        elif p is None and q is not None:
            return False
        # elif p is not None and q is not None:
        if p.val != q.val:
            return False
        
        return self.is_mirror(p.right, q.left) and self.is_mirror(p.left, q.right)

problem

from typing import Optional
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return None
        placeholder = root.left
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(placeholder)
        return root

The next few problems these days are all going to be binary tree problems. Starting off easy because it's the weekend

problems

from typing import Optional
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0

        return max(1 + self.maxDepth(root.left), 1 + self.maxDepth(root.right))

problem

from typing import Optional
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p and q:
            return False
        if p and not q:
            return False
        if p and q:
            if p.val != q.val:
                return False
        
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

problem

This week is just sliding window questions. Not a hard problem to conceptualize: two pointers and a hash table to keep state. However, took me a while to code it out / was stuck on an edge case.

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target_dict = Counter(t)
        target_sum = sum(target_dict.values())
        curr_sum = 0
        curr_dict = {}
        p1 = 0
        p2 = -1

        curr_min_substring_length = len(s) + 1
        curr_min_substring = s

        while True:

            # we want to move p2 because we haven't hit our target_dict yet
            if curr_sum < target_sum:
                p2 = p2 + 1

                if p2 >= len(s):
                    break

                last_char = s[p2]
                if target_dict.get(last_char):
                    if curr_dict.get(last_char):
                        curr_dict[last_char] = curr_dict[last_char] + 1
                    else:
                        curr_dict[last_char] = 1
                
                    if target_dict[last_char] >= curr_dict[last_char]:
                        curr_sum = curr_sum + 1
            
            # we want to move p1 because we have hit our target
            else: # curr_sum == target_sum

                if p2 - p1 + 1 < curr_min_substring_length:
                    curr_min_substring = s[p1:p2+1]
                    curr_min_substring_length = p2 - p1 + 1

                first_char = s[p1]
                if target_dict.get(first_char):
                    curr_dict[first_char] = curr_dict[first_char] - 1
                    
                    if target_dict[first_char] > curr_dict[first_char]:
                        curr_sum = curr_sum - 1
                
                p1 = p1 + 1
                
                if p1 > p2:
                    p1 = p1 - 1
                    continue

                while target_dict.get(s[p1]) == None:
                    if curr_sum == target_sum:
                        if p2 - p1 + 1 < curr_min_substring_length:
                            curr_min_substring = s[p1:p2+1]
                            curr_min_substring_length = p2 - p1 + 1
                    p1 = p1 + 1

        if curr_min_substring_length == len(s) + 1:
            return ""
        
        return curr_min_substring

problem

This week is just sliding window questions.

Confusing wording. Can be optimized to actually use “pointers” and actually be a sliding window problem, but that requires more work and I'm lazy (go through the array len(words[0)] time and in each time, removing the last one and adding the next one, etc.). Good enough...

from collections import Counter

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        
        target_map = Counter(words)
        single_word_length = len(words[0])
        words_length = len(words)
        concat_total_length = words_length * single_word_length
        solution = []

        if concat_total_length > len(s):
            return solution

        for k in range(0, single_word_length):
            for i in range(0, len(s)):

                concat_word = s[i:i+concat_total_length]
                curr_map = {}

                for j in range(0, words_length):
                    word = concat_word[j*single_word_length : (j+1) * single_word_length]
                    if curr_map.get(word):
                        curr_map[word] = curr_map[word] + 1
                    else:
                        curr_map[word] = 1
            
                if curr_map == target_map:
                    solution.append(i)
        
        return solution