commit 69371fbc320a52a080ef462ffc2148fbeb2102b4
parent 618aeaf7949007df444f6f73de0c0a2c85fcd097
Author: Andrew Laack <andrew@laack.co>
Date: Mon, 30 Jun 2025 10:30:19 -0500
Finished more problems. The problems were primarily tree problems.
Diffstat:
9 files changed, 269 insertions(+), 0 deletions(-)
diff --git a/binary-tree-level-order-traversal/trav.py b/binary-tree-level-order-traversal/trav.py
@@ -0,0 +1,27 @@
+from collections import deque
+class Solution:
+ def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
+
+ if root is None:
+ return []
+
+ results = []
+ queue = deque()
+ queue.append(root)
+ layer = 0
+
+ while queue:
+
+ queue_size = len(queue)
+ results.append([])
+
+ for i in range(0, queue_size):
+ current = queue.popleft()
+
+ if not current.left is None:
+ queue.append(current.left)
+ if not current.right is None:
+ queue.append(current.right)
+ results[layer].append(current.val)
+ layer += 1
+ return results
diff --git a/binary-tree-right-side-view/binary-tree-right-side-view.py b/binary-tree-right-side-view/binary-tree-right-side-view.py
@@ -0,0 +1,31 @@
+from collections import deque
+# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
+
+ if root is None:
+ return []
+
+ queue = deque()
+ queue.append(root)
+ layer = 0
+ result = []
+
+ while queue:
+ length = len(queue)
+ result.append([])
+ for i in range(0, length):
+ current = queue.popleft()
+ result[layer].append(current.val)
+ if current.left is not None:
+ queue.append(current.left)
+ if current.right is not None:
+ queue.append(current.right)
+ layer += 1
+
+ return [x[-1] for x in result]
diff --git a/combination-sum/combination-sum.py b/combination-sum/combination-sum.py
@@ -0,0 +1,32 @@
+class Solution:
+ def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
+ searched = set()
+ return make_combinations([], candidates, target, searched)
+
+def make_combinations(current, candidates, target, searched):
+
+ current.sort()
+
+ if str(current) in searched:
+ return None
+ else:
+ searched.add(str(current))
+
+ if sum(current) == target:
+ return [current]
+
+ if sum(current) > target:
+ return None
+
+ ret_ls = []
+
+ for i in range(0, len(candidates)):
+ copy_ls = current.copy()
+ copy_ls.append(candidates[i])
+ all_others = make_combinations(copy_ls, candidates, target, searched)
+
+
+ if all_others is not None:
+ ret_ls.extend(all_others)
+
+ return ret_ls
diff --git a/combination-sum/combination-sumV2.py b/combination-sum/combination-sumV2.py
@@ -0,0 +1,24 @@
+class Solution:
+ def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
+ candidates.sort()
+ return combine(candidates, target, [], 0)
+
+def combine(candidates, target, current, left_ptr):
+
+ if target == 0:
+ return [current]
+
+ current_index = left_ptr
+ results = []
+
+ while current_index < len(candidates) and candidates[current_index] <= target:
+
+ cp_ls = current.copy()
+ cp_ls.append(candidates[current_index])
+ with_current = combine(candidates, target - candidates[current_index], cp_ls, current_index)
+ current_index += 1
+
+ for ans in with_current:
+ results.append(ans)
+
+ return results
diff --git a/count-good-nodes-in-binary-tree/count-good.py b/count-good-nodes-in-binary-tree/count-good.py
@@ -0,0 +1,29 @@
+# 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
+
+# basic dfs problem
+ # pass forwards largest seen
+ # if > largest seen update largest seen and increment counter
+ # else continue with children
+
+class Solution:
+ def goodNodes(self, root: TreeNode) -> int:
+ return dfs_count_good(root, -100000)
+
+def dfs_count_good(root, highest_val) -> int:
+
+ if root is None:
+ return 0
+
+ new_high = max(root.val, highest_val)
+ left = dfs_count_good(root.left, new_high)
+ right = dfs_count_good(root.right, new_high)
+
+ if root.val >= highest_val:
+ return left + right + 1
+ else:
+ return left + right
diff --git a/find-longest-harmonious-subsequence/find-longest.py b/find-longest-harmonious-subsequence/find-longest.py
@@ -0,0 +1,26 @@
+class Solution:
+ def findLHS(self, nums: List[int]) -> int:
+
+ counts = {}
+
+ for num in nums:
+ if num in counts:
+ counts[num] += 1
+ else:
+ counts[num] = 1
+
+
+ max_len = 0
+
+ for key in counts:
+ if key - 1 in counts:
+ current = counts[key - 1] + counts[key]
+ if current > max_len:
+ max_len = current
+
+ if key + 1 in counts:
+ current = counts[key + 1] + counts[key]
+ if current > max_len:
+ max_len = current
+
+ return max_len
diff --git a/find-longest-harmonious-subsequence/find-longestV2.py b/find-longest-harmonious-subsequence/find-longestV2.py
@@ -0,0 +1,26 @@
+class Solution:
+ def findLHS(self, nums: List[int]) -> int:
+
+ counts = {}
+
+ for num in nums:
+ if num in counts:
+ counts[num] += 1
+ else:
+ counts[num] = 1
+
+
+ max_len = 0
+
+ for key in counts:
+ if key - 1 in counts:
+ current = counts[key - 1] + counts[key]
+ if current > max_len:
+ max_len = current
+
+ if key + 1 in counts:
+ current = counts[key + 1] + counts[key]
+ if current > max_len:
+ max_len = current
+
+ return max_len
diff --git a/kth-smallest-element-in-a-bst/kth-smallest.py b/kth-smallest-element-in-a-bst/kth-smallest.py
@@ -0,0 +1,38 @@
+# 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
+
+
+# IDEA:
+
+# Perform DFS:
+ # go all the way to the left
+ # decrement smallest counter value
+ # if smallest counter value == 0:
+ # return current value
+
+class Solution:
+ def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
+ return dfs_kth(root, [k])
+
+def dfs_kth(root, val):
+
+ if root is None:
+ return None
+
+ left_found = dfs_kth(root.left, val)
+
+ if left_found is not None:
+ return left_found
+
+ val[0] -= 1
+
+ if val[0] == 0:
+ return root.val
+
+ right_found = dfs_kth(root.right,val)
+
+ return right_found
diff --git a/validate-binary-search-tree/validate-binary-search-tree.py b/validate-binary-search-tree/validate-binary-search-tree.py
@@ -0,0 +1,36 @@
+# IDEAS:
+
+# 1) Perform in-order traversal then verify ordering of the result
+ # TIME: O(n) SPACE: O(n)
+
+class Solution:
+ def isValidBST(self, root: Optional[TreeNode]) -> bool:
+
+ if root is None:
+ return True
+
+ in_order = dfs_in_order(root)
+
+ for i in range(0, len(in_order) - 1):
+ if in_order[i] >= in_order[i+1]:
+ return False
+ return True
+
+# Return a list of nodes
+def dfs_in_order(root):
+
+ if root is None:
+ return None
+
+ left = dfs_in_order(root.left)
+ if left is not None:
+ left.append(root.val)
+ else:
+ left = [root.val]
+
+ right = dfs_in_order(root.right)
+
+ if right is not None:
+ left.extend(right)
+
+ return left
