commit 2e7a99518b0d10618b9c88bf6d6c0379e97874d4 parent 9674c7aad3941e9a17f752674e2db1ee6a32b240 Author: Andrew Laack <andrew@laack.co> Date: Fri, 4 Jul 2025 11:56:34 -0500 Reformatted all files Diffstat:
56 files changed, 367 insertions(+), 308 deletions(-)
diff --git a/3sum/3sum.py b/3sum/3sum.py @@ -12,11 +12,10 @@ class Solution: # how to move the pointers? # left pointer stays in place - # right pointer iterates - + # right pointer iterates def threeSum(self, nums: List[int]) -> List[List[int]]: - + nums.sort() returnLs = [] @@ -29,10 +28,16 @@ class Solution: while right_ptr > left_ptr: - if right_ptr != len(nums) - 1 and nums[right_ptr] == nums[right_ptr + 1]: + if ( + right_ptr != len(nums) - 1 + and nums[right_ptr] == nums[right_ptr + 1] + ): right_ptr -= 1 continue - if left_ptr != current_index + 1 and nums[left_ptr] == nums[left_ptr - 1]: + if ( + left_ptr != current_index + 1 + and nums[left_ptr] == nums[left_ptr - 1] + ): left_ptr += 1 continue @@ -44,17 +49,17 @@ class Solution: right_ptr -= 1 left_ptr += 1 continue - + returnLs.append(cl) added.add(cl_string) if nums[right_ptr - 1] == nums[right_ptr]: right_ptr -= 1 else: - left_ptr += 1 - + left_ptr += 1 + if current_value > inverse: right_ptr -= 1 if current_value < inverse: left_ptr += 1 - + return returnLs diff --git a/3sum/3sumV2.py b/3sum/3sumV2.py @@ -6,19 +6,18 @@ class Solution: # a + b + c = 0 # a_index = 0 # for each a_index: - # b = val at next index - # c = len(nums) - 1 - # for each b,c: - # check if prior b was same - # check if prior c was same - # if either were, test next selection of b,c - # next selection of b,c is where b_index += 1 or c_index -= 1 - # depending on if the current guess is too high or low based on - # a + b + c - + # b = val at next index + # c = len(nums) - 1 + # for each b,c: + # check if prior b was same + # check if prior c was same + # if either were, test next selection of b,c + # next selection of b,c is where b_index += 1 or c_index -= 1 + # depending on if the current guess is too high or low based on + # a + b + c def threeSum(self, nums: List[int]) -> List[List[int]]: - + nums.sort() # a + b + c = 0 @@ -26,7 +25,7 @@ class Solution: # -2 because b_index > a_index and c_index > b_index for a_index in range(0, len(nums) - 2): - + if a_index != 0 and nums[a_index] == nums[a_index - 1]: continue @@ -47,19 +46,19 @@ class Solution: if c_index != len(nums) - 1 and c == nums[c_index + 1]: c_index -= 1 continue - + sumbc = b + c result = sumbc + a - + if result == 0: returnLs.append([a, b, c]) c_index -= 1 b_index += 1 - + if result > 0: c_index -= 1 - + if result < 0: b_index += 1 - + return returnLs diff --git a/add-two-numbers/add-two-numbers.py b/add-two-numbers/add-two-numbers.py @@ -4,9 +4,10 @@ # self.val = val # self.next = next class Solution: - - def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: + def addTwoNumbers( + self, l1: Optional[ListNode], l2: Optional[ListNode] + ) -> Optional[ListNode]: l1Val = convert(l1) l2Val = convert(l2) res = l1Val + l2Val @@ -14,10 +15,11 @@ class Solution: finalLs = revert(res) return finalLs + def revert(num): if num == 0: return ListNode(0) - + retLs = [] while num > 0: toAdd = num % 10 @@ -33,6 +35,7 @@ def revert(num): return base + def convert(l1): vals = "" while l1 != None: diff --git a/balanced-binary-tree/balanced-binary-tree.py b/balanced-binary-tree/balanced-binary-tree.py @@ -2,12 +2,13 @@ class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: return dfs(root) != -1 + # return depth of tree def dfs(root): if root is None: return 0 - + left_depth = dfs(root.left) right_depth = dfs(root.right) diff --git a/binary-search/binary-search.py b/binary-search/binary-search.py @@ -1,6 +1,6 @@ class Solution: def search(self, nums: List[int], target: int) -> int: - + done = False lower = 0 upper = len(nums) - 1 @@ -14,12 +14,12 @@ class Solution: if nums[lower] == target: return lower if nums[upper] == target: - return upper + return upper return -1 if nums[center] == target: return center - + if nums[center] < target: lower = center else: diff --git a/binary-search/binary-searchV2.py b/binary-search/binary-searchV2.py @@ -1,18 +1,19 @@ class Solution: def search(self, nums: List[int], target: int) -> int: - return recursive_binary_search(nums,target, 0, len(nums) - 1) + return recursive_binary_search(nums, target, 0, len(nums) - 1) + def recursive_binary_search(nums, target, lower, upper) -> int: - + if lower > upper: return -1 - + center = ((upper - lower) // 2) + lower - + if nums[center] == target: return center - + new_lower = lower new_upper = upper @@ -20,5 +21,5 @@ def recursive_binary_search(nums, target, lower, upper) -> int: new_lower = center + 1 if nums[center] > target: new_upper = center - 1 - - return recursive_binary_search(nums,target, new_lower, new_upper) + + return recursive_binary_search(nums, target, new_lower, new_upper) diff --git a/binary-tree-level-order-traversal/trav.py b/binary-tree-level-order-traversal/trav.py @@ -1,10 +1,12 @@ 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) @@ -17,7 +19,7 @@ class Solution: 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: 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 @@ -1,4 +1,6 @@ from collections import deque + + # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): @@ -7,7 +9,7 @@ from collections import deque # self.right = right class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: - + if root is None: return [] @@ -27,5 +29,5 @@ class Solution: if current.right is not None: queue.append(current.right) layer += 1 - + return [x[-1] for x in result] diff --git a/combination-sum-ii/combination-sum-ii.py b/combination-sum-ii/combination-sum-ii.py @@ -1,8 +1,9 @@ class Solution: - def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: + def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() return find_all([], target, candidates, 0, set()) + def find_all(current, target, candidates, index, used): if str(current) in used: @@ -16,7 +17,7 @@ def find_all(current, target, candidates, index, used): ret_ls = [] while index < len(candidates) and candidates[index] <= target: - + copy_ls = current.copy() copy_ls.append(candidates[index]) @@ -25,5 +26,5 @@ def find_all(current, target, candidates, index, used): ret_ls.extend(ret) index += 1 - + return ret_ls diff --git a/combination-sum/combination-sum.py b/combination-sum/combination-sum.py @@ -3,10 +3,11 @@ class Solution: 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: @@ -14,7 +15,7 @@ def make_combinations(current, candidates, target, searched): if sum(current) == target: return [current] - + if sum(current) > target: return None @@ -25,7 +26,6 @@ def make_combinations(current, candidates, target, searched): 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) diff --git a/combination-sum/combination-sumV2.py b/combination-sum/combination-sumV2.py @@ -3,11 +3,12 @@ class Solution: candidates.sort() return combine(candidates, target, [], 0) + def combine(candidates, target, current, left_ptr): if target == 0: return [current] - + current_index = left_ptr results = [] @@ -15,9 +16,11 @@ def combine(candidates, target, current, left_ptr): cp_ls = current.copy() cp_ls.append(candidates[current_index]) - with_current = combine(candidates, target - candidates[current_index], cp_ls, 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) diff --git a/count-good-nodes-in-binary-tree/count-good.py b/count-good-nodes-in-binary-tree/count-good.py @@ -6,19 +6,21 @@ # self.right = right # basic dfs problem - # pass forwards largest seen - # if > largest seen update largest seen and increment counter - # else continue with children +# 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) diff --git a/design-add-and-search-words-data-structure/design-add.py b/design-add-and-search-words-data-structure/design-add.py @@ -1,8 +1,9 @@ -class TreeNode(): +class TreeNode: def __init__(self): self.isWord = False self.chars = {} + class WordDictionary: def __init__(self): @@ -18,23 +19,23 @@ class WordDictionary: node = TreeNode() current.chars[char] = node current = current.chars[char] - + current.isWord = True - def search(self, word: str, root = None) -> bool: - + def search(self, word: str, root=None) -> bool: + current = None if root is None: current = self.root else: current = root - + for index, char in enumerate(word): - if char == '.': + if char == ".": for option in current.chars: - test = self.search(word[index + 1:], current.chars[option]) + test = self.search(word[index + 1 :], current.chars[option]) if test: return True return False @@ -44,7 +45,7 @@ class WordDictionary: continue else: return False - + return current.isWord diff --git a/diameter-of-binary-tree/diameter-binary-tree.py b/diameter-of-binary-tree/diameter-binary-tree.py @@ -11,10 +11,11 @@ # Idea: # Find height of left and right at each node. -# Return this up the stack. Incrementing longest as we return. +# Return this up the stack. Incrementing longest as we return. # for each element, we then sum left and right heights and return largest one. + class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: @@ -22,15 +23,17 @@ class Solution: return 0 return get_heights(root)[1] - + + # TUPLE: # [0] is the number of traversals to the bottom # [1] is the max traversals in the tree -def get_heights(node : TreeNode): + +def get_heights(node: TreeNode): if node is None: - return [-1,0] - + return [-1, 0] + left_tuple = get_heights(node.left) right_tuple = get_heights(node.right) @@ -42,4 +45,4 @@ def get_heights(node : TreeNode): current = lh + rh - return max(lh,rh), max(current, left_tuple[1], right_tuple[1]) + return max(lh, rh), max(current, left_tuple[1], right_tuple[1]) diff --git a/even-odd-tree/even-odd-tree.py b/even-odd-tree/even-odd-tree.py @@ -1,10 +1,11 @@ -#even odd tree +# even odd tree -#is only true if even layers are ascending order and odd -#and odd layers are even nums and descending order +# is only true if even layers are ascending order and odd +# and odd layers are even nums and descending order + +# 233ms beats 53.29% +# 60.06MB Beats 5.76% -#233ms beats 53.29% -#60.06MB Beats 5.76% class Solution(object): def isEvenOddTree(self, root): @@ -31,6 +32,7 @@ class Solution(object): layer += 1 return True + def recurse(root, layer, lis): if len(lis) <= layer: lis.append([]) @@ -40,4 +42,3 @@ def recurse(root, layer, lis): if root.right is not None: recurse(root.right, layer + 1, lis) return lis - diff --git a/find-longest-harmonious-subsequence/find-longest.py b/find-longest-harmonious-subsequence/find-longest.py @@ -1,6 +1,6 @@ class Solution: def findLHS(self, nums: List[int]) -> int: - + counts = {} for num in nums: @@ -9,7 +9,6 @@ class Solution: else: counts[num] = 1 - max_len = 0 for key in counts: @@ -17,7 +16,7 @@ class Solution: 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: diff --git a/find-longest-harmonious-subsequence/find-longestV2.py b/find-longest-harmonious-subsequence/find-longestV2.py @@ -1,6 +1,6 @@ class Solution: def findLHS(self, nums: List[int]) -> int: - + counts = {} for num in nums: @@ -9,7 +9,6 @@ class Solution: else: counts[num] = 1 - max_len = 0 for key in counts: @@ -17,7 +16,7 @@ class Solution: 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: diff --git a/find-min-in-rotated-sorted-array/findMin.py b/find-min-in-rotated-sorted-array/findMin.py @@ -1,9 +1,9 @@ class Solution: def findMin(self, nums: List[int]) -> int: - + # IDEA: - # Find the cutoff between low and high values. + # Find the cutoff between low and high values. # Consideration; what happens with a list of all the same values? # Rotated 'n' times to the right, but we don't know n @@ -19,9 +19,9 @@ class Solution: right = len(nums) - 1 while left <= right: - + center = ((right - left) // 2) + left - + if nums[center] > nums[right]: left = center + 1 elif nums[center] > nums[left] or nums[center - 1] < nums[center]: diff --git a/find-original-typed-string-i/find-original-i.py b/find-original-typed-string-i/find-original-i.py @@ -2,41 +2,43 @@ # get the counts of each character # the total number of possible strings is -# the number of 2 selections of characters that result in a +# the number of 2 selections of characters that result in a # different word. # the counting approach likely won't work because it doesn't # handle duplicate strings correctly, as is the case with 'aaa' -# which can only become 'a' or 'aa' but not 'aa' and 'aa'. +# which can only become 'a' or 'aa' but not 'aa' and 'aa'. # recursive approach: - # given the word we create a count branch - # every time the current character is the same as the previous - # at each branch we continue on assuming it is either their or not +# given the word we create a count branch +# every time the current character is the same as the previous +# at each branch we continue on assuming it is either their or not # how do we handle duplicates then? - # to handle duplicate we could memoize but that's slow - # we could also skip any character that is a run - # and then evaluate all unique selections of it at the end - # this runs in linear time and should be simple to do +# to handle duplicate we could memoize but that's slow +# we could also skip any character that is a run +# and then evaluate all unique selections of it at the end +# this runs in linear time and should be simple to do + class Solution: def possibleStringCount(self, word: str) -> int: return recurse(word, 0) + def recurse(word, idx) -> int: if idx == len(word): return 1 - + duplicates = 1 while idx < len(word) - 1 and word[idx] == word[idx + 1]: duplicates += 1 idx += 1 - + word_count = duplicates - 1 - + word_count += recurse(word, idx + 1) - + return word_count diff --git a/find-the-duplicate-number/find-duplicate.py b/find-the-duplicate-number/find-duplicate.py @@ -12,5 +12,5 @@ class Solution: return index + 1 else: nums[index] *= -1 - + return -1 diff --git a/find-the-index-of-the-first-occurrence-in-a-string/find-the-iV1.py b/find-the-index-of-the-first-occurrence-in-a-string/find-the-iV1.py @@ -1,7 +1,6 @@ class Solution: def strStr(self, haystack: str, needle: str) -> int: for i in range(0, 1 + len(haystack) - len(needle)): - if haystack[i:i+len(needle)] == needle: + if haystack[i : i + len(needle)] == needle: return i return -1 - diff --git a/find-the-k-th-character-in-string-game-i/find-the-k-th-character-in-string-game-iV1.py b/find-the-k-th-character-in-string-game-i/find-the-k-th-character-in-string-game-iV1.py @@ -5,6 +5,7 @@ class Solution: word += increment_word(word) return word[k - 1] + def increment_word(word): new_word = "" for char in word: diff --git a/implement-trie/trie.py b/implement-trie/trie.py @@ -1,8 +1,9 @@ -class TreeNode(): +class TreeNode: def __init__(self): self.is_string = False self.chars = {} + class Trie: def __init__(self): @@ -20,10 +21,10 @@ class Trie: else: current = current.chars[char] - current.is_string = True + current.is_string = True def search(self, word: str) -> bool: - + current = self.root for char in word: @@ -31,7 +32,7 @@ class Trie: current = current.chars[char] else: return False - + return current.is_string def startsWith(self, prefix: str) -> bool: @@ -54,4 +55,4 @@ class Trie: # idea: # route through the tree based on the prefix of the string. # if a string exists, we then mark the node with a 'is_string' bool -# +# diff --git a/invert-binary-tree/invert-binary-tree.py b/invert-binary-tree/invert-binary-tree.py @@ -6,20 +6,21 @@ # self.right = right class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: - + if root is None: return root out = recurse(root) return out - + + def recurse(current): - assert(current is not None) + assert current is not None if current.left is None and current.right is None: return current - + temp = current.right current.right = current.left current.left = temp diff --git a/koko-eating-bananas/eating.py b/koko-eating-bananas/eating.py @@ -1,5 +1,6 @@ import math + class Solution: # IDEA: @@ -9,14 +10,14 @@ class Solution: # and return smallest value # Optimized approach: - # we can use a binary search from 1 to m, - # checking at each step if k is sufficient + # we can use a binary search from 1 to m, + # checking at each step if k is sufficient # to solve the problem. # If k solves the problem, check lower values # If it doesn't, check higher values. def minEatingSpeed(self, piles: List[int], h: int) -> int: - + m = max(piles) lower = 1 @@ -26,7 +27,7 @@ class Solution: while lower <= upper: center = ((upper - lower) // 2) + lower - + if possible(piles, h, center): smallest_k = center upper = center - 1 @@ -35,10 +36,11 @@ class Solution: return smallest_k + # h = hours # k = bph def possible(piles, h, k): - + total_hours = 0 for pile in piles: total_hours += math.ceil(pile / k) diff --git a/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV1.py b/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV1.py @@ -1,5 +1,6 @@ from heapq import heappush, heappop, nlargest + class KthLargest: def __init__(self, k: int, nums: List[int]): @@ -18,9 +19,10 @@ class KthLargest: while len(self.ls) > self.k: self.ls = self.ls[1:] - + return ret_val + # Your KthLargest object will be instantiated and called as such: # obj = KthLargest(k, nums) # param_1 = obj.add(val) diff --git a/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV2.py b/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV2.py @@ -1,5 +1,6 @@ from heapq import heapify, heappush, heappop + class KthLargest: def __init__(self, k: int, nums: List[int]): diff --git a/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV3.py b/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV3.py @@ -3,6 +3,7 @@ from heapq import heappush, heappop + class Heap: def __init__(self, nums): if nums is None: @@ -12,25 +13,25 @@ class Heap: if len(nums) <= 1: self.nums = nums return - + self.nums = self._make_heap(nums, 0) - + def _make_heap(self, nums, index): if not self._is_leaf(nums, index): self._make_heap(nums, self._left_child(index)) self._make_heap(nums, self._right_child(index)) else: return - - self._compare_three(nums,index) + + self._compare_three(nums, index) return nums def _left_child(self, index): return (index * 2) + 1 - + def _right_child(self, index): return (index * 2) + 2 - + def pop(self): return heappop(self.nums) @@ -39,7 +40,7 @@ class Heap: def _compare_three(self, nums, index): """Compare and move pair of three to be arranged correctly. Assume index is root.""" - + root = index left = self._left_child(index) right = self._right_child(index) @@ -50,23 +51,24 @@ class Heap: min_index = left if len(nums) > right and nums[right] < nums[min_index]: min_index = right - + if min_index != index: temp = nums[root] nums[root] = nums[min_index] nums[min_index] = temp if not self._is_leaf(nums, min_index): self._compare_three(nums, min_index) - + return def _is_leaf(self, nums, index): - + if len(nums) <= (index * 2) + 1: return True - + return False + class KthLargest: def __init__(self, k: int, nums: List[int]): diff --git a/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV4.py b/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV4.py @@ -1,8 +1,10 @@ from heapq import heappush + # TODO: # Remove usage of heappush by implementing heapify up # for push method. + class Heap: def __init__(self, nums): if nums is None: @@ -12,25 +14,25 @@ class Heap: if len(nums) <= 1: self.nums = nums return - + self.nums = self._make_heap(nums, 0) - + def _make_heap(self, nums, index): if not self._is_leaf(nums, index): self._make_heap(nums, self._left_child(index)) self._make_heap(nums, self._right_child(index)) else: return - - self._heapify_down(nums,index) + + self._heapify_down(nums, index) return nums def _left_child(self, index): return (index * 2) + 1 - + def _right_child(self, index): return (index * 2) + 2 - + def pop(self): nums = self.nums nums[0] = nums[-1] @@ -38,7 +40,7 @@ class Heap: if len(nums) > 1: self._heapify_down(nums, 0) - + return ret_val def push(self, val): @@ -46,7 +48,7 @@ class Heap: def _heapify_down(self, nums, index): """Compare and move pair of three to be arranged correctly. Assume index is root.""" - + root = index left = self._left_child(index) right = self._right_child(index) @@ -57,23 +59,24 @@ class Heap: min_index = left if len(nums) > right and nums[right] < nums[min_index]: min_index = right - + if min_index != index: temp = nums[root] nums[root] = nums[min_index] nums[min_index] = temp if not self._is_leaf(nums, min_index): self._heapify_down(nums, min_index) - + return def _is_leaf(self, nums, index): - + if len(nums) <= (index * 2) + 1: return True - + return False + class KthLargest: def __init__(self, k: int, nums: List[int]): diff --git a/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV5.py b/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV5.py @@ -7,25 +7,25 @@ class Heap: if len(nums) <= 1: self.nums = nums return - + self.nums = self._make_heap(nums, 0) - + def _make_heap(self, nums, index): if not self._is_leaf(nums, index): self._make_heap(nums, self._left_child(index)) self._make_heap(nums, self._right_child(index)) else: return - - self._heapify_down(nums,index) + + self._heapify_down(nums, index) return nums def _left_child(self, index): return (index * 2) + 1 - + def _right_child(self, index): return (index * 2) + 2 - + def pop(self): nums = self.nums nums[0] = nums[-1] @@ -33,7 +33,7 @@ class Heap: if len(nums) > 1: self._heapify_down(nums, 0) - + return ret_val def push(self, val): @@ -42,7 +42,7 @@ class Heap: def _heapify_down(self, nums, index): """Compare and move pair of three to be arranged correctly. Assume index is root.""" - + root = index left = self._left_child(index) right = self._right_child(index) @@ -53,14 +53,14 @@ class Heap: min_index = left if len(nums) > right and nums[right] < nums[min_index]: min_index = right - + if min_index != index: temp = nums[root] nums[root] = nums[min_index] nums[min_index] = temp if not self._is_leaf(nums, min_index): self._heapify_down(nums, min_index) - + return def _heapify_up(self, nums, index): @@ -73,12 +73,13 @@ class Heap: self._heapify_up(nums, parent) def _is_leaf(self, nums, index): - + if len(nums) <= (index * 2) + 1: return True - + return False + class KthLargest: def __init__(self, k: int, nums: List[int]): diff --git a/kth-smallest-element-in-a-bst/kth-smallest.py b/kth-smallest-element-in-a-bst/kth-smallest.py @@ -9,30 +9,32 @@ # IDEA: # Perform DFS: - # go all the way to the left - # decrement smallest counter value - # if smallest counter value == 0: - # return current value +# 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) + + right_found = dfs_kth(root.right, val) return right_found diff --git a/last-stone-weight/last-stone-weightV1.py b/last-stone-weight/last-stone-weightV1.py @@ -1,31 +1,32 @@ from heapq import heappop, heappush, heapify + class Solution: def lastStoneWeight(self, stones: List[int]) -> int: - + # heapq is a min-heap. - + stones = [-x for x in stones] heapify(stones) heap = stones while len(heap) > 1: - + # y heaviest = heappop(heap) - + # x second_heaviest = heappop(heap) # if x == y both destroyed if heaviest == second_heaviest: continue - + # x != y heaviest = heaviest - second_heaviest heappush(heap, heaviest) - + if len(heap) == 1: return heap[0] * -1 - + return 0 diff --git a/linked-list-cycle/linked-list-cycle.py b/linked-list-cycle/linked-list-cycle.py @@ -4,9 +4,10 @@ # self.val = x # self.next = None + class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: - + if head is None: return False @@ -19,5 +20,5 @@ class Solution: else: current.val = None current = current.next - + return False diff --git a/linked-list-cycle/linked-list-cycleV2.py b/linked-list-cycle/linked-list-cycleV2.py @@ -4,9 +4,10 @@ # self.val = x # self.next = None + class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: - + # two pointers, one fast, one slow # if fast catches slow, issue # if fast reaches end, success @@ -22,10 +23,10 @@ class Solution: return True fast_ptr = fast_ptr.next - + if fast_ptr is not None: fast_ptr = fast_ptr.next - + slow_ptr = slow_ptr.next return False diff --git a/longest-repeating-character-replacement/longest-repeating.py b/longest-repeating-character-replacement/longest-repeating.py @@ -1,20 +1,21 @@ import numpy as np + class Solution: def characterReplacement(self, s: str, k: int) -> int: - + # keep track of the most popular as we go through # when adverserial examples are found, we add them to our hash_map - # and increment our counter for them. - + # and increment our counter for them. + # when adverserial > k, we move the left_ptr to the right, removing values each time. - # while we do this, we also need to check the most popular character in our - # substring. + # while we do this, we also need to check the most popular character in our + # substring. longest = 0 counts = [0] * 26 - + left_ptr = 0 right_ptr = 0 @@ -30,25 +31,26 @@ class Solution: counts[converted[left_ptr]] -= 1 left_ptr += 1 looped = True - + else: current = (right_ptr - left_ptr) + 1 if current > longest: longest = current right_ptr += 1 - return longest + def char_to_int(char_input): return ord(char_input) % 97 + def count_adversaries(counts): adversaries = 0 max_index = np.argmax(counts) for i in range(0, len(counts)): - + if i == max_index: continue adversaries += counts[i] diff --git a/longest-substring-without-repeating-characters/longest-substring.py b/longest-substring-without-repeating-characters/longest-substring.py @@ -1,11 +1,11 @@ class Solution: def lengthOfLongestSubstring(self, s: str) -> int: - + left_ptr = 0 right_ptr = 0 longest = 0 hash_map = {} - + while right_ptr < len(s): # if the right side is in the map, remove characters until it is no longer there @@ -19,7 +19,7 @@ class Solution: current_len = (right_ptr - left_ptr) + 1 if current_len > longest: longest = current_len - + right_ptr += 1 - + return longest diff --git a/lowest-common-ancestor-of-a-binary-search-tree/lowest.py b/lowest-common-ancestor-of-a-binary-search-tree/lowest.py @@ -5,22 +5,26 @@ # self.left = None # self.right = None + class Solution: - def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': + def lowestCommonAncestor( + self, root: "TreeNode", p: "TreeNode", q: "TreeNode" + ) -> "TreeNode": if p.val > q.val: temp = p p = q q = temp - + return dfs(root, p, q) + # Assume input of p <= q def dfs(current, p, q): assert not current is None if p.val <= current.val and q.val >= current.val: return current - + if current.val > p.val: return dfs(current.left, p, q) else: diff --git a/max-dotproduct-of-subsequences/MaxDotProductOfTwoSubsequences.py b/max-dotproduct-of-subsequences/MaxDotProductOfTwoSubsequences.py @@ -1,6 +1,5 @@ - # Call again with subset of set and input is selections -def maxDotProduct(nums : list[int], nums2 : list[int]) -> int: +def maxDotProduct(nums: list[int], nums2: list[int]) -> int: return 1 @@ -9,6 +8,6 @@ def printResult(expected, actual): print("ACTUAL: " + str(expected)) -printResult(18, maxDotProduct([2,1,-1,5], [3,0,-6])) -printResult(21, maxDotProduct([3,-2] , [2,-6,7])) -printResult(-1, maxDotProduct([-1,-1], [1,1])) +printResult(18, maxDotProduct([2, 1, -1, 5], [3, 0, -6])) +printResult(21, maxDotProduct([3, -2], [2, -6, 7])) +printResult(-1, maxDotProduct([-1, -1], [1, 1])) diff --git a/maximum-depth/maximum-depth.py b/maximum-depth/maximum-depth.py @@ -8,12 +8,13 @@ class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: return dfs(root, 0) + def dfs(current, depth) -> int: - + if current is None: return depth - + left = dfs(current.left, depth + 1) right = dfs(current.right, depth + 1) - return max(left,right) + return max(left, right) diff --git a/maximum-difference-by-remapping-a-digit/max-diff.py b/maximum-difference-by-remapping-a-digit/max-diff.py @@ -1,15 +1,15 @@ class Solution: def minMaxDifference(self, num: int) -> int: - + num_ls = [] while num > 0: lsb = num % 10 num = num // 10 num_ls.append(lsb) - + num_ls.reverse() num_ls_min = num_ls.copy() - + # min = setting msb to 0 (since int, no leading 0's) val_to_map = num_ls[0] @@ -17,9 +17,9 @@ class Solution: for i in range(0, len(num_ls)): if num_ls[i] == val_to_map: num_ls_min[i] = 0 - + # max = setting max non 9 value to be = 9 (or leaving as is when all 9's) - + num_ls_max = num_ls.copy() digit_to_change = 9 @@ -27,11 +27,10 @@ class Solution: if num_ls_max[i] != 9: digit_to_change = num_ls_max[i] break - + for i in range(0, len(num_ls_max)): if num_ls_max[i] == digit_to_change: num_ls_max[i] = 9 - max_val = to_int(num_ls_max) min_val = to_int(num_ls_min) @@ -42,5 +41,5 @@ class Solution: def to_int(num_ls) -> int: num = 0 for i in range(len(num_ls) - 1, -1, -1): - num += num_ls[i] * 10**((len(num_ls) - 1) - i) + num += num_ls[i] * 10 ** ((len(num_ls) - 1) - i) return num diff --git a/maximum-odd-binary-number/maximum-odd-binary-number.py b/maximum-odd-binary-number/maximum-odd-binary-number.py @@ -1,16 +1,17 @@ -#Not great solution +# Not great solution + +# 5.93% 93ms +# 75.75% 16.56MB -#5.93% 93ms -#75.75% 16.56MB class Solution: def maximumOddBinaryNumber(self, s: str) -> str: - ones = s.count('1') + ones = s.count("1") lis = [] for i in range(ones): - lis.append('1') + lis.append("1") for i in range(len(s) - ones): - lis.append('0') + lis.append("0") st = toStr(lis) val = int(st, 2) while val % 2 == 0: @@ -19,18 +20,20 @@ class Solution: val = int(st, 2) return st + def toStr(lis): - st = '' + st = "" for i in lis: st += i return st + def moveRightMost(s): count = len(s) - 1 for i in reversed(s): - if i == '0' and s[count - 1] == '1': - s[count - 1] = '0' - s[count] = '1' + if i == "0" and s[count - 1] == "1": + s[count - 1] = "0" + s[count] = "1" return s count -= 1 return s diff --git a/maximum-odd-binary-number/maximum-odd-binary-numberV2.py b/maximum-odd-binary-number/maximum-odd-binary-numberV2.py @@ -1,10 +1,10 @@ +# This is the right way. Kinda wasn't thinking that the last +# bit being a one means the number is odd and that is the only +# way.... -#This is the right way. Kinda wasn't thinking that the last -#bit being a one means the number is odd and that is the only -#way.... -#30ms 93.00% -#16.56MB 75.75% +# 30ms 93.00% +# 16.56MB 75.75% class Solution: def maximumOddBinaryNumber(self, s: str) -> str: diff --git a/merge-two-sorted-lists/merge-two-sorted-lists.py b/merge-two-sorted-lists/merge-two-sorted-lists.py @@ -5,37 +5,39 @@ # self.next = next class Solution: # len(list1, list2) can be 0 - def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: - + def mergeTwoLists( + self, list1: Optional[ListNode], list2: Optional[ListNode] + ) -> Optional[ListNode]: + if list1 is None: return list2 if list2 is None: return list1 - + head = None - + if list1.val < list2.val: head = list1 list1 = list1.next else: head = list2 list2 = list2.next - - assert(head is not None) - + + assert head is not None + current = head while list1 is not None and list2 is not None: - + if list1.val < list2.val: current.next = list1 list1 = list1.next else: current.next = list2 list2 = list2.next - + current = current.next - + if list1 is None: current.next = list2 else: diff --git a/palindrome-number/palindrome-number.py b/palindrome-number/palindrome-number.py @@ -1,6 +1,6 @@ class Solution: def isPalindrome(self, x: int) -> bool: - + ls = list(str(x)) ls_cp = ls.copy() ls_cp.reverse() diff --git a/permutation-in-string/perm-in-string.py b/permutation-in-string/perm-in-string.py @@ -3,16 +3,16 @@ class Solution: # SLIDING WINDOW: # CONSIDER: - - # if s2 contains a permutation of s1 then - # there exists a contiguous string s1_x - # such that the count of each character - # in s1_x is the same s2 + + # if s2 contains a permutation of s1 then + # there exists a contiguous string s1_x + # such that the count of each character + # in s1_x is the same s2 # Given this, we slide a window over s2, # keeping track of character counts as we go # if the characters match s1's characters, we return - # true. + # true. # since we do at most 26 comparisons (one for each character) # per window, we see this is O(n) @@ -27,7 +27,7 @@ class Solution: for char in s1: s1_counts[to_int(char)] += 1 - + left_ptr = 0 right_ptr = len(s1) - 1 @@ -52,15 +52,17 @@ class Solution: s2_counts[to_int(s2[right_ptr])] += 1 return False - + def to_int(char): return ord(char) % 97 + # assumes len(ls1) == len(ls2) which should -# be true when initialized to represent lower case +# be true when initialized to represent lower case # characters. + def compare_lists(ls1, ls2): for i in range(0, len(ls1)): if ls1[i] != ls2[i]: diff --git a/remove-duplicates-from-sorted-array/remove-duplicates.py b/remove-duplicates-from-sorted-array/remove-duplicates.py @@ -1,16 +1,16 @@ class Solution: def removeDuplicates(self, nums: List[int]) -> int: - + current_index = 0 current_val = nums[0] - 1 for i in range(0, len(nums)): - + if current_val == nums[i]: continue current_val = nums[i] nums[current_index] = nums[i] current_index += 1 - + return current_index diff --git a/remove-nth-node-from-end/remove-nth.py b/remove-nth-node-from-end/remove-nth.py @@ -5,31 +5,31 @@ # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: - + ############################################# # IDEA: # two pointers, sliding window - # left_ptr = right_ptr's index - (n + 1) - # right_ptr increments until reaching the end + # left_ptr = right_ptr's index - (n + 1) + # right_ptr increments until reaching the end # once right_ptr is at the end, left_ptr is one position before the point to remove - # at this point, we set left_ptr's next to be left_ptr.next.next. - + # at this point, we set left_ptr's next to be left_ptr.next.next. + ############################################# - + if head.next is None: return None - + left_node = head right_node = head for i in range(0, n): right_node = right_node.next - + if right_node is None: return head.next - + while right_node.next is not None: right_node = right_node.next left_node = left_node.next diff --git a/reorder-list/reorder-list.py b/reorder-list/reorder-list.py @@ -15,14 +15,15 @@ # interlace lists O(n) # return nothing + class Solution: def reorderList(self, head: Optional[ListNode]) -> None: # count length - + current = head n = 0 - + while current is not None: n += 1 current = current.next @@ -40,12 +41,11 @@ class Solution: for i in range(0, midpoint_index - 1): midpoint = midpoint.next - + midpoint_left = midpoint midpoint = midpoint.next midpoint_left.next = None - # reverse second half iterations = n - midpoint_index @@ -58,9 +58,9 @@ class Solution: right.next = left left = right right = temp_next - + head_of_reverse = left - + # interlace # current_left = head @@ -72,6 +72,6 @@ class Solution: while next_node is not None: temp_next = current.next current.next = next_node - + current = next_node next_node = temp_next diff --git a/reverse-linked-list/reverse-list.py b/reverse-linked-list/reverse-list.py @@ -10,7 +10,7 @@ class Solution: if head is None or head.next is None: return head - + left = head right = head.next head.next = None @@ -20,7 +20,7 @@ class Solution: right.next = left left = right right = temp - + head = left return head diff --git a/same-tree/same-tree.py b/same-tree/same-tree.py @@ -8,8 +8,8 @@ class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: right = p left = q - return dfs(left,right) - + return dfs(left, right) + def dfs(left, right): @@ -18,12 +18,12 @@ def dfs(left, right): if right is None: none += 1 if left is None: - none += 1 + none += 1 if none == 1: return False if none == 2: return True - + left_id = dfs(left.left, right.left) right_id = dfs(left.right, right.right) current_id = left.val == right.val diff --git a/search-a-2d-matrix/search-a-2d-matrix.py b/search-a-2d-matrix/search-a-2d-matrix.py @@ -1,21 +1,22 @@ class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: - + for row in matrix: if binary_search(row, 0, len(row) - 1, target): return True - + return False + def binary_search(row, lower, upper, target) -> bool: if lower > upper: return False - + center = ((upper - lower) // 2) + lower if row[center] == target: return True - + if row[center] > target: upper = center - 1 return binary_search(row, lower, upper, target) diff --git a/search-in-rotated-sorted-array/searchArray.py b/search-in-rotated-sorted-array/searchArray.py @@ -1,12 +1,12 @@ # This was really quite hard. class Solution: def search(self, nums: List[int], target: int) -> int: - + left = 0 right = len(nums) - 1 while left <= right: - + center = ((right - left) // 2) + left if nums[center] == target: diff --git a/squares-of-a-sorted-array/squares-of-a-sorted-array.py b/squares-of-a-sorted-array/squares-of-a-sorted-array.py @@ -1,8 +1,9 @@ -#158ms 50.27% -#18.76MB 72.31% +# 158ms 50.27% +# 18.76MB 72.31% + +# This solution is a bit wordy. In a real environment I would just do the nlogn approach +# of squaring then sorting. -#This solution is a bit wordy. In a real environment I would just do the nlogn approach -#of squaring then sorting. class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: @@ -13,15 +14,17 @@ class Solution: while count < len(nums) and nums[count] < 0: negative.append(nums[count] * nums[count]) count += 1 - + while count < len(nums): positive.append(nums[count] * nums[count]) count += 1 - + count = 0 negativeIndex = len(negative) - 1 positiveIndex = 0 - while count < len(nums) and negativeIndex >= 0 and positiveIndex < len(positive): + while ( + count < len(nums) and negativeIndex >= 0 and positiveIndex < len(positive) + ): if negative[negativeIndex] < positive[positiveIndex]: returnList.append(negative[negativeIndex]) negativeIndex -= 1 @@ -29,7 +32,7 @@ class Solution: returnList.append(positive[positiveIndex]) positiveIndex += 1 count += 1 - + while negativeIndex >= 0: returnList.append(negative[negativeIndex]) negativeIndex -= 1 @@ -39,4 +42,3 @@ class Solution: positiveIndex += 1 return returnList - diff --git a/time-based-key-value-store/time-based.py b/time-based-key-value-store/time-based.py @@ -10,7 +10,7 @@ class TimeMap: if key in self.hash_map: current = self.hash_map[key] current_val = self.hash_map[key + " value"] - + current.append(timestamp) current_val.append(value) @@ -18,14 +18,14 @@ class TimeMap: self.hash_map[str(key) + " value"] = current_val def get(self, key: str, timestamp: int) -> str: - + current = [] current_vals = [] - + if key in self.hash_map: current = self.hash_map[key] current_vals = self.hash_map[str(key) + " value"] - + # perform binary search to find the biggest timestamp s.t. prev_timestamp <= timestamp left = 0 @@ -33,13 +33,13 @@ class TimeMap: while left <= right: center = ((right - left) // 2) + left - if (current[center] <= timestamp) and (center == len(current) - 1 \ - or current[(center + 1)] > timestamp): + if (current[center] <= timestamp) and ( + center == len(current) - 1 or current[(center + 1)] > timestamp + ): return current_vals[center] elif current[center] > timestamp: right = center - 1 else: - left = center + 1 + left = center + 1 - return "" diff --git a/two-sums/two-sums.py b/two-sums/two-sums.py @@ -1,13 +1,13 @@ - """ Leet Ratings Speed Memory -Total 1005ms 15MB +Total 1005ms 15MB Beats 38.22% 67.55% """ -def twoSum( nums: list[int], target: int): + +def twoSum(nums: list[int], target: int): count1 = len(nums) - 1 count2 = len(nums) - 1 while count1 >= 0: @@ -17,10 +17,10 @@ def twoSum( nums: list[int], target: int): return [count1, count2] count2 -= 1 count1 -= 1 - return [0,0] + return [0, 0] -nums = [0 , 1 , 4, 5 ,7 , 67] +nums = [0, 1, 4, 5, 7, 67] -print(twoSum(nums , 67)) +print(twoSum(nums, 67)) diff --git a/validate-binary-search-tree/validate-binary-search-tree.py b/validate-binary-search-tree/validate-binary-search-tree.py @@ -1,36 +1,38 @@ # IDEAS: -# 1) Perform in-order traversal then verify ordering of the result - # TIME: O(n) SPACE: O(n) +# 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]: + 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