commit ea03a9e2e460fe9b4654b0385b803d7b4fc4e6a1
parent d5703d1554710e7ceda6b0e10d6edfdf6b67c85e
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 11 Jun 2025 21:42:19 -0500
Completed a few more problems
Diffstat:
7 files changed, 250 insertions(+), 0 deletions(-)
diff --git a/3sum/3sum.py b/3sum/3sum.py
@@ -0,0 +1,60 @@
+class Solution:
+ # IDEA:
+
+ # O(n^2) time complexity
+ # pointer on left, pointer on right
+ # check if i in hashmap where i + left + right == 0
+ # if it is, add to output
+ # if it is not, continue on
+ # we do this for each selection of left and right indices
+ # we check O(n^2) possible combinations in constant time with
+ # the hashmap thus this is O(n^2) time complexity
+
+ # how to move the pointers?
+ # left pointer stays in place
+ # right pointer iterates
+
+
+ def threeSum(self, nums: List[int]) -> List[List[int]]:
+
+ nums.sort()
+
+ returnLs = []
+ added = set()
+
+ for current_index in range(0, len(nums)):
+ current_value = nums[current_index]
+ left_ptr = current_index + 1
+ right_ptr = len(nums) - 1
+
+ while right_ptr > left_ptr:
+
+ 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]:
+ left_ptr += 1
+ continue
+
+ inverse = -(nums[right_ptr] + nums[left_ptr])
+ if inverse == current_value:
+ cl = [nums[right_ptr], nums[left_ptr], current_value]
+ cl_string = str(cl)
+ if cl_string in added:
+ 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
+
+ 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
@@ -0,0 +1,65 @@
+class Solution:
+
+ # IDEA:
+
+ # sort list
+ # 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
+
+
+ def threeSum(self, nums: List[int]) -> List[List[int]]:
+
+ nums.sort()
+
+ # a + b + c = 0
+ returnLs = []
+
+ # -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
+
+ b_index = a_index + 1
+ c_index = len(nums) - 1
+ a = nums[a_index]
+
+ while c_index > b_index:
+
+ b = nums[b_index]
+ c = nums[c_index]
+
+ # b same as prior
+ if b_index - 1 != a_index and b == nums[b_index - 1]:
+ b_index += 1
+ continue
+ # c same as prior
+ 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
@@ -0,0 +1,41 @@
+# Definition for singly-linked list.
+# class ListNode:
+# def __init__(self, val=0, next=None):
+# self.val = val
+# self.next = next
+class Solution:
+
+
+ def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
+ l1Val = convert(l1)
+ l2Val = convert(l2)
+ res = l1Val + l2Val
+ print(res)
+ finalLs = revert(res)
+ return finalLs
+
+def revert(num):
+ if num == 0:
+ return ListNode(0)
+
+ retLs = []
+ while num > 0:
+ toAdd = num % 10
+ retLs.append(toAdd)
+ num = num // 10
+
+ base = ListNode(retLs[0])
+ last = base
+ for i in range(1, len(retLs)):
+ current = ListNode(retLs[i])
+ last.next = current
+ last = current
+
+ return base
+
+def convert(l1):
+ vals = ""
+ while l1 != None:
+ vals = str(l1.val) + vals
+ l1 = l1.next
+ return int(vals)
diff --git a/binary-search/binary-search.py b/binary-search/binary-search.py
@@ -0,0 +1,26 @@
+class Solution:
+ def search(self, nums: List[int], target: int) -> int:
+
+ done = False
+ lower = 0
+ upper = len(nums) - 1
+
+ while not done:
+
+ diff = upper - lower
+ center = (diff // 2) + lower
+
+ if upper == lower or lower + 1 == upper:
+ if nums[lower] == target:
+ return lower
+ if nums[upper] == target:
+ return upper
+ return -1
+
+ if nums[center] == target:
+ return center
+
+ if nums[center] < target:
+ lower = center
+ else:
+ upper = center
diff --git a/binary-search/binary-searchV2.py b/binary-search/binary-searchV2.py
@@ -0,0 +1,24 @@
+class Solution:
+
+ def search(self, nums: List[int], target: int) -> int:
+ 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
+
+ if nums[center] < target:
+ new_lower = center + 1
+ if nums[center] > target:
+ new_upper = center - 1
+
+ return recursive_binary_search(nums,target, new_lower, new_upper)
diff --git a/maximum-difference-between-adjacent-elements-in-a-circular-array/max-diff.py b/maximum-difference-between-adjacent-elements-in-a-circular-array/max-diff.py
@@ -0,0 +1,10 @@
+class Solution:
+ def maxAdjacentDistance(self, nums: List[int]) -> int:
+ max_diff = 0
+ # NOTE:
+ # Since -1 == final element, we know -1 and 0 are adjacent :)
+ for i in range(0, len(nums)):
+ current = abs(nums[i - 1] - nums[i])
+ if max_diff < current:
+ max_diff = current
+ return max_diff
diff --git a/search-a-2d-matrix/search-a-2d-matrix.py b/search-a-2d-matrix/search-a-2d-matrix.py
@@ -0,0 +1,24 @@
+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)
+ else:
+ lower = center + 1
+ return binary_search(row, lower, upper, target)
