//Dec 22 2024 1389 Create Target Array in the Given Order In example 2, you can see that: nums index target 1 0 [1] 2 1 [1,2] 3 2 [1,2,3] 4 3 [1,2,3,4] 0 0 [0,1,2,3,4] You're able to over-ride index elems, by pushing the arry to the right. What you want to do is map the nums to the index. res = [] for i in range(len(nums)): res.insert(index[i], nums[i]) return res 1523 Count Odd Numbers in an Interval Range return (high - low) // 2 1-5 = 4 // 2 = 2 , 3, so the return should be 1 There are 4 cases: low = even, low = odd low = even, high = odd low = odd, high = even low = odd, high = odd 1,5 -> 2//2 + 1 = 3 [1,3,5] 2,5 -> 3//2 + 1 = 2 [3,5] 1,4 -> 3//2 + 1 = 2 [1,3] 2,4 -> 2//2 + 0 = 1 [3] (high - low) // 2: Base count (high % 2 or low % 2): Adds 1 if either bound is odd Or you could do brute force O(n) forloop and just count the odd vals. class Solution: def countOdds(self, low: int, high: int) -> int: return (high - low) // 2 + (high % 2 or low % 2) 3168 Minimum Number of Chairs in a Waiting Room current_chairs = 0 max_chairs = 0 for event in s: if event == 'E': current_chairs += 1 max_chairs = max(max_chairs, current_chairs) else: current_chairs -= 1 return max_chairs 3046 Split the Array Ok, the problem is worded pretty badly. The thing to note is that 1) we don't have to actually split the array 2) we simply have to look for occurance of > 2 in hash map (fails the dist test) count = {} for num in nums: counts[num] = count.get(num, 0) + 1 if counts[num] > 2: return False return True class Solution: def isPossibleToSplit(self, nums: List[int]) -> bool: nums1, nums2 = nums[:len(nums)//2], nums[len(nums)//2:] dist1, dist2 = set(nums1), set(nums2) if len(nums1) != len(nums2) or len(dist1) != len(nums1) or len(dist2) != len(nums2): return False return True //Dec 21 2024 2706 Buy Two Chocolates You just return the money - sum of the 2 smallest vals and if that greater than money, return money? class Solution: def buyChoco(self, prices: List[int], money: int) -> int: sorted_prices = sorted(prices) total = sorted_prices[0] + sorted_prices[1] return money if total > money else money - total 1704 Dettermine if String Halves Are Alike Split strings in half (a,b). Create hash map of lowercase and upper case vowels. If len(vowels(a)) == len(vowels(b)), return true. class Solution: def halvesAreAlike(self, s: str) -> bool: all_vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'} a, b = s[:len(s)//2], s[len(s)//2:] a_count, b_count = 0, 0 for char in a: if char in all_vowels: a_count += 1 for char in b: if char in all_vowels: b_count += 1 return a_count == b_count //Dec 20 2024 2574 Left and Right Sum Differences Putting everything together: n = len(array) prefix_sum, suffix_sum = [0] * n, [0] * n prefix_sum[0], suffix_sum[-1] = nums[0], nums[-1] for i in range(1, n): prefix_sum[i] = prefix_sum[i-1] for i in range(n-2, -1, -1): suffix_sum[i] = suffix_sum[i+1] answer = [] for i in n: answer.appned(abs(prefix_sum[i] - suffix_sum[i])) return answer Seems like you're creating an array for this problem. Make a prefix sum. leftsum = [nums[1]] for num in range(1, len(nums)): leftsum.append(left_sum[-1] + num) The relationship to suffix sum = total_sum - prefix[i-1] total_sum = prefix_sum[i-1] Or we can be lazy and create a suffix sum manually: n = len(array) suffix_sum = [0] * n suffix_sum[-1] = array[-1] for i in range(n-2, -1, -1): suffix_sum[i] = suffix_sum[i+1] answer = array len (nums) # empty array for i, num in enumerate(nums): answer[i] = //Dec 19 2024 1160 Find Words That Can Be Formed by Characters Attempt two (use hashmap) char_count = Counter(chars) total = 0 for word in words: word_count = Counter(word) for c in word: if word_count[c] > char_count[c]: break else: total += len(word) return total Attempt one (one line) return sum(1 for word in words if set(word).issubset(set(chars))) //Dec 18 2024 1784 Check if Binary String Has at Most One Segment of Ones Loop through, if 1 occures, there cannot be a 0, and a one again. class Solution: def checkOnesSegment(self, s: str) -> bool: seeing_ones = False prev = '0' for bit in s: if bit == '1' and prev == '0' and seeing_ones: return False if bit == '1': seeing_ones = True prev = bit return True 2595 Number of Even and Odd Bits Conver to bin. Loop through it, if bit == 1 and i % 2 == 0, [even, odd+=1] res = [0, 0] binary = bin(n)[2:] for i, bit in enumerate(binary[::-1]): if bit == '1': if i % 2 == 0: res[0] += 1 else: res[1] += 1 return res //Dec 17 2024 3280 Convert Date to Binary Loop through everything. Split @ '-', convert to bin, convert back to string, return append. class Solution: def convertDateToBinary(self, date: str) -> str: parts = date.split('-') binary_parts = [] for part in parts: binary = bin(int(part))[2::] binary_parts.append(binary) return '-'.join(binary_parts) //Dec 15 2024 3295 Report Spam Message Add the list of banned words to set. bannedSet= set(bannedWords) count = 0 for word in message: if word in bannedSet: count += 1 return count < 2 //Dec 14 2024 2367 Number of Arithmetic Triplets The brute force solution is to us i,j,k triple forloop. Or you can create a set: Proof: nums[k] - nums[j] = diff Thus nums[k] = nums[j] + diff nums[k] = (x + diff) + diff nums[k] = x + 2*diff nums_set = set(nums) count = 0 for num in nums: if num + diff in nums_set and num + 2 * diff in nums_set: count += 1 return count 1688 Count of Matches in Tournament class Solution: def numberOfMatches(self, n: int) -> int: return n-1 //Dec 13 2024 985 Sum of Even Numbers After Queries class Solution: def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]: even_sum = sum(x for x in nums if x % 2 == 0) answer = [] for val, i in queries: if nums[i] % 2 == 0: even_sum -= nums[i] nums[i] += val if nums[i] % 2 == 0: even_sum += nums[i] answer.append(even_sum) return answer Misread the question. Attempt two: answer = [] for val, index in queries: nums[index] += val even_sum = sum(x for x in nums if x % 2 == 0) answer.append(even_sum) return answers The above is a brute force solution. Can use memo. for the 1st index of every 2d array in queries, num[ith index] = nums[ith index] += val at ith index. Return answer arr. answer = empty array len(nums) for val, index in queries: if statement to only sum even val of nums answer[index] = nums[index] + val return answer //Dec 12 2024 1869 Longer Contiguous Segments of Ones than Zeros Code cleanup (forgor to reset 0s and 1s counter): longest_zeros = longest_ones = 0 cur_zeros = cur_ones = 0 for char in s: if char == '0': cur_zeros += 1 cur_ones = 0 longest_zeros = max(longest_zeros, cur_zeros) else: cur_ones += 1 cur_zeros = 0 longest_ones = max(longest_ones, cur_ones) return longest_ones > longest_zeros longest_zeros, longest_ones = 0, 0 for i, num in enumerate(1, len(s)): cur_zeros, cur_ones = 0, 0 if s[i-1] == s[i]: if s[i] == 0: cur_zeros += 1 if cur_zeros > longest_zeros: longest_zeros = cur_zeros else: cur_ones += 1 if cur_ones > longest_ones: longest_ones = cur_ones return longest_ones > longest_zeros 3069 Distribute Elements Into Two Arrays class Solution: def resultArray(self, nums: List[int]) -> List[int]: arr1, arr2 = [nums[0]], [nums[1]] for num in nums[2:]: if arr1[-1] > arr2[-1]: arr1.append(num) else: arr2.append(num) return arr1 + arr2 //Dec 11 2024 1952 Three Divisors if n < 4: return False root = int(n**0.5) if root * root != n: return False for i in range(2, int(root ** 0.5) + 1): if root % i == 0: return False return True What the hek, this is kinda hard if you dont know the rules. //Dec 10 2024 2124 Check if All A's Appears Before All B's This is a simple flag question. class Solution: def checkString(self, s: str) -> bool: b_occurred = False for letter in s: if letter == 'b': b_occurred = True if b_occurred and letter == 'a': return False return True 2148 Count Elements With Strictly Smaller and Greater Elements Count the numb of elem within the range of min, max? if num < max and num > min, count += 1 class Solution: def countElements(self, nums: List[int]) -> int: min_val, max_val = min(nums), max(nums) count = 0 for num in nums: if min_val < num and max_val > num: count += 1 return count //Dec 9 2024 3038 Max Num of Operations With the Same Score I The wording for the problem is really bad :( The score val = first 2 val summed. And you do sliding window till you find another grouping that == score? count = 0 L, R = 0, 1 score = nums[0] + nums[1] while R < len(nums): if nums[L] + nums[R] == score: count += 1 L = R + 1 R = L + 1 else: L += 1 R = L + 1 return count Since we're returning the max num of operations, find the max num. max_num = max(nums) You do want to sort it. sorted_nums = sorted(nums) Then you want to count the max num of sub arrays you can make. class Solution: def maxOperations(self, nums: List[int]) -> int: nums.sort() count, subsum = 0, 0 for i in range(len(nums) - 1): if subsum + nums[i] >= nums[-1]: subsum = nums[i] count += 1 else: subsum += nums[i] return count //Dec 8 2024 2529 Max Count of Postive Integer and Neg Integer L and R pointers. Count the pairs of +, and -. if not nums or (nums[0] == 0 and nums[-1] == 0): return 0 L, R = 0, len(nums) - 1 while L < R and nums[L] < 0 and nums[R] > 0: L += 1 R -= 1 return min(L, len(nums) - R - 1) Ooof misread the question. class Solution: def maximumCount(self, nums: List[int]) -> int: if not nums or (nums[0] == 0 and nums[-1] == 0): return 0 L = 0 while L < len(nums) and nums[L] < 0: L += 1 R = len(nums) - 1 while R >= 0 and nums[R] > 0: R -= 1 return max(L, len(nums) - R - 1) 3074 Apple Redistribution into Boxes Loop. Only move forward with capacity if apple.val == 0. capactity[j] - apple[i] i, j = 0, 0 while apple[-1] > 0 and j < len(apple)-1: if capacity[j] > apple[i]: capacity[j] -= apple[i] i += 1 else: capacity[j+1] + capacity[j] -= apple[i] j + 1 return j wait, you could just sort this. Since the box ordering does not matter. capacity.sort(reverse=True) total_apples = sum(apples) boxes_needed = 0 cur_capacity = 0 for i in range(len(capacity)): cur_capacity += capacity[i] box_needed += 1 if cur_capacity >= total_apples: return boxes_needed return -1 //Dec 6 2024 1200 Minimum Abs Difference Note that you can make the solution more optimal with a single pass after the sort. Sort the arr. find the min abs val, if pairs == min abs val, append. class Solution: def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]: res = [] sorted_arr = sorted(arr) min_diff = float('inf') for i in range(len(arr)-1): curr_diff = sorted_arr[i+1] - sorted_arr[i] if curr_diff < min_diff: min_diff = curr_diff for i in range(len(arr)-1): if sorted_arr[i+1] - sorted_arr[i] == min_diff: res.append([sorted_arr[i], sorted_arr[i+1]]) return res //Dec 5 2024 1154 Day of the Year I have no idea what the rules of the Gregorian Cal is... guh 1) Look at the first 4 digits. Year = int([:4]). year % 400 == 0 or (year % 4 == 0 and year % 100 != 0) it gets 29 days instead of 28 (feb) 2) Skip the dash and look at the month. month = int([5:6]) 3) days_in_month = { 1: 31, 2: 28, 3: 31, 4: 30, 5: 31, 6: 30, 7: 31, 8: 31, 9: 30, 10: 31, 11: 30, 12: 31 } 4) Loop through. If leap year +1 to date + final 2 vals 5) Get the last 2 digits as date. class Solution: def dayOfYear(self, date: str) -> int: year = int(date[:4]) month = int(date[5:7]) day = int(date[8:]) days_in_month = {1:31, 2:28, 3:31, 4:30, 5:31, 6:30, 7:31, 8:31, 9:30, 10:31, 11:30, 12:31} total = day for m in range(1, month): total += days_in_month[m] if month > 2 and (year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)): total += 1 return total 1437 Check If All 1's Are at Least Length K Places Away class Solution: def kLengthApart(self, nums: List[int], k: int) -> bool: dst = k for num in nums: if num == 1: if dst < k: return False dst = 0 else: dst += 1 return True 3340 Checking Balanced String class Solution: def isBalanced(self, num: str) -> bool: sum_even, sum_odd = 0, 0 for i, val in enumerate(num): if i % 2 == 0: sum_even += int(val) else: sum_odd += int(val) return sum_even == sum_odd // Dec 3 2024 1491. Avg Salary Excluding Min and Max Salary class Solution: def average(self, salary: List[int]) -> float: min_pay, max_pay, total = float('inf'), -float('inf'), 0 for pay in salary: total += pay if pay < min_pay: min_pay = pay if pay > max_pay: max_pay = pay return (total - min_pay - max_pay) / (len(salary) - 2) 2319. Check if Matrix is X matrix Return true if diagonal != 0, all others == 0. Double for loop. Check diagonal i == j. return false else. class Solution: def checkXMatrix(self, grid: List[List[int]]) -> bool: n = len(grid) for i in range(n): for j in range(n): if ((i == j or i + j == n - 1) and grid[i][j] == 0) or \ (i != j and i + j != n - 1 and grid[i][j] != 0): return False return True 2169. Count Operations to Obtain Zero num1 = 2 num2 = 3 1) 3-2 = 1 num1 = 2 num2 = 1 2) 2-1 = 1 num1 = 1 num2 = 1 3) 1-1 = 0 num1 = 0 num2 = 1 either or class Solution: def countOperations(self, num1: int, num2: int) -> int: count = 0 while num1 > 0 and num2 > 0: if num1 > num2: num1 -= num2 else: num2 -= num1 count += 1 return count //Dec 2 2024 3264. Final Array State After K Multiplication Operations Lets start off with a brute force solution. 1) find min val 2) relace with 2nd min w/ x*mutiplier for _ in range(k): min_val, min_index = min((val, idx) for idx, val in enumerate(nums)) second_min = min((val for val in nums if val != min_val), default=min_val) nums[min_index] = min_val * multiplier return nums //Dec 1 2024 1323. Maximum 69 Number The good python syntax for this is: class Solution: def maximum69Number(self, num: int) -> int: return int(str(num).replace('6', '9', 1)) To the get max num, you never want to ever end up changing 9->6. class Solution: def maximum69Number (self, num: int) -> int: new_num, first_six = '', False for char in str(num): if char == '6' and not first_six: first_six = True new_num += '9' else: new_num += char return int(new_num) //Nov 30 2024 3162. Find the Number of Good Pairs I I'm sure there is a solution better than O(n^2), but its 5am in the morning. Have a funct called is_good = nums1[i] % nums2[j] * k == 0 in a double for loop def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int: count = 0 for i in range len(nums1): for j in range(nums2): if nums1[i] % nums2[j] * k == 0: count += 1 return count Ok, since we finished it in 5min lets try the optimized solution. You could pre compute to get O(n*m) runtime. targets = [num * k for num in nums2] //June 3 2024 3033. Modify the Matrix class Solution: def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]: R, C = len(matrix), len(matrix[0]) max_col = [] change = [] answer = [row[:] for row in matrix] for c in range(C): col_max = float('-inf') for r in range(R): if matrix[r][c] == -1: change.append((r, c)) else: col_max = max(col_max, matrix[r][c]) max_col.append(col_max) for r, c in change: answer[r][c] = max_col[c] return answer 409. Longest Palindrome class Solution: def longestPalindrome(self, s: str) -> int: letters = defaultdict(int) for char in s: letters[char] += 1 res = 0 odd_found = False for val in letters.values(): res += val // 2 * 2 # Add pairs of characters if val % 2 == 1: # Check for odd counts odd_found = True if odd_found: res += 1 return res //May 17 2024 Dijkstra's Self Quiz **1631 Path With Minimum Effort** Q: Why would standard BFS not work for this shortest path? Answer, BDFs does not work for weighted graphs as it can only count the number of edges without taking into about of the weighting. We want to initialize the 1) heap 2) don't need an adjList def minimumEffortPath(self, heights: List[List[int]]) -> int: rows, cols = len(heights), len(heights[0]) efforts = [] efforts[0][0] = 0 for r in rows: for c in cols: efforts[r][c] = float('inf') min_heap = [(0, 0, 0)] #(effort, row, col) dir = [(1,0), (-1,0), (0,1), (0,-1)] while min_heap: effort, r, c = heapq.heappop(min_heap) if r == rows - 1 and col == cols - 1: return effort for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: new_effort = max(effort, abs(heights[nr][nc]-heights[r][c])) if new_effort < efforts[nr][nc]: efforts[nr][c] = new_effort heapq.heappush(min_heap, (new_effort, new_row, new_col)) return -1 **2331 Evaluate Boolean Binary Tree** This is a simple post order traversal problem. Q: Should we return a value? yes. Bool. def evaluateTree(self, root: Optional[TreeNode]) -> bool: if not root: return False if not root.left and not root.right: return root.val == 1 leftVal = self.evaluateTree(root.left) rightVal = self.evaluateTree(root.right) if root.val == 2: return leftVal or rightVal if root.val == 2: return leftVal and rightVal **1325 Delete Leaves With a Given Value** Better method: if not root: return None root.left = self.removeleafNodes(root.left, target) root.right = self.removeLeafNodes(root.right, target) if root.val == target and not root.left and not root.right: return None return root Delete all leaf nodes with target val. We have to save a ref to the parent node. Right we pass in the parent node, but how do we know which side to delete? def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]: if not root: return None if root.left and root.left.val == target: child = root.left if not child.left and not child.right: root.left = None if root.right and root.right.val == target: child = root.right if not child.left and not child.right: root.right = None root.left = self.removeLeafNodes(root.left, target) root.right = self.removeLeafNodes(root.right, target) return root //May 16 2024 Fun w/ graphs **1631 Path With Minimum Effort** **743 Network Delay Time** GPT: def netWorkDelayTime(times, n, k) -> int: graph = defaultdict(list) for u, v, w in times: graph[u].append((v,w)) min_heap = [(0,k)] distances = {i: float('inf) for i in range(1, n + 1)} distances[k] = 0 visited = set() while min_heap: current_dist, cur = heapq.pop(min_heap) if cur in visited: continue visited.add(cur) for neighbor, weight in adjList[cur]: new_dist = current_dist + weight if new_dist < distances[neighbor]: distances[neighbor] = new_dist heapq.heappush(min_heap, (new_dist, neightbor)) max_dist = max(distances.values()) return max_dist if max_dist < float('inf') else -1 For Dijkstra's: def dijkstra(src, dst): min_heap = [(0, src)] distances = {src: 0} visited = set() while min_heap: current_dist, cur = heapq.heappop(min_heap) if cur in visited: continue visited.add(cur) if cur == dst: return current_dist for neighbor, weight in adjList[cur]: if neighbor not in visited: new_dist = current_dist + weight if neighbor not in distances or new_dist < distances[neighbor]: distances[neighbor] = new_dist heapq.heappush(min_heap, (new_dist, neightbor)) return -1 Recall for BFS: def bfs(src, dst): visited = set() queue = deque([src]) visited.add(src) while queue: cur = queue.popleft() if cur == dst: return distance[cur] for neighbor in adjList[cur]: if neighbor not in visted: visited.add(neighbor) queue.append(neighbor) distances[neighbor] = distances[cur] + 1 def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = defaultdict(int) for u, v, w in times: graph[u].append((v,w)) min_heap = [(0,k)] heapq.heapify(min_heap) dist = {} for i in range(1, N + 1): dist[i] = float('inf') dist[K] = 0 //May 15 2024 **1460. Make Two Arrays Equal by Reversing Subarrays** Or return sorted(1) == sorted(2) Assume that as long as all the # are there, through an inf num of swaps if len(arr) != len(target): return False arrHash, targetHash = defaultdict(int), defaultdict(int) for i in range(len(arr)): if arr[i] in arrHash: arrHash[arr[i]] += 1 if target[i] in targetHash: targetHash[target[i]] += 1 for key, val in arrHash.items(): if val != targetHash[key] or key not in targetHash: return False return True **1290. Convert Binary Number in a Linked List to Integer** binStr = '' cur = head while cur: binStr += str(cur.val) cur = cur.next return int(binStr, 2) **2455. Average Value of Even Numbers That Are Divisible by Three** class Solution: def averageValue(self, nums: List[int]) -> int: subarr = [] for num in nums: if num % 2 == 0 and num % 3 == 0: subarr.append(num) if len(subarr) == 0: return 0 return sum(subarr)//len(subarr) **3065. Minimum Operations to Exceed Threshold Value I** nums.sort() count = 0 for num in nums: if num >= k: return count count += 1 **2733 Neither Minimum nor Maximum** return sorted(nums)[1] if len(nums) > 2 else -1 **2413 Smallest Even Mutiple** Given int n. Smallest + int that is mutiple of 2 and n if n % 2 != 0: return n * 2 return n **1913. Maximum Product Difference Between Two Pairs** O(n) solution: l1, l2 = -float('inf'), -float('inf') s1, s2 = float('inf'), float('inf') for num in nums: if num > l1: l2, l1 = l1, num elif num > l2: l2 = num if num < s1: s2, s1 = s1, num elif num < s2: s2 = num return (l1*l2) - (s1*s2) sort, take the largest 2, mutiple, subtract by smallest pair. nums.sort() return (nums[-1] * nums[-2]) - (nums[0] * nums[1]) **2358 Max Number of Groups Entering a Competition** Not completeing this problem. grades.sort() if grades[0] == grades[-1]: return 1 groups = 0 i = 0 while i < len(grades): groups += 1 group_size = groups i += group_size return groups I flopped this Q pretty bad. Reverse sort and a greedy algo? grades = sorted(grades, reverse=True) groupGrades = [grades[0]] You know that the right group always has to be > left val. groupGrade = 0 for i in range(1, len(grades)): if groupGrade > groupGrades[-1]: groupGrade = 0 groupGrades.append(groupGrade) [12, 10, 7, 6, 5, 3] [12] [10 + 3] [7 + 5 + 6] So you have a L and R ptr that moves inwards grades = sorted(grades, reverse=True) groupGrades = [grades[0]] while L < R: newGroupGrade = grades[L] while newGroupGrade < groupGrades[-1]: newGroupGrade += grades[R] R -= 1 if newGroupGrade > groupGrades[-1]: groupGrades.append[newGroupGrade] L += 1 return len(newGroupGrade) 2 backtracking problems: **916 Word Subsets** def countChars(word): hashMap = defaultdict(int) for char in word: hashMap[char] += 1 return hashMap maxWord2hash = defaultdict(int) for word in words2: wordHash = countChar(word) for char, count in wordHash.items(): maxWord2hash[char] = max(maxWord2hash[char], count) res = [] for word in words1: word1hash = countChars(word) for key, val in maxWord2hash.items(): if key not in word1hash or word1hash[key] < val: break else: res.append(word) return res You have to calculate the max freq of each char in word2 Given words1 and words2. str b is subset of str a if every latter in b occurs in a (multiplicity). This is not a backtracking problem... def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: res = [] word2hash = {} for word in words2: for char in word: if char in word2hash: word2hash[char] += 1 else: word2hash[char] = 1 for word in words1: word1hash = {} for char in word: if char in word1hash: word1hash[char] += 1 else: word1hash[char] = 1 for key, val in word2hash.items(): if val < word1hash[key]: break else: res.append(word) return res H2 e:2 H1 e:3 **2044 Count Number of Maximum Bitwise-OR Subsets** def countMaxOrSubsets(nums): maxOr = 0 count = 0 def subsetOR(subset): res = 0 for num in subset: res |= num return res def backtrack(start, path): nonlocal maxOR, count if path: curOr = subsetOR(path) if curOR > maxOR: maxOR = curOR count = 1 elif curOR == maxOR: count += 1 for i in range(start, path): path.append(nums[i]) backtrack(i+1, path) path.pop() backtrack(0, []) return count Find max bitwise OR subset of nums. Return num of diff non-empty subsets. This is a pretty standard backtrack subset algo. def countMaxOrSubsets(self, nums: List[int]) -> int: res = [] def subsetOR(subset) def backtrack(start, path): res.append[path[:]] return for i in range(start, len(nums)): path.append(num[i]) backtrack(i+1, path) path.pop() backtrack(start, []) return len(res) - 1 **Maximum Strength of a Group** def maxStrength(self, nums: List[int]) -> int: num = sorted(nums) res = 1 largestNeg = None if len(num) == 2 and num[0] < 0: return num[1] for i in range(len(num)): if num[i] < 0: if largestNeg is None or num[i] > largestNeg: largestNeg = num[i] if num[i] != 0: res *= num[i] return res if res > 0 else res // largestNeg nums = [-1,-7,-5,7,7,0,9,0,-5,-6] print = [-7, -6, -5, -5, -1, 0, 0, 7, 7, 9] -7, -6, -5, -5, -1, 7, 7, 9 You have to have a even group of negs. Try prefix sum? But it mutiplication. I wonder if there is a trick to extract prefix sum from R - L at O(1) time. [3,-1,-5,2,5,-9] -> [3,−3,15,30,150,−1350] i j i j Lets try to extract val between i-j inclusive from the prefix sum: −1×−5×2=5×2=10 To find the sub sum, you can do R/L. You don't use prefix sum for this. Oh the students do not have to be connected. Sort the arr: Mutiply the smallest neg numbers with all the pos numbers. But ensure that before you get to 0, the sum of the neg > 0 nums = sorted(nums) res = 1 for i in range(len(nums)-1): if nums[i] < 0: if num[i+1] >= 0: if res < 0: res =/ num[i] res += nums[i] return res [-,+,+,+] i What if you just loop through and store the smallestNeg? If at end res + good, else return res / smallest neg, if not smallestNeg, return res num = sorted(nums) res = nums[0] smallestNeg = None for i in range(1, len(nums)): if nums[i] >= 0: smallestNeg = nums[-1] res *= nums[i] return res if res > 0 else res // smallestNeg Also, you must skip 0s [-5,-4,-4] To find the largest neg: for num in arr: if num < 0: if largestNeg is None or num > largestNeg: largestNeg = num [-9, -5, -1, 2, 3, 5] largestNeg = -1 **2730 Find the Longest Semi-Repetitive Substring** GPT's more refined method: L = 0 maxLength = 0 pairCount = 0 for R in range(1, len(s)): if R > 0 and s[R] == s[R] - 1: pairCount += 1 while pairCount > 1: if s[L] == s[L+1]: pairCount -= 1 L += 1 maxLength = max(maxLength, R - L + 1) return maxLength Few issues highlighted by GPT: pairIndex = - 1 pair = False maxLength = 0 L = 0 for R in range(len(s) - 1): if s[R] == s[R + 1]: if not pair: pair = True pairIndex = R else: maxLength = max(R - L + 1, maxLength) while L <= pairIndex: L += 1 pair = False pairIndex = R maxLength = max(len(s) - L, maxLength) return maxLength def for consecutive pair = if there is at most one consecutive pair of same digits. Could not understand the Q Assume, is pair if palindrome? Nope this is a trivial sliding window problem. 1) Make hashmap 2) move left, when >1 pair, move right by default hashMap = {} maxLength = 0 for R in range(len(s)): if s[R] not in hashMap: maxLength = max((R - L + 1), maxLength) hashMap[R] = 1 while hashMap[s[R]] > 1: L += 1 hashMap[s[R]] -= 1 Wait no you move by pairs. We dont have to track the val of the pairs? No we do. If s[L] == pair val we remove it? pairIndex pair = False maxLength = 0 for R in range(len(s)-1): if s[R] == s[R+1]: if not pair: pair = True pairIndex = R else: maxLength = max(R - L, maxLength) while L < pairIndex: L += 1 return maxLength **1090 Largest Values From Labels** Ok, the goofball mistake I made is to try to manually iterate through labels even if it may be unsorted. We would have to use a ditc: value, label = tup[i] if label not in label_count: label_count[label] = 1 if label_count[label] < useLimit: res += value curNum += 1 label_count[label] += 1 i += 1 I don't think you need to sort it, but nowhere in the problem does it say its sorted. tup = [] for i in range(len(values)): tup.append((values[i], labels[i])) tup = sorted(tup) curNum, curUseLimit, i, res = 0, 0, 0, 0 while curNum < numWanted: curLabel = tup[i][1] if curUseLimit < useLimit: res += values[i] curNum += 1 curUseLimit += 1 i += 1 else: while tup[i][1] == curLabel: i += 1 return res //May 14 2024 **1090 Largest Values From Labels** Greedy algo. Only choose M items. Only choose L items of same label. Gonna store in tuple: tup = [] for val in range(len(values)): tup.append((values[i], labels[i])) tup = sorted(tup) curNum, curUseLimit = 0, 0 while curNum < numWanted: if curNum < numWanted: #check label curLabel = tup[i][1] if curUseLimit < useLimit: res += values[i] curNum += 1 curUseLimit += 1 i += 1 else: while tup[i][1] == curLabel: #skip the vals of the same label i += 1 #You have to count the occurance of labels **3096 Minimum Levels to Gain More Points** Given arr possible len n. if possible[i] == 0: impossible Point += 1 if clear, -= if fail. Alice starts for x turns. Then bob plays for rest. return min levels Alice plays to gain more points than bob. What if you just keep a running sum of the 1s? Or better yet the score? [1,0,1,0] -> [1,0,1,0], return 1 [1,1,1,1,1] -> [1,2,3,4,5] return 3 s s = selected val. arr[-1] - s < s, return i if i > 0 else return -1 (if not i, return -1 as well) arr = [possible[0]] for i in range(1, len(possible)): if possible[i] == 1: arr.append(possible[-1] + 1) else: arr.append(possible[-1] - 1) for i in range(len(arr)): if arr[-1] - arr[i] < arr[i]: return i + 1 return -1 **915 Partition Array into Disjoint Intervals** Partitioning always exisits. The arr len could be up to 10^5 so at most the run time must be O(n^2). Maybe even not. We len(left) + len(right) = len(arr) maxLeft = 0 for i in range(len(num)): maxLeft = max(maxLeft, nums[i]) #for all vals after, [M+1:] > maxLeft. We dont want to keep checking right side. What if keep a hashmap of key = val, val = index? Finding things on the hash map would be O(n^2). Q: What if you go through it and the max occured value for L -> R? [5,0,3,8,6] then becomes [5, 5, 5, 8, 8] arrA Then iterate through it again and find the min val from R -> L: [5,0,3,8,6] becomes [0, 0, 3, 6, 6] arrB Then you simply find the index where arrA > arrB 6 6 3 0 0 -> 00366 arrA, arrB = [nums[0]], [nums[-1]] for i in range(1, len(nums)): arrA.append(max(arrA[-1], nums[i]]) for j in range(len(nums) - 2, - 1, -1): arrB.append(max(arrA[-1], nums[j]) arrB = arrB[::-1] for i in range(len(nums): if arrA[i] >= arrB[i]: return i + 1 **92 Reverse Linked List II** def reverseBetween(head: ListNode, left: int, right: int) -> ListNode: dummy = ListNode(0) dummy.next = head cur = dummy leftNode, rightNode = None, None prevLeft, rightNext = None, None # Traverse to find the positions and nodes position = 0 while position <= right: if position == left - 1: prevLeft = cur if position == left: leftNode = cur if position == right: rightNode = cur rightNext = rightNode.next break cur = cur.next position += 1 prev = rightNext cur = leftNode while cur != rightNext: cur.next, prev, cur = prev, cur, cur.next if prevLeft: prevLeft.next = rightNode return dummy.next dummy = ListNode(0) cur = dummy leftNode, rightNode = None, None prevLeft, rightNext = None, None while right > 0: left -= 1 right -= 1 if left == 1: prevLeft = cur if left == 0: leftNode = cur if right == 0: rightNode = cur if rightNode.next: rightNext = rightNode.next cur = cur.next cur = prevLeft prev = None while cur != rightNext: cur.next, prev, cur = prev, cur, cur.next prevLeft.next = rightNode rightNext.next = leftNode return dummy.next def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: **1219 Path with Maximum Gold** def getMaxiumnGold(self, grid): dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] R, C = len(grid), len(grid[0]) globalMax def backtrack(r, c, pathSum, globalMax): nonlocal globalMax if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] == 0: return max(globalMax, pathSum) tmp = grid[r][c] grid[r][c] = 0 for dr, dc in dirs: backtrack(r+dr, c+dc, pathSum + tmp) grid[r][c] = tmp for r in range(R): for c in range(C): if grid[r][c] != 0: backtrack(r, c, 0) return globalMax Given m x n grid. Cell = amount of gold. Return max gold (can't visit same cell more than once). Can't visit with 0 gold. Can start at anywhere with gold. Grid size under 100 x 100. Have a for loop. Locate every single cell as a potential starting point. Pass it in as a start to the backtrack function. This is similar to all paths. pathSum = for path in paths: res.append(sum(path)) def getMaximumGold(self, grid: List[List[int]]) -> int: dirs = [[1,0], [-1,0], [0,1], [0,-1]] R, C = len(grid), len(grid[0]) for r in range(R): for c in range(C): if grid[r][c] != 0: backtrack(r,c,0,0) def backtrack(r, c, pathSum, globalMax): if grid[r][c] == 0 or r < 0 or r > R or c < 0 or c > C: return tmp = grid[r][c] grid[r][c] = 0 for nr, nc in dirs: curSum = pathSum + grid[r][c] backtrack(r+nr, c+nc, curSum, max(globalMax, curSum)) grid[r][c] = tmp #this is == pop() return globalMax //May 13 2024 --Review Merge Sort-- def merge(arr, L, M, R): def merge(arr, L, M, R): left, right = arr[L:M+1], arr[M+1:R+1] i, j, k = L, 0, 0 while j < len(left) and k < len(right): if arr[j] < arr[k]: arr[i] = left[j] j += 1 else: arr[i] == right[k] k += 1 i += 1 while j < len(left): arr[i] = left[j] j += 1 i += 1 while k < len(right): arr[i] = right[k] k += 1 i += 1 def mergeSort(arr, L, R): if L < R: M = (L + R) // 2 mergeSort(arr, L, M) mergeSort(arr, M + 1, R) merge(arr, L, M, R) mergeSort(arr, 0, len(arr)) return arr **148 Sort List** Given head, return list after sorting. arr = [] cur = head while cur: arr.append(cur.val) cur = cur.next cur = head arr = sorted(arr) i = 0 while cur and i < len(arr): cur.val = arr[i] cur = cur.next i += 1 return head --Review-- def binarySearch(arr, target): left, right = 0, len(arr) - 1 while left < right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid return left **162 Find Peak Elem** nums[left] < nums[mid] and nums[right] < nums[mid] Q: How do you shrink the bounds? if nums[mid] < nums[left]: left = mid if nums[mid] < nums[right]: right = mid BS method: class Solution: def findPeakElement(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] < nums[mid + 1]: left = mid + 1 else: right = mid return left A peak elem is an elem greater than neighbors. Find and return peak elem. Algo must be O(logn) time. Most likely a BS. But lets do the trivial solution first anyways. class Solution: def findPeakElement(self, nums: List[int]) -> int: if len(nums) == 1: return 0 if len(nums) == 2: return nums.index(max(nums)) if nums[0] >= nums[1]: return 0 if nums[-1] >= nums[-2]: return len(nums) - 1 for i in range(1, len(nums) - 1): if nums[i - 1] <= nums[i] >= nums[i + 1]: return i **875 Koko Eating Bananas** def canFinish(speed): hours = 0 for pile in piles: hours += (pile + speed - 1) // speed return hours <= h left, right = 1, max(piles) while left < right: mid = (left + right) // 2 if canFinish(mid): right = mid else: left = mid + 1 return left **1011. Capacity To Ship Packages Within D Days** Corrections: def canShipWithinDays(capacity): currentWeight = 0 daysNeeded = 1 for weight in weights: if currentWeight + weight > capacity: daysNeeded += 1 currentWeight = weight else: currentWeight += weight if daysNeeded > days: return False return True left, right = max(weights), sum(weights) while left < right: mid = (left + right) // 2 if canShipWithinDays(mid): right = mid else: left = mid + 1 return left ith package has weight[i]. May not load more than max capacity. Return least weight that result in all packages shipped within day days. In example: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 sum (weights) must < days * weight. But I can think of edge case where: [99,99,1,1,1,1,1] days = 5 so minWeight = max(weights) In this example, we split the weights like: (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) if we did sum([1,2,3,4,5,6,7,8,9,10]) = 5 * x, which is 11. something which is incorrect. What if we did binary search on the possible values of maxWeight and just test the value? left = max(weights) right = sum(weights) def shipCpacity(maxWeight): tmp = maxWeight for weight in weights: if maxWeight < 0: totalDays += 1 maxWeight = tmp maxWeight -= weight if totalDays > day: return False return True while left < right: mid = (lower + upper) // 2 if shipCpacity(mid): #decrease the guess val right = mid else: left = mid + 1 return left def shipWithinDays(self, weights: List[int], days: int) -> int: **786 K-th Smallest Prime Fraction** Given arr. Return ith biggest fraction where the fraction is calculated as arr[i]/arr[j]. You return the values of the num and den. def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]: left, right, n = 0.0 , 1.0, len(arr) while left < right: mid = (left + right) / 2 count, maxFrac = 0, 0.0 num, den = 0, 1 j = 1 for i in range(n): while j < n and arr[i]/arr[j] < mid: j += 1 count += n - j frac = arr[i]/ arr[j] if frac > maxFrac: maxFrac = frac num, den = arr[i], arr[j] if count == k: return [num, den] elif count < k: left = mid else: right = mid Returns wrong answer. Not doing this Q. **861 Score After Flipping Matrix** Entire code: R, C = len(grid), len(grid[0]) for r in range(R): if grid[r][0] == 0: for c in range(C): grid[r][c] = 1 - grid[r][c] for c in range(C): oneCount = 0 for r in range(R): if grid[r][c] == 1: oneCount += 1 if oneCount < R / 2: for r in range(R): grid[r][c] = 1 - grid[r][c] res = 0 for r in range(R): rowStr = '' for c in range(C): rowStr += str(grid[r][c]) res += int(rowStr, 2) return res Given m x n matrix grid. Move = toggle all r/c 1->0 and 0 -> 1. Score = sum of rows (binary #). Return highest possible score after any number of moves. First sub problem = int -> bin. We calculate the score - > this comes after we flip all the bits. R, C = len(gird), len(grid[0]) scores = [] for r in R: rowStr = '' for c in C: rowStr += grid[r][c] scores.append(rowStr) for score in scores: res += int(b, 2) return res Due to the nature of the array being binary, we want to ensure that ealier colums = 1. We dont need to calculate the scores before knowing what is optimal. Start off with row. Rule: ensure 1st bit always 1: for r in R: if grid[r][0] == 0: #flip bits for c in C: if grid[r][c] == 0: grid[r][c] = 1 else: grid[r][c] = 0 To ensure that col is optimal, we simply count the number of 1s and flip if # of 0s > 1s. for c in C: oneCount = 0 for r in R: if grid[r][c] == 1: oneCount += 1 if oneCount < len(grid) // 2: for r in R: if grid[r][c] == 0: grid[r][c] = 1 else: grid[r][c] = 0 def matrixScore(self, grid: List[List[int]]) -> int: //May 12 2024 **How Many Numbers Are Smaller Than the Current Number** class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: tmp = sorted(nums) mapping = {} res = [] for i in range(len(tmp)): if tmp[i] not in mapping: mapping[tmp[i]] = i for i in range(len(nums)): res.append(mapping[nums[i]]) return res **Find Target Indices After Sorting Array** class Solution: def targetIndices(self, nums: List[int], target: int) -> List[int]: nums = sorted(nums) res = [] for i, num in enumerate(nums): if num == target: res.append(i) return res **Score of a String** class Solution: def scoreOfString(self, s: str) -> int: res = 0 for i in range(1, len(s)): res += abs(ord(s[i]) - ord(s[i - 1])) return res **Divisible and Non-divisible Sums Difference** class Solution: def differenceOfSums(self, n: int, m: int) -> int: num1, num2 = 0, 0 for i in range(1, n+1): if i % m == 0: num2 += i else: num1 += i return num1 - num2 **Count Negative Numbers in a Sorted Matrix** class Solution: def countNegatives(self, grid: List[List[int]]) -> int: res = 0 for row in grid: for num in row: if num < 0: res += 1 return res **Type of Triangle** class Solution: def triangleType(self, nums: List[int]) -> str: if max(nums) < sum(nums) - max(nums): if len(set(nums)) == 1: return 'equilateral' elif len(set(nums)) == 2: return 'isosceles' return 'scalene' return 'none' **Number of Students Doing Homework at a Given Time** class Solution: def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int: res = 0 for i in range(len(startTime)): if startTime[i] <= queryTime <= endTime[i]: res += 1 return res **Check If a Word Occurs As a Prefix of Any Word in a Sentence** class Solution: def isPrefixOfWord(self, sentence: str, searchWord: str) -> int: wordList = sentence.split(' ') for i, word in enumerate(wordList): if searchWord in word and searchWord == word[:len(searchWord)]: return i + 1 return -1 **Maximum Product of Two Elements in an Array** Optimal solution: class Solution: def maxProduct(self, nums: List[int]) -> int: nums = sorted(nums) return (nums[-1] - 1) * (nums[-2] - 1) Crappy solution: class Solution: def maxProduct(self, nums: List[int]) -> int: max_val = 0 for i in range(len(nums)): for j in range(i+1, len(nums)): max_val = max(max_val, (nums[i]-1)*(nums[j]-1)) return max_val **Shuffle the Array** class Solution: def shuffle(self, nums: List[int], n: int) -> List[int]: nums1 = nums[:n] nums2 = nums[n:] res = [] for i in range(n): res.append(nums1[i]) res.append(nums2[i]) return res **Find Lucky Integer in an Array** class Solution: def findLucky(self, arr: List[int]) -> int: hash_map = {} for num in arr: if num in hash_map: hash_map[num] += 1 else: hash_map[num] = 1 max_lucky = 0 for key, val in hash_map.items(): if key == val: max_lucky = max(key, max_lucky) return max_lucky if max_lucky != 0 else -1 **3028. Ant on the Boundary** Correct solution: class Solution: def returnToBoundaryCount(self, nums: List[int]) -> int: res, cumulative_sum = 0, 0 for num in nums: cumulative_sum += num if cumulative_sum == 0: res += 1 return res I misread the Q- my solution: from typing import List class Solution: def returnToBoundaryCount(self, nums: List[int]) -> int: res, cumulative_sum = 0, 0 for num in nums: prev = cumulative_sum cumulative_sum += num if (prev < 0 and cumulative_sum > 0) or (prev > 0 and cumulative_sum < 0): res += 1 return res **3099. Harshad Number** Solution 2: def sumOfTheDigitsOfHarshadNumber(x) -> int: sum = 0 num = x while num > 0: sum += num % 10 num //= 10 if x % sum == 0: return sum return -1 Solution 1: class Solution: def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int: strx = str(x) sum = 0 for digit in strx: sum += int(digit) if x % sum == 0: return sum return -1 **1108. Defanging an IP Address** def defangIPaddr(self, address: str) -> str: return '[.]'.join(address.split('.')) **1930 Unique Length-3 Palindromic Subsequences** The O(n^2) solution uses a hashmap. You have: def countPalindromicSubsequence(s): count = 0 chars = set(s) for char in chars: first, last = s.find(char), s.rfind(char) count += len(set(s[first+1:last])) return count char: indexes The pattern to make palindrome is 1) all char are the same 2) first and last char are the same. Since this question requires unique palindromes, it makes the q easier. 1) Loop through the arr and add char + indicies to hash map 2) count all the char where len(hash_map[letter]) >= 3 3) For every char that has len(hash_map[letter]) >= 2 (lets call A) compare with every other item in hashmap (lets call B) and see if you get get indexB < index A < index B. If yes, add that too. Corrected code: class Solution: def countPalindromicSubsequence(self, s: str) -> int: res = set() # Use a set to avoid counting duplicates def isPalindrome(s): return s == s[::-1] for i in range(len(s)): for j in range(i + 1, len(s)): for k in range(j + 1, len(s)): sub = s[i] + s[j] + s[k] if isPalindrome(sub): res.add(sub) # Add the palindromic subsequence to set return len(res) def countPalindromicSubsequence(self, s: str) -> int: res = 0 def isPalindrome(s1, s2, s3): s = s1 + s2 + s3 return s == s[:-1] for i in range(len(s)): for j in range(i + 1, len(s)) for k in range(j + 1, len(s)) if isPalindrome(s[i] + s[j] + s[k]): res += 1 return res **N-Queens II** class Solution: def totalNQueens(self, n: int) -> int: col, posDiag, negDiag = set(), set(), set() res = [0] def backtrack(r): nonlocal res if r == n: res[0] += 1 return for c in range(n): if c not in col and (r + c) not in posDiag and (r - c) not in negDiag: col.add(c) posDiag.add(r + c) negDiag.add(r - c) backtrack(r + 1) col.remove(c) posDiag.remove(r + c) negDiag.remove(r - c) backtrack(0) return res[0] **51 N-Queens** Convo: Why is it necessary to only place one queen per row? Because you know there is only one queen in a row. That's a part of the constraints. You can't have the same queen in the same diagonal, row, or column. So we only have to do it row by row. Explain the sets for columns, positive diagonals, and negative diagonals. For columns, during the backtracking process, we loop through every column. What we do is for columns, we add the row column to the set, or essentially the columns to the set, as well as positive diagonal which is R plus C, negative diagonal which is R minus C. Because one diagonal has a constant value due to the geometric properties of the 2D matrix. Essentially, we check to see if the column positive diagonals or the negative diagonals are in the set. If they are, that means that there's already an attackable queen there, so we can't place there. That's where we would pop. And that's where the backtracking would occur. What is the process or the purpose of using .join in the context of recording solutions to the in-queue problem? In the context of the problem, simply it wants to answer back the entire solution in the string format. So we have to join the multiple elements together. It's question specific. If it wanted a list of solutions, then we would just do normal append of the shallow copy. Okay, let's tackle question four, deeper understanding. So in the backtracking function for the end queen, why must you remove a queen after the recursive call returns? Well, I mean, that's just very standard backtracking. After all the recursive calls return, that means you've explored all the possible paths in that direction. So you just simply pop and that's the only way to explore other paths. Question five, discuss implications of forgetting to remove the column and diagonal markers from their sets. Well, if we do that, you end up with ghost queens, where in the board, the queen isn't there, but the set still maintains the queen being there. And eventually you end up unable to further progress in the backtracking algorithm. And you miss out on potential solutions that exist, or you could have no solutions when there are solutions that exist. Okay, let's talk about how we can leverage symmetry to optimize this solution. So if we look across the middle columns or column for a even n, the solution to the left half mirror the solution to the right half. And there is also a rotational symmetry where after finding a valid config, you can rotate the board by 90, 270, and 180 degrees. Okay so it's not necessarily the case and this is just an attempt at potential solutions. It doesn't mean the solutions are all valid depending on the placement and the rotation of the boards. This is a shortcut that could potentially have invalid configurations. So we wouldn't know how many solutions there are in an 8x8 unless we actually do it. def solveNQueens(n): col, posDiag, negDiag = set(), set(), set() res, board = [], [] for _ in range(n): board.append(['.'] * n) def backtrack(r): if r == n: solution = [] for row in board: solution.append(''.join(row[:]) res.append(solution) for c in range(n): if c in col or (r+c) in posDiag or (r-c) in negDiag: continue col.add(c) posDiag.add(r+c) negDiag.add(r-c) board[r][c] = 'Q backtrack(r+1) col.remove(c) posDiag.remove(r+c) negDiag.remove(r-c) board[r][c] = '.' backtrack(0) return res Watched some parts of the neet code vid. The key thing to realize is that the vals for r+c and r-c for the diagnals are the same, and we can maintain 'taken' spots via a set. Placing n queens on a nxn board where no two queens can attack eachother. Return all solutions to the n-queen puzzle. We can rep the board with a 2d matrix where Q == queen and . = empty space. We have to make sure that: 1) Row clear 2) Col clear 3) Diagonal clear R, C = len(n), len(n[0]) -> This can be our matrix 1) if r > 2 Q, pop(), backtrack 2) if c > 2 Q, pop, backtrack - we can check that by for c index in every row. 3) Diagnal: if (r + 1, c + 1), (r - 1, c - 1), (r + 1, c -1), (r - 1, c + 1) has another queen, backtrack Q: How do we place a qeen? 1) start off w/ empty board. Done. To place a queen, we have to simply set [r][c] = Q. To backtrack, board[r][c] = '.' The first idea was to check every grid cell repeatedly during backtracking. This is super inefficent. How about we use lists or sets? For each queen, we only place 1 per row. def solveNQueens(n): board = [] for _ in range(n): board.append(['.']*n) def validboard(board): for row in board: if row.count('Q') > 1: return False for def backtrack(r, c, board): board[r][c] = 'Q' if valid board: board[r][c] = '.' **1025 Divisor Game** Given n number. Choose x with 0 < x < n and n % x == 0. You replace a number on the chalkboard with n - x. If a player cannot make a move they lose. Q: Would you select the largest possible n for each step? What is the optimal play for this game? You want to force the other player to n = 1 thus, you want n = 2 and the other player auto-loses. This also means the base case is: if n == 1: return False When n == 3, the only move is to - 1, so 3 is losing. n = 4 is winning. So the trick is to leave the opponent in losing position after move. GPT reponse: def is_winning(n, memo={}): if n in memo: return memo[n] if n == 1: memo[n] == False return False divisors = [] for i in range(1, n): if n % i == 0: divisors.append(i) for x in divisors: if not is_winning(n-x, memo): memo[n] = True return True memo[n] = False return False n = 6 example [1, 2, 3] //May 11 2024 **473 Matchsticks to Square** Ok I give up, this is the Neetcode solution: def makesquare(matchsticks) -> bool: length = sum(matchsticks) // 4 sides = [0] * 4 if sum(matchsticks) / 4 != length: return False This is a subset problem. Recall to form subsets: def subsets(nums): res = [] def backtrack(start, path): res.append(path[:]) return for i in range(start, len(nums): path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return res You can make a matchstick square if you can split the matchsticks into 4 equal lengths. Once again, similar to the palindrome partioning problem. class Solution: def makesquare(self, matchsticks: List[int]) -> bool: def lengthCheck(path, segment): if not path or path[-1] == segment: return True return False def backtrack(start, path): print("Trying path:", path) if start == len(matchsticks) and len(path) == 4: return True for i in range(start, len(matchsticks)): segment = sum(matchsticks[start:i+1]) if lengthCheck(path, segment): path.append(segment) if backtrack(i + 1, path): return True path.pop() print("Backtracking path:", path) return backtrack(0, []) This would not work because you only look a clumps of solutions (groups of solutions that are immediate neighbors). **786. K-th Smallest Prime Fraction** def kthSmallestPrimeFraction(arr, k): n = len(arr) left, right = 0, 1 #these are the range of floating point values (not indices) res = [] while left <= right: mid = (left + right) / 2 j, total , num, den = 1, 0, 0, 0 maxFrac = 0 j = denominator index total = num of fractions <= cur mid num = index of largest fraction found in mid for i in range(n): while j < n and arr[i] >= arr[j] * mid: j += 1 You loop through i index, which I assume is the numerator of the fraction and while j < n (if the denominator is in bounds) and the current numerator >= than denomiator * mid, j += 1. I'm still not sure why arr[i] >= arr[j] * mid is a condidtion to move j? If we re-arrange: arr[i]/arr[j] >= mid, ensures that that fraction always needs to be bigger than mid. But why just bigger? Why not keep moving till its smaller than midpoint? It seems like a rather arbitrary decision. Is this step still not O(n^2) when going towards the midpoint? Yes This makes more sense to me: arr[i] / arr[j] >= mid. This skips over all the fraction where the fraction val is larger than mid. total += n - j Hmmm that intresting. The total val we end up calculating is the total number of possible vals and we store that as a int (without saving any values). All of this belongs in the for i in range(n) for loop. Within that i in range(n) loop: if j < n and maxFrac < arr[i] * 1.0 / arr[j] maxFrac = arr[i] * 1.0 / arr[j] num, den = i, j Why not just do arr[i] / arr[j] instead of arr[i] * 1.0 / arr[j]. Reason, there is non in python 3. if j < n and maxFrac < arr[i]/arr[j]: maxFrac = arr[i]/arr[j] num, den = i, j if total == k: res = [arr[num], arr[den]] break if total > k: right = mid else: left = mid return res mid could take on the values of 0.5, 0.25, 0.125 if total keeps > k right. //May 10 2024 **786. K-th Smallest Prime Fraction** Binary Serach solution attempt 2: def kthSmallestPrimeFraction(arr, k): n = len(arr) left, right = 0, 1 #these are the range of floating point values (not indices) res = [] while left <= right: mid = (left + right) / 2 j, total , num == 1, 0, 0, 0 All of my runtimes were 1000ms +. There are some folks that did it with a approx 60 ms runtime. How? You can actually use binary Search with this question. def kthSmallestPrimeFraction(arr, k): n = len(arr) low, high = 0, 1 #0 and 1 are not the possible vals of the fractions. arr[i] could > arr[j] The best way to determine the min and max val are: min_val, max_val = min(arr), max(arr) or since it is sorted we could just do: min_val, max_val = arr[1], arr[-1] low = min_val/max_val high = max_vla/min_val We are given a sorted array - that should scream binary search. Q1: how do we define the mid point for the search? [small -> large], we know that the abs min and max = 0 and 1 respectivly. What we want to observe is: 1) The more left i is and right j is, = closer to 0 2) The more right i is (closer to j), closer to 1 So the basics of how to serach is, if fraction > value, i moves to left search space and or r moves to right search space. But how do we even know what value we are searching for? Would we even need a heap? [1,2,3,4,5,6,7,8,9,10] Since we know we can only move i or j, what if we move it only ever finding the kth smallest and stop? smallest = arr[0] / arr[-1] 2nd smallest: 1) arr[0] / arr[-2] move i += 1 2) arr[i] / arr[-1] move j -= 1 We take the min of 1) 2). Store the res in an array. And iterate. For the next compare, we check to see if we move, i, j, or the previous bigger one (res[-1]) produces a smaller value. We iterate on this till we find kth smallest and then simply return arr[i] and arr[j]. What I just (assumed) I came up with is a sliding window or greedy selection method. Here we use a min-heap to track + select smallest cur fraction then move all indices. The way GPT did it was: def kthSmallestPrimeFraction(arr, k): n = len(arr) heap = [] for j in range(1, n): heap.append((arr[0]/arr[j], 0, j), 0, j) heapq.heapify(heap) Another way to look at the list is as (fraction_val, numerator_index, denominator_index). res = None for _ in range(k): val, i, j = heapq.heappop(heap) In this case, i will (numerator_index) will always be 0. What about a case where k > len(nums)? Or how about if we get a smaller value by moving i + 1 and setting j to -1 instead? You take the first k fractions set. Lets say k = 3: (arr[0]/arr[1], 0, 1) (arr[0]/arr[2], 0, 2) (arr[0]/arr[3], 0, 3) if i + 1 < j: #this ensures that j is always larger, we push to the heap. push(arr[1]/arr[1]) Q: Why do you i + 1 when i + 1 < j? Would you want to not keep iterating j? Ok wait a min, the code if i + 1 < j: heapq.heappush(heap, (arr[i+1]/arr[j], i+1, j)) The core reason that using a min heap is efficent is because we only have to maintain O(k) space. The complexity is O(n^2 logk). max_heap = [] for i in range(len(arr)): for j in range(i+1, len(arr)): heapq.heappush(max_heap, (-(arr[i]/arr[j]), arr[i], arr[j])) if len(max_heap) >= k: heapq.heappop(max_heap) return [max_heap[0][1], max_heap[0][2]] If you want to keep the kth smallest, you're looking at a maxheap. Brute force method without using a heap: fractions = [] for i in range(len(arr)): for j in range(i + 1, len(arr)): fractions.append((arr[i] / arr[j], arr[i], arr[j])) sorted_fractions = sorted(fractions) return [sorted_fractions[k-1][1], sorted_fractions[k-1][2]] Why would we need to use a heap for this? Because we have to return the kth smallest fraction. 1) We generate every possible fraction O(n^2) 2) Min heap, and pop k times def kthSamllestPrimeFraction(arr, k): arr2 = [] for i in range(len(arr)): for j in range(i+1, len(arr)): res.append(arr[i] // arr[j]) return sorted(arr2)[k] **Clone Graph** class Solution: def cloneGraph(node)-> Node: oldToNew = {} if node in oldToNew: return oldToNew[node] copy = Node(node.val) oldToNew[node] = copy for nei in node.neighbors: copy.neighbors.append(dfs(nei)) return copy return dfs(node) if node else None 1) We want to make a copy of the node 2) We connect the copy to the neighbors //May 9 2024 **1849 Splitting a String Into Descending Consecutive Values** def splitString(s) -> bool: def canAppend(path, segment): if not path or int(path[-1] - int(segment) == 1: return True return False def backtrack(start, path): if start == len(s): return len(path) > 1 for i in range(start, len(s)): segment = s[start:i+1] if canAppend(path, segment): path.append(segment) if backtrack(i+1, path): return True path.pop() return backtrack(0, []) New GPT response: GPT response (stupid): def splitString(s) -> bool: def segmentCheck(prev, segment): cur = int(segment) if prev is not None and prev - cur == 1: return True return False def backtrack(start, path): if start == len(s): return False if segmentCheck(prev, segment): if i == len(s) - 1: return True if backtrack(i+1, int(segment)): return True return False for i in range(len(s) - 1): Given a string that consists of only digits. This question is very similar to 131 Palindrome Partitioning. def splitString(s) -> bool: def segmentCheck(segment): if res and if int(res[-1]) - int(segment) == 1: return True return False def backtrack(start, path): if start = len(s): res.append(path[:]) return for i in range(len(s)): segment = s[start:i+1] if segmentCheck(segment): path.append(segment) backtrack(i+1, path) path.pop() res = [] backtrack(0, []) return True if res else False **17 Letter Combinations of a Phone Number** GPT Response: def letterCombinations(digits): if not digits: return [] adj_list = {} res = [] def backtrack(index, path): if len(path) == len(digits): res.append(''.join(path)) return digit = digits[index] for char in adj_list[digit]: path.append(char) backtrack(index + 1, path) path.pop() backtrack(0, []) return res Loop through each number and find the combination of each. 1) lets create an adj list for each number: 2: ['a','b','c'] ... 9: ['w','x','y','z'] We loop through, and create a combination using each of the numbers (this is a combination problem). def letterCombinations(digits): adj_list = { '2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'], '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'], '7': ['p', 'q', 'r', 's'], '8': ['t', 'u', 'v'], '9': ['w', 'x', 'y', 'z'] } res = [] def backtrack(start, path): if len(path) == len(s): path.append('.'.join(path)) return for digit in digits: for char in adj_list[digit]: path.append(char) backtrack(index + 1, path) path.pop() backtrack(0, []) return res **3075 Maximize Happiness of Selected Children** Given array of happiness + pos int k. 1) we want a time var that += 1 for each turn. Everytime we pick a children, we - happiness by time. The min val must be 0 we can do max(0, happiness - time). lets reverse sort array and count the number of pops. total_happiness = 0 happiness = sorted(happiness, reverse = True) time = 0 while k > 0: total_happiness += max(0, happiness.pop() - time) k -= 1 time += 1 return total_happiness **93 Restore IP Addressess** def restoreIPAddresses(s): def isValid(segment): if len(segment) == 0 or (segment[0] == '0' and len(segment) > 1): return False if int(segment) >= 255 or int(segment) <= 0: return False def backtrack(start, path): if len(path) == 4 and start == len(s): res.append('.'.join((path)) return if len(path) == 4 or start == len(s): return for i in range(start, min(start + 3, len(s))): segment = s[start:i+1] if isValid(segment): path.append(segment) backtrack(i + 1, path) path.pop() res = [] backtrack(0 , []) return res //May 8 2024 **93 Restore IP Addresses** You end up returning: ["251.53.5.1","251.53.5.1","251.53.5.1","251.53.5.3","251.53.5.5","251.55.1.1","251.55.1.1","251.55.1.3","251.55.1.5","251.5.1.1","251.5.1.3","251.5.1.5","251.5.1.3","251.5.1.5","251.5.3.5","255.5.1.1","255.5.1.1","255.5.1.3","255.5.1.5","255.5.1.1","255.5.1.3","255.5.1.5","255.5.1.3","255.5.1.5","255.5.3.5","21.1.1.1","21.1.1.3","21.1.1.5","21.1.1.3","21.1.1.5","21.1.3.5","21.1.1.3","21.1.1.5","21.1.3.5","21.1.3.5"] when the expected is: ["255.255.11.135","255.255.111.35"]... Ok this mis-conception that you have is that you are passing in a substring as candidate! def restoreIPAddresses(s): def isVald(segment): if not 0 <= int(segment) <= 255: return False if len[0] == '0' and len(segment) > 1: return False return True def backtrack(start, path): if start == len(s) and len(path) == 4: res.append(''.join(path[:])) return for i in range(start, len(s)): candidate = s[start::i+1] if isValid(candidate): path.append(candidate) backtrack(i+1, path) path.pop() res = [] backtrack(0, []) return res Ooops. This cannot have leading zeros either. This is a subset(?) problem? The subfunction isValid must: 1) contain 4 dots (we must partition the s in 4 ways) 2) each int is between 0-255 def restoreIpAddresses(s): def isValid(s): if len(s) != 3: return False for num in nums: if int(num) > 255 or int(num) < 0: return False return True def backtrack(start, path): if start == len(s) res.append(path[:]) return for i in range(start, len(s)): candidate = s[start:i+1] if isValid(candidate): path.append(candidate) backtrack(i+1, path) path.pop() res = [] backtrack(0, []) return res **506 Relative Ranks** At the fastest this is O(n) time. Sort. Then do index of + 1. sorted_score = sorted(score) res = [] for placement in score: output = sorted_score.indexof(placement) + 1 if output == 1: res.append('Gold Metal') elif output == 2: res.append('Silver Metal') elif output == 3: res.append('Bronze Metal') else: res.append(str(ouput)) return res **76 Minimum Window Subtring** GPT Solution: def minWindow(s, t) -> str: m, n = len(s), len(t) t_hash = {} for char in t: t_hash[char] = t_hash.get(char, 0) + 1 L = 0 window_hash = {} min_len = float('inf') min_subtr = '' def valid_window(t_hash, window_hash): for char, count in t_hash.items(): if window_hash.get(char, 0) < count: return False return True for R in range(m): char = s[R] if char in t_hash: window_hash[char] = window_hash.get(char, 0) + 1 while valid_window(t_hash, window_hash): if R - L + 1 < min_len: min_len = R - L + 1 min_substr = s[L:R+1] left_char = s[L] if window_hash[left_char] == 1: del window_hash[left_char] else: window_hash[left_char] -= 1 L += 1 return min_substr def minWindow(s, t) -> str: m, n = len(s), len(t) t_hash = {} for char in t: if char not in t_hash: t_hash[char] = 1 else: t_hash[char] += 1 L = 0 window_hash = {} min_substr = '' def valid_window(t_hash, window_hash): for char, count in t_hash.items(): if window_hash.get(char, 0) < count: return False return True for R in range(m): char = s[R] if char not in t_hash: window_hash[char] = 1 else: window_hash[char] += 1 if valid_window(t_hash, window_hash): if len(min_substr) > R - L + 1: min_substr = s[L:R] if window_hash[s[L]] == 1: del window_hash[s[L]] else: window_hash[s[L]] -= 1 L += 1 return min_subtr //May 7 2024 **76 Minimum Window Substring** Boiler plate code for variable sliding window: def sliding_window(arr, check_condition): L = 0 res = float('inf') window_data = 0 for R in range(len(arr)): window_data += arr[R] while something window_data -= arr[L] L += 1 Find the min substr. len(s) = m, len(t) = n return so the window includes every char t (including dups) for t, we prob would want a hashmap to track the total num of each char: t_hash = {} for char in t: if char not in t_hash: t_hash[char] = 1 else: t_hash[char] += 1 Another sub problem we want to solve is if the string in the window meets the requirment of all the letters in t is in window. window_hash = {} for char in window_hash: if window_hash[char] < t_hash.get(char, 0): return False So if we return false, we want to move R without moving L. **131 Palindrome Partitioning** Ok you dummy. Misread the question again. def isPalindrome(sub) -> bool: return sub == sub[::-1] def backtrack(start, path): if start == len(s): res.append(path[:]) return for i in range(start, len(s)): candidate = s[start:i+1] path.append(candidate) backtrack(i+1, path) path.pop() res = [] backtrack(0, []) return res Given string s, partition s in a way that every substring is a palindrome. This is a subset problem. You add path if s + path[:] is palindrome. 1) create isPalindrome func: def isPalindrome(s): mid = len(s) // 2 return s[:m] == s[m:][::-1] def isPalindrome(s): return s == s[::-1] 2nd method is more efficent 2) calculate subsets: def partition(s): res = [] def backtrack(start, path): if isPalindrome(s + path): res.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) backtrack(i+1, path) path.pop() backtrack(0, []) return res **79 Word Search** Additional optimizations and writing it in a diff recursive method: def exist(board, word) -> bool: if not board or not word: return False R, C = len(board), len(board[0]) char_count = {} for r in range(R): for c in range(C): char = board[r][c] if char in char_count: char_count[char] += 1 else: char_count[char] = 1 word_count = {} for char in word: if char in word_count: word_count[char] += 1 else: word_count[char] = 1 for char in word_count: if word_count[char] > char_count.get(char, 0): return False def dfs(r, c, index): if index == len(word): return True if r < 0 or r >= R or c < 0 or c >= C or board[r][c] != word[index]: return False tmp, board[r][c] = board[r][c], '#' found = dfs(r + 1, c, index + 1) or dfs(r - 1, c, index + 1) or \ dfs(r, c + 1, index + 1) or dfs(r, c - 1, index + 1) board[r][c] = tmp return found for r in range(R): for c in range(C): if board[r][c] == word[0] and dfs(r,c,0) return True return False GPT refined version of the code: def exist(board, word) -> bool: if not board or not word: return False R, C = len(board), len(board[0]) def dfs(r, c, index): if index == len(word) - 1: return board[r][c] == word[index] tmp, board[r][c] = board[r][c], '#' for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= c < nc and board[nr][nc] == word[index+1] and dfs(nr,nc,index+1): return True board[r][c] = tmp return False for r in range(R): for c in range(C): if board[r][c] == word[0] and dfs(r,c,0): return True return False Ok looking that this question, it seems like it is DFS w/ backtracking. There is a few things we should keep track of: 1) Q: How do we start the traversal? Answer, the most effective method is to prob loop through, and start at the first starting char. 2) How do we track visited? We can keep set of [r][c] and mark it as visted in a set 3) We pop() the visited var Keep in mind, we don't keep track of the path var to save in mem. def exist(board, word) -> bool: if not board or word: return False R, C = len(board), len(board[0]) def dfs(r,c, index): if r < 0 or r > R or c < 0 or c > C or board[r][c] == '#' or board[r][c] != word[index]: return False if board[r][c] != word[-1]: #if you reach the end and it matches return True board[r][c] == '#' dfs(r+1, c) dfs(r-1, c) dfs(r, c+1) dfs(r, c-1) for r in range(R): for c in range(C): if board[r][c] == word[0]: dfs(r,c, 0) **Permutations II** The trick here is that there is unique numbers so you have to track the index of the permutation rather than the value itself. Answer from GPT: def permuteUnique(nums): nums.sort() res = [] used = [False] * len(nums) def backtrack(path): if len(path) == len(nums): res.append(path[:]) return for i in range(1, len(nums)): if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]): continue used[i] = True path.append(num[i]) backtrack(path) path.pop() used[i] = False backtrack([]) return res Regular permutations: def permuate(nums): res = [] def backtrack(path): if len(path) == len(nums): res.append(path) for num in nums: if num not in path: path.append(num) backtrack(path) path.pop() backtrack([]) return res **2816 Double a Number Represented as a Linked List** Come up with function to mutiple str by 2: carry, doubled = 0, [] for digit in reversed(val): current_double = int(digit) * 2 + carry carry = current_double // 10 doubled.append(current_double % 10) if carry: doubled.append(carry) Corrected version: def doubleIt(head): val = '' cur = head while cur: val += str(cur.val) cur = cur.next val = str(int(val)*2) dummy = ListNode(0) cur = dummy for num in val: cur.next = ListNode(int(num)) cur = cur.next return dummy.next We still (pretty much always want to a dummy node for the case of handling just the head node) Given head. return the head after doubling the sum of linked list: 1-8-9 * 2 = 378 1) Iterate through the linked list. 2) Change the value as you iterate through the array 3) return head (we don't have to do the dummy stuff since we're not deleteing) def doubleIt(head): cur = head val = '' while cur: val.append(cur.val) #dumb mistake cur = cur.next val = str(int(val)*2) cur2 = head for num in val: if cur == None: cur = Node(int(num)) cur.val = int(num) cur = cur.next.next return head //May 6 2024 **2487 Remove Nodes from Linked List** GPT corrected code: if not head or not head.next: return head # Traverse and collect values cur = head arr = [] while cur: arr.append(cur.val) cur = cur.next # Reverse and calculate max from right arr.reverse() max_right = [arr[0]] for i in range(1, len(arr)): max_right.append(max(max_right[-1], arr[i])) # Reverse to original order max_right.reverse() # Rebuild the linked list dummy = ListNode(0) cur = dummy orig = head for i in range(len(arr)): if orig.val >= max_right[i]: cur.next = ListNode(orig.val) cur = cur.next orig = orig.next return dummy.next 0 5-2-13-3-8 Given head. Remove nodes where it is a greater val on the right. There is no way to do this in single run O(N). The question to ask here is, how do you track if the val on the right is bigger? Idea: keep tally of max val seen so far: 5-2-13-3-8 turns into 5-5-13-13-13. Then we do a compare and remove all where input vals < largest_seen_elem. No we actually have to traverse backwards from 8: 13-13-13-8-8 so only return 13, 8 def removeNodes(head): cur = head arr = [] while cur: arr.append(cur.val) cur = cur.next arr1 = arr1[::-1] arr2 = [arr1[0]] for i in ramge(1, arr1): arr2.append(max(arr2[-1]), arr[i]) arr2 = arr2[::-1] #this gets us to 13-13-13-8-8 cur2 = head i = 0 while cur2.next and i < len(arr2): if cur2.val < arr2[i]: cur2.next = cur2.next.next #skips node i += 1 return head //May 5 2024 **47 Permutations II** Since there is repeat vals in the nums, instead of normal permutations doing the check of vals, we can just check if index not in path. Permutaions have to be unique. So we turn into tuple (mutable) -> set (to get rid of dups) -> return. By the def, you are promised that you won't re-use elems. res_index = [] def backtrack(path_index): res_index.append(path_index) for i in range(len(nums)): if i not in path_index: path_index.append(i) backtrack(path_index) path_index.pop() backtrack([]) res = [0] * len(res_index) for i, index in enumerate(res_index): res[index] = nums[i] return res **40 Combination Sum II** def combinationSum2(candidates, target): res = [] def backtrack(start, path, cur_sum): if cur_sum == target: res.append(path[:]) return elif cur_sum > target: return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i + 1, path, cur_sum + candidates[i]) path.pop() backtrack(0, [], 0) res = [] **Subsets II** More elegent solution: for i in range(start, len(nums)): if i > start and nums[i] == nums[i-1]: continue Where continue just skips to the next iteration of the loop. Because of the extra comparisons, this code is actually slower. Jank solution: 1) Create a normal subet 2) turn it into a set() 3) turn it back into a list res = [] def backtrack(start, path): res.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) res = [tuple(subset) for subset in res] return list(set(res)) We had to sort the nums first. **Permutations** def permute(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(path): if len(path) == len(nums): res.append(path[:]) return for num in nums: if num not in path: path.append(num) backtrack(path) path.pop() backtrack([]) return res **Combinations** def combine(n, k): res = [] def backtrack(start, path): if len(path) == k: res.append(path) return for i in range(start, n): path.append(i) backtrack(i+1, path) backtrack(1, []) return res **Combination Sum** def combinationSum(candidates, target): res = [] def backtrack(start, path, current_sum): if current_sum == target: res.append(path[:] return elif current_sum > target: return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i, path, current_sum + candidates[i]) path.pop() backtrack(0, [], 0) return res First try (epic fail): class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def backtrack(start, cur_sum, path): if cur_sum == target: res.append(path[:]) for i in range(start, len(candidates)): cur_sum += candidates[i] path.append(candidates[i]) backtrack(i + 1, cur_sum, path) if cur_sum > target: val = path.pop() cur_sum -= val backtrack(1, 0, []) return res **78 Subsets** The code below returned an empty arr? Forgot to call the func. def subsets(nums): res = [] def backtrack(start, path): res.append(path) return for i in range(start, len(nums)): backtrack(i + 1, path[:] + nums[i]) path.pop() return res **2441 Largest Positive Integer That Exists With Its Negative** Find the largest neg that post also exisit. max_val = -1 numSet = set(nums) for num in nums: if -num in numSet: max_val = max(max_val, abs(num)) return max_val **237 Delete Node in a Linked List** We do not have access to the first node (head). //May 4 2024 **355 Design Twitter** class Twitter: def __init__(self): def postTweet(self, userId: int, tweetId: int) -> None: self.tweetMap[userId].append([self.count, tweetId]) def getNewsFeed(self, userId: int) -> List[int]: def follow(self, followerId: int, followeeId: int) -> None: def unfollow(self, followerId: int, followeeId: int) -> None: Ok, the way that it was implemented, it has a hashmap of [userId] and within it, there is self.count and tweetId. 1) What does self.count do? When we initalized it we started with 0. We have two diff inits 1) tweetMap: userId -> [count, tweetIds] 2) followMap: userId -> set(followeeId) Recall, we are given tweetId and userId. Q: Still have not figured out what count does in this context. Count rep the mechanism for ordering tweets. Count = timestamp for ordering index. Newer tweets have lower counts. getNewsFeed function uses a min-heap for sorting tweets. The more recent the tweet, the lower the count, the top to the top it will appear on the news feed. Ok, lets break down the problem in getNewsFeed(userId) -> List: res = [] minHeap = [] followMap[userId].add(userId) #this is the user id of the logged in user. We go to the follow hashmap, and add the user? This pretty much ensures that the user sees their own tweets, by including their own tweets when constructing news feed. You loop through the followeeId which in this case is a set() can't follow the same person twice. **621 Task Scheduler** Gave up @ 35 min Q: what if you have the letters [a,a,a,a,b,b,c]. You add to heap = processed. Given tasks rep-ed by letters. Cooling time n. 1 cycle = 1 task done. Contraint: identical tasks must be seperated by n intervervals. Return min intervals. The first question to answer is what you keep in the heap. I'm thinking tuple (letter, time left). Or in this case (time left, letter). You want to count the number of pops. everytime you pop, a letter, you set the time for all other instances of the letter to n. Q: what if you store the val of the letter on a hashmap? hashmap: cooldown: letters 1: a 2: c,d 3: 4 n : - minheap: cooldown Q: What if there are no tasks you can do in the cooldown period? Q: What if you pop a the min time? 1) min_time += popped val 2) that letter gets reset to n. Refined approach: Hashmap: { a:time b:time c:time etc etc etc } total_time which is the pop val of the min heap You have to heapify by time there is no way around it. How do we access the shortest time at O(1). Everytime we pop 'A' the time val changes, so the min heap would change as well. Ok screw the heap minHeap for now. Q: Can we have a hashmap only solution? I think so: hashmap{ 0: 1: 2: 3: 4: 5: .. n: } 1) We add 'AAAAAA' to the hashmap. When we process, for that elem, we remove last elem of str. Move that to n. Ok using the time as keys is dumb. **215 Kth Largest Element in an Array** Given int nums array. Return kth largest elem. = minheap. No sorting. heapq.heapify(nums) while len(nums) > k: heapq.heappop(nums) return nums[0] min val is at the top. We keep removing the min vals. kth largest should be @ top. **973 K Cloest Point to Orgin** 26 min Given array of points. (x,y). [[x,y],[]]. Return k closest to orgin. If it is the closest, we want to be popping max, therefore, it should be a max heap. 1) Make a distance var (list floats using formula) 2) Heapify (max heap), keep popping while len(heap) > k 3) return heap[0] distances = [] for x, y in range(points): distances.append((math.sqrt((x**2) + (y**2))) distances = [-distance in distance in distances] heapq.heapify(distance) while len(heapq) > k: heapq.heappop(distance) return -distances[0] You end up returning the distances instead of the cordinates. We are returning the kth closest points, not point. So in this case we return entire heap. **1046 Last Stone Weight** We are smashing the heaviest of two stone. That screams max heap to me. We pop twice. 1st pop() = y, 2nd pop() = x. If x == y do nothing. If x != y, heappush(y-x). While len(stones) > 1. stones = [-stone for stone in stones] heapq.heapify(stones) while len(stones) > 1: y = -heapq.heappop(stones) x = -heapq.heappop(stones) if y > x: heapq.heappush(stones, -(y-x)) return -stones[0] if stones else 0 **703 Kth Largest Element in a Stream** My implementaion from mem: class KthLargest: def __init__(self, k: int, nums: List[int]): self.minHeap = heapq.heapify(nums) self.k = k while len(self.minHeap) > k: heapq.heappop(self.minHeap) def add(self, val: int) -> int: heapq.heappush(self.minHeap, val) if len(self.minHeap) > k: heapq.heappop(self.minHeap) Design a class to find kth largest elem. We have to maintain the Kth largest elem. class Kthlargest: def __init__(self, k, nums): self.minHeap = nums self.k = k heap.heapify(self.minHeap) while len(self.minHeap) > k: heapq.heappop(self.minHeap) def add(self, val): heapq.heappush(self.minHeap, val) if len(self.minHeap) > self.k: heap.heappop(self.minHeap) return self.minHeap[0] In this case, the lib we use it 0 indexed. We maintain a min heap. Only keep the kth largest, because we keep popping the smallest. Note for most heap problems, you would be using heapq. The methods are: 1) hepq.heapify(my_list) 2) heapq.heappush(my_list, elem) 3) smallest = heapq.heappop(my_list) Q: How would you implement a max heap? You just insert and -heapq.pop() def pop(self): if len(self.heap) == 1: return None if len(self.heap) == 2: return self.heap.pop() #I guess that this would return the parent elem? Or in this case self.heap[0] res = self.heap[1] #This is just the first left child node... Nope, heaps normally start off at 1 index. res = self.heap[0] actually starts off at the 1st index i = 1 #Percolate down while 2 * i < len(self.heap): #while left child if (2 * i + 1 < len(self.heap)) and #there is no right child While there is a left child: 1) right child < heap 2) if val of right child < val of left child 3) if cur > right child Here are the cases: 1) no children 2) 1 left child 3) two children. When popping, you want to bubble up the smaller of the left or right child. So we have to check both: def pop(self): if len(self.heap) == 1: return None if len(self.heap) == 2: #this is the first elem return self.heap.pop() i = 1 while 2 * i <= len(self.heap): smaller_child_index = self.getSmallerChildIndex(i) if self.heap[i] > self.heap[smaller_child_index]: self.heap[i], self.heap[smaller_child_index] = self.heap[smaller_child_index], self.heap[i] i = smaller_child_index else: break if current index is smaller than the child, you do the swap: def getSmallerChildIndex(self, i): #This finds the lower index of the left and right bounds left_child_index = 2 * i right_child_index = 2 * i + 1 if right_child_index > len(self.heap): #right child out of bounds return left_child_index else: return left_child_index if self.heap[left_child_index] < self.heap[right_child_index] else right_child_index //May 3 2024 Learn abouts Heap and Queues. Backtracking (Tree Maze). A heap is always a full binary tree. We normally store heaps using arrays. There are generally two types of heaps 1) Min Heap 2) Max Heap. Min heap root = smallest. When deleting root = highest priority. The opp for max heap. lefChild = 2i rightChild = 2i + 1 parent = i/2 Psuedo implementation of heap: class Heap: heap = [] constructor(): heap = [] heap.add(0) There are a few functions for heaps. The first being push: def push(self, val): self.heap.append(val) i = len(self.heap) - 1 while i > 1 and self.help[i] < self.heap[i//2] #while 1) in the heap 2) the cur val larger than the child value while i > 1 and self.heap[i] < self.heap[i//2]: self.heap[i], self.heap[i//2] = self.heap[i//2], self.heap[i] i = i // 2 The push function is O(logn) since it takes time to percolate up. Pop() form a heap is more complicated. You have to swap //May 2 2024 **1905 Count Sub Islands** Futher simplified code: 1) Combine the two grids into one pass 2) Use a direct marking strategy 3) Eliminate un-needed subIsland param def countSubIslands(grid1, grid2): R, C = len(grid1), len(grid1[0]) def dfs(r, c): if 0 < r <= R and 0 < c <= C and grid2[r][c] == 1: grid2[r][c] = 0 is_sub = grid[r][c] == 1 is_sub &= dfs(r + 1, c) is_sub &= dfs(r - 1, c) is_sub &= dfs(r, c + 1) is_sub &= dfs(r, c - 1) return is_sub return True #This is for if it is out of bounds res = 0 for r in range(R): for c in range(C): if grid2[r][c] == 1: if dfs(r,c): res += 1 return res Correction by GPT: def countSubIslands(grid1, grid2): R, C = len(grid1), len(grid[0]) visited1 = set() def dfs1(r, c): if r < 0 or r >= R or c < 0 or c >= C or (r,c) in visited1 or grid[r][c] == 0: return visited1.add((r,c)) dfs1(r + 1, c) dfs1(r - 1, c) dfs1(r, c + 1) dfs1(r, c - 1) for r in range(R): for c in range(C): if grid1[r][c] == 1 and (r, c) not in visited: dfs1(r, c) res = 0 def dfs2(r, c subIsland): if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] == 0: return True grid[r][c] = 0 isSub = subIsland and (r,c) in visited1 isSub = dfs2(r + 1, c, isSub) and isSub isSub = dfs2(r - 1, c, isSub) and isSub isSub = dfs2(r, c + 1, isSub) and isSub isSub = dfs2(r, c - 1, isSub) and isSub return isSub for r in range(R): for c in range(C): if grid2[r][c] == 1: if dfs2(r, c, True): res += 1 return res We can use DFS to track the the coordinates of the islands in grid1. Then we do DFS again on grid 2. But we only += 1 to the results if we find all the 1s for an island and all of them belong in the visted coordinates of grid1. def countSubIslands(grid1, grid2): grid1islands = set() R, C = len(grid1), len(grid1)[0] def dfs1(r,c): cur_cell = (r, c) if r < 0 or r >= R or c < 0 or c >= C or cur_cell in grid1islands: return None grid1islands.add((r,c)) dfs1(r+1, c) dfs1(r-1, c) dfs1(r, c+1) dfs1(r, c-1) for r in range(R): for c in range(C): if grid1[r][c] == 1: dfs(r,c) res = 0 def dfs2(r,c, subIsland): cur_cell = (r, c) if r < 0 or r >= R or c < 0 or c >= C or grid2[r][c] == '0': return 0 grid2[r][c] = '0' #mark as visited if cur_cell not in grid1islands: subIsland = False dfs2(r+1, c) dfs2(r-1, c) dfs2(r, c+1) dfs2(r, c-1) return 1 if subIsland for r in range(R): for c in range(C): if grid[r][c] == '1': res += dfs2(r,c, True) return res **953 Verifying an Alien Dictionary** ??? How did the break statement fix things?? w1[j] != w2[j] case, if the ordering is wrong return false. Else if the the char of w1 < char of w2, we stop the loop. Better solution: Outer forloop remains the same: w1, w2 = words[i], words[i+1] for j in range(min(len(w1),len(w2)): if w1[j] != w2[j] #This avoids un-needed lookups on the hash table if orderHash[w1[j]] > orderHash[w2[j]]: return False else: if len(w1) > len(w2): return False How is this a graph problem? A: it is not. 1) Create a hash table of the ordering. This way when iterating through a letter you can check if the ordering match at O(1) time. Then you compare adj words and letters. class Solution: def isAlienSorted(self, words: List[str], order: str) -> bool: orderHash = {} for i, val in enumerate(order): orderHash[val] = i for i in range(len(words) - 1): w1, w2 = words[i], words[i+1] shortestWord = min(len(w1), len(w2)) for j in range(shortestWord): if orderHash[w1[j]] > orderHash[w2[j]]: return False if len(w1) > len(w2) and w1[:shortestWord] == w2[:shortestWord]: return False return True "he" "help" ^ ^ Other fail condition is if the char are the same but one is longer. If 1) the shorter one run out 2) orderHash[w1[j]] > orderHash[w2[j]] is not triggered. The ticky part here is 1) how do we track which word is shorter? We have to ensure that w1 is shorter. **133 Clone Graph** def cloneGraph(node): oldToNew = {} def dfs(node): if node in oldToNew: return oldToNew[node] copy = Node(node.val) oldToNew[node] = copy for nei in node.neighbors: copy.neighbors.append(dfs(nei)) return copy return dfs(node) if node else None Prompt. Here is my answers. Give feedback. Be as nuancsed and specific as possible 1) We need to check if a node already exisits in 'oldToNew' because we dont want to do reduent work (make addional recursive calls) if the node is already in the dict. We simply have to return the value of the cloned node to connect it to the graph with the other copy neighbors in the call copy.neighbors.append(dfs(nei)). This also prevents cycles by acting similar to the vistied set(). 2) We we don't use the oldToNew dict and crate a new node every time we encounter a new node like so: new_node = node(node.val), we won't be able to reference the neighbor nodes and connect them? At this step specifcally: for nei in node.neighbors, if we didn't do oldToNew[node] = copy, how do we know which node to connect its old neighbors with (the old neighbors happen to be a deep copy since of the recursive call)? Feedback: Without this mapping, each recursive call will create mutiple clones of the same node. This is because we're essentially losing out on the visited = set() feature that checking if node in oldToNew also provides right? Else you end up with mutiple clones of the same node if you end up re-visiting something (will happend if you have mutiple edges connected to it) Generally with a node, it will be re-visted porportional to the number of edges is connected to it right? Is there a mathatical relationship/formula between it? Yes. That is called the degree of a graph. For undirected graphs, it visited d times where d = degree = # of edges connected to it. For directed graphs. So for both visted = d(v) where v = number of direct connected edges. 3) The process of linking nodes happens @ copy.neighbors.append(dfs(nei)), this recursivly calls on the function and there are 2 scenarios 1) node exisits in oldToNew dict we return oldToNew[node] with the value Node(node.val) defined in the prev recursive call (oldToNew[node] = copy). 2) It does not exist, then we set copy new node val and run through the for nei in node.neighbors loop. This way during the recursive call node must in oldToNew (since oldToNew[node] = copy in previous call). 4) This solution aviods infinite cyle by maintaining a version of visited by checking if the node (key) exists already in the oldToNew map. 5) If there are two different paths leading to it from the root, whichever is closer to the root triggers: copy = Node(node.val) oldToNew[node] = copy So when the other path leads it it, it'll hit: if node in oldToNew: return oldToNew[node] Returning the pointer to the clone. 6) Already mentioned. The first return returns the pointer to the deep copy of the node in the old to new dict to reconnect the nodes. The return copy happens once at the end of the unwinding and returns the copy of the first node. 10) Time and space are both O(n) The oldToNew dictonary maps each original node to the corresponding clone. key = orgional node, values = new nodes. class Solution: def cloneGraph(self, node: "Node") -> "Node": oldToNew = {} def dfs(node): if node in oldToNew: return oldToNew[node] copy = Node(node.val) oldToNew[node] = copy for nei in node.neighbors: copy.neighbors.append(dfs(nei)) return copy return dfs(node) if node else None -- oldToNew = {} def dfs(node): if node in oldToNew: #This is is the same as if in visited return oldToNew[node] #Q: Why do you have a return value of oldToNew[node] if in visited? A: You need to return the value to actually connect the other nodes with it even if visted to create a deep copy of the graph. copy = Node(node.val) # this is the copy of the node oldToNew[node] = copy for nei in node.neighbors: copy.neightbors.append(dfs(nei)) return copy return dfs(node) if node else None //May 1 2024 **133 Clone Graph** This is a pretty standard DFS problem. The novel thing about this problem is that we have to create a deep copy of the graph via clone. And the method you use to access it isn't adj_list[cur] but rather node.neightbors. We created a dict to track the cloned nodes. def cloneGraph(node): if not node: return None cloned_nodes = {} visted = set() def dfs(node): if node in visited: return visted.add(node) if node not in cloned_nodes: cloned_nodes[node] = Node(node.val) clone = cloned_nodes[old_node] **105 Construct Binary Tree from Preorder and Inorder Traversal** Given this tree: 3 / \ 9 20 / \ 15 7 Preorder: [3,9,20,15,7] Inorder: [9,3,15,20,7] The trick is to notice that preorder always has root as first elem (does not matter if left or right root). We then use that to find the root val in post order which cleanly divides the tree into left and right subtrees. def buildTree(preorder, inorder): root = TreeNode(preorder[0]) midpoint_index = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1:mid+1], inorder[:mid]) root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:]) return root **106 Construct Binary Tree from Inorder and Postorder Traversal** Given in order and post order arrays, construct a binary tree. You cannot do the (start + end) // 2 = mid since you don't know where mid starts. def buildTree(inorder, postorder) -> TreeNode: if not inorder not or postorder: return None def createTree(): ... root.left = createTree() root = TreeNode(somearray[index]) root.right = createTree() #You also have to track the index values. Key insight: root_val = postorder[post_end] **108. Convert Sorted Array to Binary Search Tree** class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: if not nums: return None def createTree(start: int, end: int) -> TreeNode: if start > end: return None mid = (start + end) // 2 root = TreeNode(nums[mid]) root.left = createTree(start, mid - 1) root.right = createTree(mid + 1, end) return root return createTree(0, len(nums) - 1) **99 Recover Binary Search Tree** The big brain move is to solve it using Morris Traversal. Spend some time in the next few days to better understand the algo []todo. if prev and node.val < prev.val: if not first: first = prev second = node prev = node Given the tree: 3 / \ 1 4 / 2 With the code snippet: if prev and node.val < prev.val: if not first: first = prev second = node prev = node If you think about the def of a inOrder traversal, the cur node val should always be bigger than the prev val. If this is happening for the first time, the first val = prev val. prev = node I get. Why set second as node? Proper method: 1) find the two swapped nodes using first, second, prev = None def recoverTrees(root): first = second = prev = None def inOrder(node): nonlocal = first, second Alternative solution using NonLocal: # 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 recoverTree(self, root: Optional[TreeNode]) -> None: elements = [] def inOrder(node): if not node: return inOrder(node.left) elements.append(node) inOrder(node.right) inOrder(root) sorted_values = sorted(node.val for node in elements) index = 0 def refillTree(node): nonlocal index if not node: return None refillTree(node.left) node.val = sorted_values[index] index += 1 refillTree(node.right) refillTree(root) def recoverTree(self, root): elements = [] def inOrder(node): it not node: return inOrder(node.left) res.append(node) inOrder(node.right) inOrder(root) sorted_values = sorted(node.val for node in elements) def refillTree(node, index): if not node: return index index = refillTree(node.left, index) node.val = sorted_values[index] index += 1 index = refillTree(node.right, index) return index refillTree(root, 0) GPT said that elements.append(node). Why not append node.val and then traverse through node.val? Just bad practice. Unless you have a super good reason, you generally want to keep the refrence to the nodes. Then you simply sort buy node vals: sorted_values = sorted(node.val for node in elements) The problem with this approach is that the i in the recursive case does not correctly maintain the index. sorted_values = sorted(node.val for node in elements) What if we do inorder traversal. Sort the arr, and manually fill in the vals with another DFS? def recoverTree(self, root) -> None: res = [] def inOrder(node): if not node: return None inOrder(node.left) res.append(node.val) inOrder(node.right) inOrder(root) res = sorted(res) def fillTree(node, i): if not node: return None fillTree(node.left, i+1) node.val = res[i] fillTree(node.right, i+1) fillTree(root, 0) return root **2385 Amount of Time for Binary Tree to Be Infected** Given root with unique vals (so our adj list could be vals). Infection starts from node with val start. Return total min for entire tree to be infected. 1) Turn tree into undirected graph 2) BFS to spread infection, return total_min def amountOfTime(self, root, start) -> int: adj_list = defaultdict(list) def dfs(node, parent): if not node: return if parent is not None: adj_list[node.val].append(parent.val) adj_list[parent.val].append(node.val) dfs(node.left, node) dfs(node.right, node) dfs(root, None) queue = deque([start]) visited = set([start]) infection_time = 0 while queue: level_size = len(queue) for _ in range(level_size): cur = queue.popleft() for neighbor in adj_list[cur]: if neighbor not in visited: queue.append(neighbor) visited.add(neighbor) infection_time += 1 return infection_time - 1 **863 All Nodes Distance K in Binary Tree** def distance(root, target, k) -> list: adj_list = defaultdict(list) def dfs(node, parent): if not node: return if parent is not None: adj_list[node].append[parent] adj_list[parent].append[node] if node.left: dfs(node.left, node) if node.right: dfs(node.right, node) dfs(root, None) res = [] distance = 0 visited = set([root]) queue = deque([root]) while queue: queue_size = len(queue) for _ in range(queue_size): cur = queue.popleft() if distance == k: res.append(cur.val) for neighbor in adj_list[cur]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) distance += 1 if distance > k: break return res The problem here is that you don't distingish how the levels are process. You need a for loop. res = [] level = 0 visited = set() queue = deque([root]) while queue: cur = queue.popleft() visited.add(cur) for neighbor in adj_list[cur]: if neighbor not in visted: queue.append(cur) if level = k: res.append(cur.val) level += 1 return res **2000 Reverse Prefix of Word** Reverse word that starts @first occurance of char. for i, char in enumerate(word): if char == ch: return word[:i + 1][::-1] + word[i + 1:] return word //Apr 30 2024 **863 All Nodes Distance k in Binary Tree** Now we got that out of the way, we are given a target node, so we add that to out queue for our BFS. Ok. Since you cannot go up in a binary tree, turn this tree into a graph problem (adj list), and store all the nodes k distance away from target. def distance(self, root, target, k): Ok, the first sub problem to this is given the root of a binary tree, convert it to and adj list: adj_list = defaultdict(list) def dfs(node, parent): if not node: return if parent is not None: ajd_list[node.val].append(parent.val) adj_list[parent.val].append(node.val) if node.left: dfs(node.left, node) if node.right: dfs(node.right, node) dfs(root, None) Wait this breaks if there are different nodes on the tree that share the same value. So we have to link by the acutal node values. adj_list = defaultdict(list) def dfs(node, parent): if not node: return None if parent is not None: adj_list[node].append(parent) adj_list[parent].append(node) if node.left: dfs(node.left, node) if node.right: dfs(node.right, node) dfs(root, None) **2415 Reverse Odd Levels of Binary Tree** If you think about it, this question is pretty much zig zag traversal, however, the trcky part is that we have root vals def reverseOddLevels(root): queue = deque([root]) level = 0 while queue: level_size = len(queue) level_val = [] for _ in range(level_size): #dont have to do if node.left and node.right since its a perfect tree cur = queue.popleft() level_val.append(cur.val) queue.append(cur.left) queue.append(cur.right) if level % 2 == 1: {algo} level += 1 return root {algo}: for i in range(len(cur_level)//2: current_level[i].val, current_level[-1-i].val = current_level[-1-i].val, current_level[i].val Ok: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2] Output [0,2,1,0,0,0,0,1,1,1,1,2,2,2,2] Expected [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1] You can't really get it to work just doing recursion and DFS. Lets give up on this and do BFS. The reason is that you have to do the reverse not just at the level below the parent, but the entire level. The problem with this is we end up swapping all the children nodes as well. So we gonna jank this and just swap the vals We should be able to solve this using standard dfs and counting if the depth % 2 == 0. If yes, reverse else, continue. def reverseOddLevels(self, root): def reverse(node, level) -> treeNode: if not node: return None if level % 2 == 0: #if even, you swap the children (odd nodes) node.left, node.right = node.right, node.left level += 1 reverse(node.left. level) reverse(node.right, level) return root return reverse(root, 1) //Apr 29 2024 **567 Permutation in String** def checkInclusion(s1, s2)-> bool: if len(s1) > len(s2): return False s1_hashmap = {} for char in s1: if char in s1_hashmap: s1_hashmap[char] += 1 else: s1_hashmap[char] = 1 L = 0 s2_hashmap = {} for R in range(len(s2)): char = s2[R] if char in s1_hashmap: if char in s2_hashmap: s2_hashmap[char] += 1 else: s2_hashmap[char] = 1 if R - L + 1 > len(s1): if s2_hashmap[s2[L]] == 1: del s2_hashmap[s2[L]] else: s2_hashmap[s2[L]] -= 1 L += 1 if s2_hashmap == s1_hashmap: return True return False Ok notice how s1 seems to always be the shorter string. Ok you cant even use permutations since is s1 could be up to 1000 char long and the run time is O(n!*n). Ok so to solve this we need 1) sliding window 2) probably a hashmap. Loop through s2. store all the char and count in st2 hash. Iterate through s1. Subtract the vals from str2 hash with s1. This would not work since the vals would have to be grouped together. So we could take the len of s1 first and have a sliding window len(s1). For the window, keep a count of the chars: a = 2 b = 3 c = 1 etc. When you move the window, you remove the left most elem from the hash and add the right most val to the hash. While at the same time you do a comparison if you can match every s1 char into the ditc of s2. class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: window_size = R = len(s1) L = 0 s2_hashmap = {} for R in range(len(s2)): #of s1 can fit in s2_subset, return true for char in s1: if char1 not in s2_hashmap: continue return True if R - L + 1 > window_size: if s2_hashmap[s2[L]] == 1: s2_hashmap.remove(s2[L]) else: s2_hashmap[s2[L]] -= 1 L += 1 if s2[R] in s2_hashmap: s2_hashmap[s2[R]] += 1 else: s2_hashmaps2[R] = 0 return False You gotta now edit the code so it actually works now. Time for review: combinations, subsets, permutations. Combinations: Selects a group of items from a collection where ordering does not matter. So for backtracking 123 == 321 thus 321 isnt added. def combinations(nums, k): result = [] def backtrack(start, path): if len(path) == k: res.append(path) for i in range(start, len(nums)): backtrack(i + 1, path + nums[i]) backtrack[0, []] return res Wait, why do you not need to pop for this question. We actually do handle that case. The recursive call creates a new list with path + [nums[i]]. def combinations(nums, k): res = [] def backtrack(start, path): if len(path) == k: res.append(path) return for i in range(start, n + 1): backtrack(i + 1, path + [i]) backtrack(1, []) return res The more efficent method where we do not send a copy of path (which is saved on the recursive stack), but rather modifying directly to save mem. def combine(n, k): res = [] def backtrack(start, path) if len(path) == k: res.append(path[:]) return for i in range(start, n + 1): backtrack(i + 1, path.append(i)) path.pop() backtrack(1, []) return res Q: what does path[:] do? Im assuming that it points to the mem location of the orgional path func. A: This is a shallow copy of the list object. Think of it as copying the addresses where the items are being store rather than the item itself. Shallow copy vs deep copy and usecases. subset = special set of combination where its the combination of all len sets. def subsets(nums): res = [] def backtrack(start, path): res.append(path) for i in range(start, n): path.append(i) backtrack(i + 1, path) path.pop() backtrack(0, []) return res With permutations, ordering matters: def permutations(nums): res = [] def backtrack(path): if len(path) = len(nums): res.append(path[:]) return for num in nums: if num not in path: path.append(num) backtrack(path) path.pop() backtrack([]) return res In permutations, we do num in nums because we don't have to traverse through subarrays - we are only concered with the odering of elems. **Reverse Linked List II** Correct code: def reverseBetween(head, left, right): left_head = head for _ in range(left): left_head = left_head.next right_head = left_head prev = None for _ in range(left, right) prev, right_head.next, right_head = right_head.next, prev, right_head.next left_head.next = prev right_head.next = right_head return head if left > 1 else prev #return head of the OG linked list def reverseBetween(head, left, right): left_head = head for _ in range(left): left_head = left_head.next right_head = left_head prev = None for _ in range(left, right) prev, right_head.next, right_head = right_head.next, prev, right_head.next 1-2-3-4-5 L R **Unique Binary Search Trees II** def generateTrees(n) -> list: if n == 0: return [] def generate_trees(start, end): if start > end: return [None] res = [] for root_val in range(start, end + 1): left_subtrees = generate_trees(start, root_val - 1) right_subtree = generate_trees(root_val + 1, end) for left_tree in left_subtrees: for right_tree in right_subtrees: root = newNode(root_val) root.left = left_tree root.right = right_tree res.append(root) return result return generate_trees(1, n) This is the exact same problem as the previous one we solved with Catalan's numbers, but this time, we actually have to build a tree. If n == 1 or n == 0, return None to recurse back. def generateTrees(n) -> list: res = [] def combinations(n, root): for root in range(1, n + 1): Lets break the problem down together. First and foremost, the min runtime is the amount of trees you can build. Another observation is that for the root node, the numbers 1 - n should take turns being the root. When building the tree, we must also follow the rules of a binary tree. left < parent < right. Lets first think about the basecase. Since we're building a tree, if n == 1, we return the cur node, and if n == 0 we return 0 as a signal to unwind the stack. For root selection, we could have for root in range(1, n + 1) outside of the recursive calls to make sure that every n val gets a chance of being the root. Building Construction. When we have the node n. So we have to have some sort of method to remeber to not re-use nodes. I'm almost thinking of for every permuation of the tree, we keep a set(), and only draw upon the vals that are still in the set (not used). But this way, we are try out every possible combination of a potential tree, rejecting most of the attempts. This does not seem very run time efficent. The logic to check if valid tree should be something along the lines of: if new_val < parent: parent.left = newNode(new_val) else: parent.rigth = newNode(new_val) - The insight is that when building the subtree, everything smaller than root goes to the left subtree while everything bigger goes to the right. We can acheive this recursivly by doing: left_sub_tree = generate_trees(1, root - 1) right_sub_tree = generate_trees(root + 1, n) This way we start from the root, and build outwards? When building the tree, we should probably return the pointer to the tree nodes, but at the end, we should have a function that appends all the possible trees into a array to append onto a final res array in which we return. How do we generate all possible left and right subtrees? The given loop is: for left_tree in left_subtrees: for right_tree in right_subtrees: where left_subtrees is just a range from start to root_val - 1. So in this case left_tree and right_tree just take the vals of int from (start to root_val - 1) and (root_val + 1, end). So you're saying pretty much, for this recursive call, we'll take an number root from 1-n. And we split that up into a left and right subtree as defined by (start, root_val - 1) and (root_val + 1, end). For the left and right subtree, we are able to create every possible subtree by the two nested for loops. //Apr 28 2024 --Bonus-- Catalan numbers sequence of natural numbers. Where C0 == 1 is the base case. With DP, there is top down (memo) and bottom up (real DP). Bottom up is called tabulation btw. For memo, recursive func that checks the res input is already computed. For tab, initalize arr with base case and iterativly fill the vals based on the recursive formula. def catalan = [0] * (n + 1) catalan[0] = 1 **Unique Binary Search Trees** class Solution: def numTrees(self, n: int) -> int: def calculate(n, memo): if n in memo: return memo[n] if n == 0 or n == 1: return 1 total_trees = 0 for root in range(1, n + 1): left_trees = calculate(root - 1, memo) right_trees = calculate(n - root, memo) total_trees += left_trees * right_trees memo[n] = total_trees return total_trees return calculate(n, {}) def of a BST, left < parent < right. Does not have to be a complete tree. Return type of int. Give a int n. Where the nodes you have to work with is 1 -> n. Brute force every combination and see if its a tree? DFS. Build tree? This isn't your average tree traversal problem... **662 Maximum Width of Binary Tree** Correct code: def widthOfBinaryTree(root) -> int: width = 0 queue = deque([(root, 0)]) while queue: level_size = len(queue) _, start_index = queue[0] end_index = 0 for _ in range(level_size): cur, cur_index = queue.popleft() end_index = cur_index if cur.left: queue.append((cur.left, 2 * cur_index + 1)) if cur.right: queue.append((cur.right, 2 * cur_index + 2)) width = max(width, end_index - start_index + 1) return width 1) end_index = cur_index gives you pretty much the last index elem of the row - the first index 2) if cur.left: queue.append((cur.left, 2 * cur_index + 1)) Ok. I have to pretty much prove to myself that 2 * cur_index + 1 is always the val of the left node. But what if on a tree the level goes like 1, None, None, None, None, 4? 1 <-- Index: 0 / None <-- Index: 1 (2 * 0 + 1) / \ \ \ None None None 4 <-- Indices: 3, 5, 7, 15 Oh ma god. This uses the val of the parent index to calculate the val of the cur index. def widthOfBinaryTree(root) -> int: if not root: return 0 width = 0 queue = deque([root, 0]) while queue: level_size = len(queue) L = float('inf') R = -float('inf) for i in range(level_size): cur, index = queue.popleft() if cur: L = min(index, L) R = max(index, R) if cur.left: queue.append((cur.left, index)) if cur.right: queue.append((cur.right, index)) width = max(width, R - L + 1) return width 1 12 1234 - ex cur index == 4 12345678 the cur index then is 9? So the calculation of the index assuming that its is a full tree = if cur.left: 2 * cur_index + 1 Nah this is too big brained. I smol brain rn. Gemini Review: 1) For the index of every level, min is technically 0 and if its a full tree, R doubles. 2) We would want to skip L and R for the first level. 3) Well in my code I kept a global width and for each level did width = max(width, R - L). This is BST but at each level, you count None as a elem and add that. Then you count the total max index diff of non None elems @ each level. When you are appending to the path (if cur.left or if cur.right) you have to have some form of method to also add the None elems. One sub problem that you have to figure out is how do you add the children of the None vals. def widthOfBinaryTree(root) -> int: if not root: return 0 width = 0 queue = deque([(root, 0)]) while queue: level_size = len(queue) for i in range(level_size): cur = queue.popleft() if cur.left: queue.append((cur.left, i)) elif cur.right: queue.append((cur.right, i)) else: queue.append((None, i)) L = float('inf) R = -float('inf) for val, index of queue: if val != None: L = min(index, L) R = max(index, R) width = max(width, R - L) return width Now we have a tuple of the index and the vals, at the end of each level, we keep a running tally of the R most and L most of elem that is not None. **958 Check Completeness of a Binary Tree** Ok so the correct way to do it is have a flag called is_empty, and if empty and there is a left and right child in the following nodes, we know to return False. That is all there is to this problem. def isCompleteTree(self, root) -> bool: if not root: return True queue = deque() queue.add(root) empty = False while queue: level_size = len(queue) for _ in range(level_size): cur = queue.popleft() if empty and (cur.left and cur.right): return False if cur.left: queue.append(cur.left) else: empty = True if cur.right: queue.append(cur.right) else: empty = True return True DFS seems like an non ideal algo. Lets try BFS? def isCompleteTree(self, root) -> bool: queue = deque() queue.add(root) while queue: level_size = len(queue) for i in range(level_size): cur = queue.popleft() (if cur.right and not cur.left) \ or not cur.right and i != level_size: #If there is a right child without a left return False if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) return True Code breaks at this test case: [1,2,3,5,null,7,8] We also have to make sure that there is always a right child unless i == level_size. Nope that is a epic fail. The rule here is that it cannot have more neighbors if there is no right child. For that level, if there are any more items to loop over and we missing a right child, return False. You simply have to check if there are full leafs. But upon re-reding the question, that is not the def of a complete binary tree. You use recursion. Return val is bool. Question: is there any other axuillary DS we have to pass in as a param? No. One idea is to have a counter that cannot > 1 for number of empty children, but that will not work, we can fail @ case in example 2. def isCompleteTree(root) -> bool: if not root: return True #Question how do we know if its not at the right most leaf return self.isCompleteTree(root.left) and self.isCompleteTree(root.right) #Since we have to compare both left and right subtrees //Apr 27 2024 **124 Binary Tree Maximum Path Sum** Code according to Gemini: def maxPathSum(self, root) -> int: res = -float('inf') def dfs(node) nonlocal res if not node: return 0 left_max = max(0, dfs(node.left)) right_max = max(0, dfs(node.right)) cur_max = node.val + max(left_max, right_max) res = max(res, cur_max) return cur_max dfs(root) return res Ok, so the really smart thing to do is that the left_max and right_max does not exactly calculate the 'max' val possible, but rather think of this as a substep to see if you would want to append this to the arry. If its a -, you dont add it therefore its (0). Do nothing. Which is the same as not adding that path? cur_max, looks at the max possible val in the cur subtree. You add the most recent node to the max val of the left and right subsum (check which subtree to keep). At the end, you do the global max to compare the left and right subtree at each unwinding to get the global max. Since you're looking at pairs of adjecent nodes, you can do visit left subtree, visit right subtree, visit root. And take all possible paths and track the min val of it. Ok, Gemini helped me a bit in that its not just adjacent nodes. A path can zigzag through the tree as long as there is a parent child relationship. Right, would this require backtracking? Say we make an array of all the possible values, and for each, we apply the min func to the subpath Ok lets break the question down into the base case: 1) What do we return? int. if not node, return 0. 2) The left path should only return its left subchildren while the right path only the right subchildren. We keep a tally of maxsum as a global var. 3) The help from each children should be the left or right sub_sums? def maxPathSum(self, root) -> int: def dfs(node, cur_sum) -> int: if not node: return 0 cur_sum = 0 left_sum = The tricky part for me is the fact that I only know how to calculate (or ever had to calculate) the total sum of a left or right subtree. I never had to skip the val in between the values left and right adj nodes to create "a path". So the trick is, for the children, instead of returning the sum of the subtree, you return max_path sum from that child. def maxPathSum(self, root) -> int: def traverse(root) **230 Kth Smallest Element in BST** Ok. lets try the trivial solution to this first. In order traverse, and then return -kth from end. Done. --Review-- Sub Tree of another tree: def isSubtree(treeNode, subTreeNode)-> bool: if not treeNode: return False if not subTreeNode: return True if isSameTree(treeNode, subTreeNode): return True return self.isSubtree(treeNode.left, subTreeNode) or self.isSubtree(treeNode.right, subTreeNode) def isSameTree(p, q)-> bool: if not p and not q: return True if not p or not q or p.val != q.val return False return isSameTree(p.left, q.left) and isSameTree(p.right, q.right) Validate BST: def validateBST(root): lower, upper = -float('inf'), float('inf') def dfs(node, lower, upper) -> bool: if not node: return True if not (lower < node.val < upper): return False return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper) return dfs(root, lower, upper) **501. Find Mode in Binary Search Tree** class Solution: def findMode(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] elem_map = defaultdict(int) def traverse(node): if not node: return traverse(node.left) elem_map[node.val] += 1 traverse(node.right) traverse(root) res = [] max_freq = 0 for key, val in elem_map.items(): max_freq = max(val, max_freq) for key in elem_map: if elem_map[key] == max_freq: res.append(key) return res **98 Validate Binary Search Tree** A jank solution is in order traversal and check if always increasing. res = [] def inOrder(node) inOrder(node.left) res.append(node.val) inOrder(node.right) return res == sorted(res) def dfs(node, min_val, max_val): if not node: return True if not (min_val < node.val < max_val): return False return dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val) return dfs(root, -float('inf), float('inf')) Lets try to trace till 4: 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 node min_val max_val 8 -∞ ∞ 3 -∞ 8 6 3 8 4 3 6 min_val = val of left most common ancestor to cur node max_val = val of right most common ancestor to cur node First attempt = epic fail Given root, determine if its a valid BST. The tricky part is that you're only returning True false with this BST. def isValidBST(self, root) -> bool: if not root: return True if root.left or root.right: if root.left: if root.left.val < root.val: return True else: return False if root.right: if root.right.val > root.val: return True else: return False return self.isValidBST(root.left) and self.isValidBST(root.right) **1448 Count Good Nodes in Binary Tree** Glanced @ how GPT did it. def goodNodes(self, root) -> int: dfs(node, max_val): if not root: return 0 count = 1 if node.val >= max_val else 0 max_val = max(node.val, max_val) left_count = dfs(node.left, max_val) right_count = def(node.right, max_val) return count + left_count + right_count return dfs(root, -float('inf') Damn, your last implementaion was dumb af. This is easy DFS and check if the children are larger. If yes return += 1, else 0? def goodNodes(self, root)-> int: if not node: return 0 left = self.goodNodes(root.left) right = self.goodNodes(root.right) if left.val > node.val: return 1 if right.val > node.val: return 1 return 0 return left + right **652 Find Duplicate Subtrees** Gave on on this because I needed a win earlier in the day. Asked ChatGPT. subtree_map = defaultdict(int) duplicates = [] def serialize(node): if not node: return "#" serial = str(node.val) + ',' + serialize(node.left) + ',' + serialize(node.right) subtree_map[serial] += 1 if subtree_map[serial] == 2: duplicates.append(node) return serial serialize(root) return duplicates Q: Do we need to even serialize/flatten the tree in the first place? It does not seem trivial to me how we can determine which nodes are subtree based based on the technique used yesterday. Another method is to build a tree with () brackets defining the children, and then using a hashmap to track what same subtrees has been already added. (1)(()(0)) (1) //Apr 26 2024 **652 Find Duplicate Subtrees** Ok. I kinda mentally checked out here. But according to chat GPT, 1) serialize each subtree 2) count subtree occurrences 3) collect dups. To solve this problem you should do 1) same tree 2) is subtree. Done and done. Note, that another method to check if subtree is to serialize(node) def serialize(node): if not node: return return str(node.val) + ',' + serialize(node.left) + serialize(node.right) tree_serial = serialize(root) subtree_serial = serialize(subRoot) return subtree_serial in tree_serial **103 Binary Tree Zigzag Level Order Traversal** This is just level order traversal, but at the end of each queue, you reverse the order you append. You can do the ordering based on even odd. if n % 2 == 0, you go from right to left. def zigzagLevelOrder(self, root) -> int: res = [] queue = deque([root]) while queue: level_size = len(queue) level = [] for i in range(level_size): cur = queue.popleft() if root.left: queue.append(root.left) if root.right: queue.append(root.right) if level_size % 2 == 0: reverse = -1 else: reverse = 1 res.append(level[::reverse]) return res **2492 Minimum Score of a Path Between Two Cities** Misread the question: Massive L Help from GPT. To store the min val, we simply add another var (you dummy) Ok, lets break this base case down. If src in visited, return 0. You should return the min distance between the prev path that worked and the cur path that worked. Q: how do you do the min statement. class Solution: def minScore(self, n: int, roads: List[List[int]]) -> int: adj_list = defaultdict(list) for u, v, distance in roads: adj_list[u].append((v, distance)) adj_list[v].append((u, distance)) def dfs(src, dst, visted): if src in visted: return 0 path_sum = 0 visited.add(src) for neighbor, distance in adj_list[src]: if neighbor not in visted: sub_sum = dfs(neighbor, dst, visted) if neighbor == dst: path_sum += sub_sum + distance return path_sum dfs(0, n, set()) --Good to know-- There are a bunch of diff graphs out there. If you're just given edges and nodes, here is how you convert each of them into an adj_list. Directed Graph: adj_list = defaultdict(list) for u, v in edges: adj_list[u].append(v) Undirected Graph: adj_list = defaultdict(list) for u, v in edges: adj_list[u].append(v) adj_list[v].append(u) Weighted Graph: adj_list = defaultdict(list) for u, v in edges: adj_list[u].append((v, weight)) adj_list[v].append((u, weight)) **1443. Minimum Time to Collect All Apples in a Tree** def minTime(n, edges, hasApple): -> int: adj_list = defaultdic(list) for u,v in edges: adj_list[u].append(v) adj_list[v].append(u) def dfs(node, visited): if node in visited: return 0 vistied.add(node) total_cost = 0 for neighbor in adj_list[node]: if neighbor not in visted: sub_tree_cost = dfs(neighbor, visited) if cost_from_subtree > 0 or hasApple[neighbor]: total_cost += sub_tree_cost + 2 return total_cost return dfs(0, set()) if total_cost > 0 else 0 Recall, generally when given edges, and n nodes, you want to turn it into an adj list for easy manipulation. adj_list = {} for u, v in edges: adj_list[u].append(v) adj_list[v].append(u) The question I have top of mind is if the creation of the list changes based on what kind of graph it is. Recall that u stands for vertices (nodes) and v stands for ending vertex. So another way to look at it is start and finish (which combine to make an edge). Lets try to apply DFS to our problem: def dfs(node) if node in visited: return 0 visited = set() visited.add(node) for neighbor in adj_list[node]: if neighbor not in visited: dfs(neighbor) dfs(0) 1. Ok for visted handling, we should have visited outside of the dfs func so the results persist. 2. When visiting a node to check if it has an apple we could do hasApple[node]. So if that path has apples then we should be going in that dir. Therefore, we count the depth it takes to go there. 3. When we recurse into each neighbor in the DFS if there is apple in that path and its not in visited, we should traverse towards the apple and += 2 for each layer we go down. 4. Base case 1) if in visited, return 0. This happens when we already went to the node before. We don't want to do that (or ever have to due to the tree like structure) so we return 0. If no more neighbors or all the neighbors visited, return 0 too? In terms of the nodes with apples we should return the cumlative sum of steps to conver all the paths with apples. And in terms of nodes without apples, we don't want to go there unless there is a apple lower down in the path. def dfs(node, visited): if not node in vistied: return 0 visited.add(node) total_cost = 0 for neighbor in adj_list[node]: if neighbor not in visted: cost_from_subtree = dfs(neighbor, visited) if cost_from_subtree > 0: #pretty much if the subtree has apples total_cost += cost_from_subtree + 2 if hasApple[node]: return total_cost + 2 return total_cost We do if cost_from_subtree > 0: to check if it has apples right? And if it does we know we have to go down that path requiring at least + 2 to go there. I think another key thing for me to wrap my mirror smooth brain around is the fact that when you initalize the total_cost to 0, you += 2 unpon every recursive call unwind, so you set it as 0 once, and you add a call stack worth of 2s. Its not like you're resetting the value to 0 each time you unwind the stack. //Apr 25 2024 **1443. Minimum Time to Collect All Apples in a Tree** This algo is generalizable to a subset of graph traversal algos. This is closer to a BFS graph min len problem than a binary tree problem. Since there are mutiple apples to collect, we actually should probably use DFS. 1) we prob want to convert the n and edges into and adj list? Yes. def build_list(edges): adj_list = {} for u, v in edges: adj_list[u].append(v) adj_list[v].append(u) return adj_list def minTime(self, n, edges, hasApple) -> int: adj_list = build_list(edges) visited = set() def dfs(node): visited.add(node) total_cost = 0 has_apple_in_subtree = hasApple[node] for neighbor in adj_list[node]: if neighbor not in visted: cost_of_subtree = dfs(neighbor) if cost_of_subtree > 0: total_cost += cost_of_subtree + 2 return total_cost if has_apple_in_subtree or total_cost > 0 else 0 dfs(0) **101 Symmetric Tree** Chat GPT response: def isSymmetric(self, root) -> bool: if not root: return True def dfs(p,q): if not p and not q: return True if not p or not q or p.val != q.val: return False return dfs(p.left, q.right) and dfs(p.right, q.left) return dfs(root.left, root.right) Given the root of a binary tree, check if it is a mirror of itself. root.left.val == root.right.val. Return false. There must be a way to check left and right at the same time. def isSymmetric(self, root) -> bool: if not root: return True if node.val return self.isSymmetric(root.left) and self.isSymmetric(root.right) Ok, lets try to split the tree up into two parts: def isSymmetric(self, root) -> bool: if not root: return True def dfs(p,q): if not p and not q: return True if p or q: return False if p.val != q.val: return False return dfs(p.left, q.right) and dfs(p.right, q.lefts) return dsf(root.left, root.right) **783 Minimum Distance Between BST Nodes** Technically it is O(H) with h being the height of the tree. def minDiffinBST(self, root): -> int: self.min_diff = float('inf') self.prev = None def in_order_traverse(node): if not node: return in_order_traverse(node.left) if self.prev is not None: self.min_diff = min(self.min_diff, node.val - prev.val) prev.val = node.val in_order_traverse(node.right) in_order_traverse(root) return self.min_diff Given root of BST return the min diff between the vals of any two diff nodes. First brute force solution that is O(n) space and O(n) time is to traverse through the tree. Store all the vals in arr. L, R, Right = Lowest to higest since its a BST def minDiffInBST(self, root) -> int: nodes = [] def dfs(node): if not node: return dfs(node.left) nodes.append(node.val) dfs(node.right) dfs(root) min_diff = float('inf') for i in range(1, len(nodes)): min_diff = min(min_diff, nodes[i] - nodes[i-1]) return min_diff You can also do this without saving the val of the nodes (O(1)). def minDiffInBST(self, root) -> int: if not node: return min(min_diff, ) **199 Binary Tree Right Side View** This is BFS, but only the right most nodes. If there are left nodes that are deeper than the right, we return those. So this is level order traversal, but we only return the right most elem in each level. def rightSideView(self, root) -> List[int]: res = [] queue = deque([root]) while queue: queue_size = len(queue) for i in range(queue_size) cur = queue.popleft() if i == queue_size - 1: res.append(cur.val) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) return res --Review (all paths)-- Goal here is to print all paths of a binary tree. def binaryTreePaths(self, root) -> list: res = [] def dfs(node, path): if not root: return path.append(node) if not root.left and not root.right: res.append('->'.join(path)) dfs(node.left, path) dfs(node.rigth, path) path.pop() dfs(root, []) return res **Binary Tree Level Order Traversal II** Ok, I'm going to Jank it by doing res[::-1] **Binary Tree Level Order Traversal** Corrected version according to chat GPT: def levelOrder(root): if not root: return [] res = [] queue = deque([root]) while queue: level_size = len(queue) level = [] for _ in range(level_size): cur = queue.popleft() level.append(cur.val) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) res.append(level) return res This is just BFS. def levelOrder(root): res = [] def BFS(root): queue = deque() queue.append(root) while queue: cur = queue.popleft() res.append(level) level = [] if cur.left: queue.append(cur.left) level.append(cur.val) if cur.right: queue.append(cur.right) level.append(cur.val) BFS(root) return res **450 Delete Node in a BST** GPT Corrected Answer: def deleteNode(self, root, key): if not root: return if key < root.val: root.left = self.deleteNode(root.left, key) elif key > root.val: root.right = self.deleteNode(root.right, key) else: if not root.left: return root.right elif not root.right return root.left #Node with two children min_larger_node = root.right while min_larger_node.left: min_larger_node = min_larger_node.left root.val = min_larger_node.val root.right = self.delete(root.right, root.val) return root Seems like we return the root of the tree. Lets solve this using recursion. In a BST, if the node being deleted has: 1) no child, remove from tree 2) 1 child, replace node with child 3) 2 children, find smallest node in right subtree. def deleteNode(self, root, key) -> TreeNode: if not root: return #search tree if root.val < key: self.deleteNode(root.right, key) else: self.deleteNode(root.left, key) #delete node if root.val == key: if not root.left and not root.right: root == None elif root.left ^ root.right: #swap the nodes if root.left: root = root.left root.left = None else: root = root.right root.right = None else: cur = root.right while cur: #find min val of right subtree cur = cur.left root = cur cur = None return root One thing to recall, is that other than adding a node, when you're modifying a tree using recursion, you should set root.left and root.right to the recursive call unless you have a good reason not to. --Review-- **701 Insert into a Binary Search Tree** def insertIntoBST(self, root, val): -> TreeNode if not root: return TreeNode(val) if root.val < val: if not root.right: root.right = TreeNode(val) else: self.insertIntoBST(root.right, val) else: if not root.left: root.left = TreeNode(val) else: self.insertIntoBST(root.left, val) return root //Apr 24 2024 **Delete Node in a BST** I am way too lazy to figure out the exact method when there are children nodes. Something about a rotation. **Insert into a Binary Search Tree** Lets try the recursive solution to insert into a binary tree again: def insertIntoBST(root, val): if not root: return TreeNode(val) if root.val < val: if not root.right: root.right = TreeNode(val) else: insertIntoBST(root.right, val) elif root.val > val: if not root.left: root.left = TreeNode(val) else: insertIntoBST(root.left, val) return root Lets try a solution of this that uses recursion: def insertIntoBST(root, val): if not root: return TreeNode(val) if val < root.val: return insertIntoBST(root.right, val) else: return insertIntoBST(root.left, val) return root Lets think of the iterative solution. When inserting, we should make sure its a balanced BST. 4 / \ 2 7 / 6 In this example, lets say that we try to insert 5. It would not make sense to insert it to the left of 6. 4 / \ 2 5 / \ 6 7 This following tree would make more sense. The algo for this is. def insertIntoBST(root, val): if not root: return TreeNode(val) cur = root while cur: if val < cur.val: if not cur.left: cur.left = TreeNode(val) return root cur = cur.left else: if not cur.right: cur.right = TreeNode(val) return root cur = cur.right return root **235. Lowest Common Ancestor of a Binary Search Tree** Based on the iterative solution, lets try to write the recursive version: def findLCA(root, p, q) if not root: return None if p.val > root.val and q.val > root.val: return findLCA(root.right, p, q) elif p.val < root.val and q.val < root.val: return findLCA(root.left, p, q) return root More refined GPT version of the code (you do not need recursion) def findLCA(root, p, q): while root: if p.val > root.val and q.val > root.val: root = root.right elif p.val < root.val and q.val < root.val: root = root.left else: return root return None The def for the lowests common ancestor of a BST seems to the the lowest node that can access both p and q -> We'll name that node T. We know the answer is T if the left subtree and the right subtree has p and q respectivly. The targets are p and q. We only have to traverse root. def lca(root, p, q) -> TreeNode: if not root: return #traverse: lca(root.left) lca(root.right) Since this is a BST, we just have to find the first node between p and q. if root.val < p and root.val < q: traverse(root.right) if root.val > p and root.val > p: traverse(root.left) if (root.val < p and root.val > q) or if (root.val > p and root.val < q): return root if (root.val == p or root.val == q) return root **Construct String from Binary Tree** 1) Just do post oder traversal 2) If not left or right, add left 2) If not right, add right def tree2str(root): -> str: if not root: return '' res = str(root.val) if root.left or root.right: res += '(' + self.tree2str(root.left) + ')' if root.right: res += '(' + self.tree2str(root.right) + ')' return res **N-th Tribonacci Number** First attempt: def tribonacci(n): if n == 0: return 0 if n == 1 or n == 2: return 1 return self.trib(n-1) + ... The problem with is this that we run out of memory for the call stack, so we need to "remeber" our answers def tribonacci(n): hash_map = {0:0, 1:1, 2:1} def helper(n): if n in hash_map: return hash_map[n] else: hash_map[n] = helper(n-1) + helper(n-2) + helper(n-3) return hash_map[n] return helper(n) //Apr 23 2024 **Construct String from Binary Tree** Correct solution: def tree2str(self, root): if not root: return '' def helper(node): if not node: return '' res = str(node.val) if node.left or node.right: res += '(' + helper(node.left) + ')' if node.right: res += '(' + helper(node.right) + ')' return res return helper(root) GPT helped me contruct a better rule set: 1) if root node: append val 2) if left node: append left child (recursive) 3) if left node don't exist, but right, append () 4) if right node: append recursive right res 5) if leaf, return def tree2str(self, root): -> str: res = root.val def helper(node): if not node: return '' if not node.left and node.right: res += '()' if not node.left: res += '(' + helper(node.left) + ')' if not node.right: res += '(' + helper(node.right) + ')' helper(root) This seems like root, left, right traversal (dfs). The trick is to figure out the rules of the (). if root node = append 'val' if leaf node = append '(val)' if None, append '()' At the start of going into every child '(' and at the end ')' **Path Sum** Todo: Try an all paths algo GPT reccomendation: def def(node, cur_sum): if not node: return False cur_sum += node.val if not node.left and not node.right: return cur_sum == targetSum return dfs(node.left, cur_sum) or dfs(node.right, cur_sum) Somthings to remeber. When you want to check if either the left or right subtree contains x, you can do dfs(left) or def(right) provided that the return val is True or False. Also, if not node.left and not node.right is to check the leaf node which you have to do. And the base case is, if you run out of nodes to check, return False. Check if root-to-leaf path has all values == sum. This is dfs. def dfs(node, cur_sum): if cur_sum == targetSum: return True return dfs(node.left, cur_sum += node.val) return dfs(node.right, cur_sum += node.val) return dfs(root, 0) The problem with this is that if a subpath == targetSum, it'll return True. **Merge Two Binary Trees** Another (more space efficent method) is to only manipulate the pointers to the tree nodes and update the vals. def mergeTrees(root1, root2): if not root1: return root2 if not root2: return root1 root1.val += root2.val root1.left = mergeTrees(root1.left, root2.left) root1.rigth = mergeTrees(root1.right, root2.right). return root1 Easiest approach is to create a new BT: def mergeTrees(root1, root2): if not root1 and not root2: return val1 = root1.val if root1 else 0 val2 = root2.val if root2 else 0 root = TreeNode(val1 + val2) root.left = self.mergeTrees(root1.left, root2.left) root.right = self.mergetTrees(root1.right, root2.right) return root Ok, you are missing an additional check. Because root1 could be None. root.left = self.mergeTrees(root1.left if root1 else None, root2.left if root2 else None) root.right = self.mergeTrees(root1.right if root1 else None, root2.right if root2 else None) You are given root1 and root2. Traverse through the tree. Merge tree 2 into tree 1. Return the root of tree 1 @ end. If both have values, sum them. The return val should be the pointer to the correct nodes. Base cases: if not root1 and not root2: return root1 #return the head of the first merged binary tree if not root1: return mergeTrees(root1, root2.left) **108. Convert Sorted Array to Binary Search Tree** Given interger array nums sorted (l -> h) convert to height balanced BST. Ok, I'm thinking, for this problem, would we want to start at the root node? How can we determine which index of arr should be root? 1,2,3,4,5,6 def sortedArrayToBST(nums): L, R = 0, len(nums) M = (L + R) // 2 root.left = sortedArrayToBST([L:M]) root.right sortedArrayToBST([M+1:R]) return root wait. What if you break it up into sub arrays LHS [L:M] and RHS [M+1:R] and recursivly return the midpoint? Ok to create a tree, we have to have a return val. Ok, lets look to see if the question has a def of tree node (yes). The L and R pointers are really only useful for iterative approaches to this question, not recursive. You forgot to add a base case of if not nums, return None. def sortedArrayToBST(nums): if not nums: return M = len(nums) // 2 root = TreeNode(nums[M]) root.left = sortedArrayToBST([:M]) root.right = sortedArrayToBST([M+1:]) return root **310 Minimum Height Trees** 33% submission success. LOL. NAH. --Review-- Reverse Linked List def reverseList(head): if not head or not head.next: return head next_node = self.reversList(head.next) head.next.next = head head.next = None return next_node //Apr 22 2024 **773. Sliding Puzzle** Got to review: cur_row, cur_col = divmod(cur_zero_index, C) for move in dir: new_zero_index = cur_zero_index + move new_row, new_col = divmod(new_zero_index, C) # Ensure moves do not wrap around rows if new_zero_index < 0 or new_zero_index >= R * C or \ (move == 1 and cur_col == C - 1) or \ (move == -1 and cur_col == 0): continue TLDR is to prevent wrap arounds. This part also generalizes to n grids. Final answer: class Solution: def slidingPuzzle(self, board: List[List[int]]) -> int: queue = deque() visted = set() target = '123450' R, C = len(board), len(board[0]) dir = [3, -3, 1, -1] inital_state = '' for r in range(R): for c in range(C): inital_state += str(board[r][c]) visted.add(inital_state) queue.append((inital_state, inital_state.index('0'), 0)) while queue: cur_state, cur_zero_index, cur_depth = queue.popleft() if cur_state == target: return cur_depth for move in dir: new_zero_index = cur_zero_index + move if new_zero_index < 6 and new_zero_index >= 0: state_list = list(cur_state) state_list[cur_zero_index], state_list[new_zero_index] = state_list[new_zero_index], state_list[cur_zero_index] new_state = ''.join(state_list) if new_state not in visted: queue.append((new_state, new_zero_index, cur_depth + 1)) visted.add(cur_state) return -1 def sliding_puzzle(board): target = '123450' - Notice that the [[],[]] 2D array was converted to a str R, C = len(board), len(board[0]) Q: how do you convert [[123],[450]] -> '123450' str(board[0]) + str(board[1]). No. This will give '[123][450]' = ''.join(str(num) for row in board for num in row) Another way to write this is: inital_state = '' for r in range(R): for c in range(C): res += str(board[r][c]) You want to define directions as a tuple, and when looping through it you can do: for left_elem, right_elem in tuple_list: dir = [3, -3, -1, 1] #move down, up, left, right queue = deque((inital_state, inital_state.index('0'), 0)) #inital state, index of 0, depth while queue: cur_state, cur_zero_index, cur_depth = queue.popleft() if cur_state == target: return cur_depth for move in dir: new_zero_index = cur_zero_index + move if new_zero_index < 6 and new_zero_index >= 0: #bounds state_list = list(cur_state) state_list[cur_zero_index], state_list[new_zero_index] = state_list[new_zero_index], state_list[cur_zero_index] new_state = ''.join(state_list) if new_state not in visted: queue.append(new_state, new_zero_index, cur_depth + 1) visited.add(cur_state) return -1 Keep in mind that cur_state = '123450'. How do we map [+-1, +-1] to that? '123 450' We can convert to int and look at it as a 6 digit int and divide. Or we can use it as a str and index. I do belive that the str method is easier. '123450' Move down = i + 3 Move up = i - 3 Move left = i - 1 Move right = i + 1 To check if in bounds, we can simply do new_ >= 0 Q: What is the solving condition? [[1,2,3],[4,5,0]]. We can do BFS. There is no dead ends which makes it easier? Note that there is no condition that allows us to return -1 right away. 1) we know to to do bfs. 2) the key problem is to simulate the movements of the board. [1,2,3] 0th index [4,0,5] 1st index You can only move the vals directly to the left, right, above, and below. Q: how do we simulate moving across the 2d arr. left: board[i][j-1] right: board[i][j+1] above: board[i-1][j] below: board[i+1][j] You're swapping bounds 0 =< i < 1, 0 <= j < 2. Q: how do we find the 0th val. We can pass the location of 0th val as param. We also want a cur_depth param. setup to find 0th val: target = str([[1,2,3],[4,5,0]]) R, C = len(board), len(board[0]) for r in R: for c in C: if board[r][c] == 0: bfs(r,c) def bfs(r,c): queue = deque() visited = set() inital_state = str(board) queue.append(inital_state, r, c, 0) #want to add location of 0, and cur_depth visited.add(inital_state) while queue: cur_state, r, c, cur_depth = queue.popleft() if cur_state = target: return cur_depth for move_y in (-1, 1): for move_x in (-1, 1): if r + move_x < 1 and r + move_x >= 0 and c + move_y < 2 and c + move_y >= 0: #check if valid move cur_state[r][c], cur_state[r + move_x][c + move_y] = cur_state[r + move_x][c + move_y], cur_state[r][c] #swap locations if cur_state not in visited: queue.append(cur_state, r, c, cur_depth + 1) visited.append(cur_state) return -1 **752 Open the Lock** Quiz Q2: Ok. My main fumble is the fact that only calculated for the ith elem in comb. When generating new_state, I have to do: ith = (int(cur_state[i]) + movement) % 10 new_state = cur_state[:i] + str(ith) + cur_state[i+1:] while queue: cur_state, cur_depth = queue.popleft() if cur_state == target: return depth #Q: do you want to generate new states first or do a check to see if valid (not in deadend, generate first. You want to see if you need to append the generated val, much like how you do for neighbors first in adj list) for i in range(4) #len of comb for movements in (1,-1): #calculate new movements new_state = str((int(cur_state[i]) + movements) % 10) if new_state not in deadends and new_state not in visited: queue.append((new_state, cur_depth + 1) visited.add(new_state) 0000 1) move through the arr. 2) +1 -1 we start off as str, convert to int. new_state = str((int(cur_state[i]) + movements) % 10) Quiz Q: queue = deque() deadends = set(deadends) visited = set([('0000', 0)]) queue.append([('0000', 0)]) Proper solution: deadends = set(deadends) visited = set() queue = dequeue() initial_state = '0000' if initial_state not in deadends: queue.append(inital_state, 0) visited.add(inital_state) #we don't have to add depth to hashmap Another thought/better method to do this: deadends = set(deadends) queue = deque() visited = set() initial_state = '0000' if initial_state in deadends: return -1 queue.append((initial_state, 0)) visited.add(initial_state) Asked GPT for answer: def openLock(deadends, target): dead = set(deadends) # Hash set for quick lookup queue = deque([('0000', 0)]) # (state, depth) visited = set('0000') if '0000' not in dead else set() while queue: state, depth = queue.popleft() if state == target: return depth for i in range(4): for move in (-1, 1): # Decrement or increment each wheel new_state = list(state) new_state[i] = str((int(new_state[i]) + move) % 10) new_state = ''.join(new_state) if new_state not in visited and new_state not in dead: visited.add(new_state) queue.append((new_state, depth + 1)) return -1 Lets try a BFS approach. We could see this as 1) 4d matrix 2) adj list. We can't do either with this problem. @ each decision point, we have 8 possible paths. So this is a BFS on a tree with 8 children. Total 4 deep. Ok 1) this is not 4 deep. There is 10k possible states. This is closer to a graph because each node could have mutiple predecessors - think graph with cycle since the circular nature of the wheel. The lock has circular wheels with vals from 0 - 9, len(4) as str. Return min numbers of turns to unlock the lock. 1) We need a hash map of our tried vals, if in set, retun -1. This means that we ended up where we started = no way to reach target val (you're going to end up in inf loop). The first thing I'm thinking about, is when incrementing/decreaing the vals, is it better to start from [0] or [-1]? Does it matter? (recall you can both increase/decrease). Lets walk through an example together. Go from start. target = 0202 1) match [0] index. Done. i += 1 0000 2) match [1] index. Done i += 1 0200 3) match [2] index. i += 1 0200 This is a BFS problem. Q: Can we make a decision tree and then BFS it? --Review-- Reverse linked list using recursion: def reverse(head): if not head or head.next: return head next_node = reverse(head.next) next_node.next.next = head head.next = None return next_node Traverse a linked list using recursion: def traverse(root): if not root: return print(root) return traverse(root.next) //Apr 21 2024 **Subtree of Another Tree** def isSubtree(self, main_tree, sub_tree) -> bool: if not main_tree: return False if not sub_tree: return True if self.sameTree(main_tree, sub_tree): return True return self.isSubtree(main_tree.left, sub_tree) or self.isSubtree(main_tree.right, sub_tree) def is sameTree(main_tree, sub_tree) -> bool: if not main_tree and not sub_tree: return True if main_tree == None or sub_tree == None or main_tree.val != sub_tree.val: return False return sameTree(main_tree.left, sub_tree.left) and sameTree(main_tree.right, sub_tree.right) def isSubtree(self, s, t) -> bool: if not t: return True if not s: return True if self.sameTree(s,t): return True return self.isSubtree(s.left, t) or self.isSubtree(s.right(s.right, t)) def sameTree(self, s, t): if not s and not t: return True if s and t and self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right) return False The key thing we got to figure out is how to determine if the tree is the stubtree of another. The flag is a valid strat. However, there is prob a better method to do this. Another method is to when unwinding the tree, the the vals of subtree to some wacky val. And after the first traversal, traverse the subtree again and check if all the subtree vals are set to that wacky val. This leads to a bunch of problems. You use extra space and assume that the marked val does not exist in the orgional tree. The subtree problem shares a lot of similarties with the problem below. It seems to me like that the trick to this question is if you can exhaust the entire subtree. The problem here is we don't know when we've reached the subtree when recursing. So we can only really figure out if its a subtree in during the unwinding phase. Recall, the problem to check if two trees p and q are equal is: def isSameTree(self, p, q) -> bool: if not p and not q: #This means that we reached the end of the tree return True if p is None or q is None or p.val != q.val: return False left_same = isSameTree(p.left, q.left) right_same = isSameTree(p.right, q.right) return left_same + right_same return isSameTree(p,q) **Find if Path Exists in Graph** Asked GPT to help review my code. There is a few issues with my implementaion. We have to 1) create an adj list from the edge list: graph = {i: [] for i in range(n)} for u, v in edges: graph[u].append(v) graph[v].append(u) Ok. So one thing to remeber is to convert to adj list when doing the traversals- this actually seem to be most of the problem a lot of the times. Then you have DFS and BFS written so much that I can write it faster than one can take a piss. In the context of graph theory, u = edge and v = vertext. Question, if the graph was not unidirectional, what would creating the adj list look like? graph = {i: [] for i in range(n)} for u, v in edges: graph[u].append(v) graph[v].append(u) It would look like so: { 0: [1, 2], # Only 0 to 1 and 0 to 2 1: [2], # Only 1 to 2 2: [] # No outgoing edges from 2 } graph = {i: [] for i in range(3)} for u, v in edges: graph[u].append(v) visited = set() def dfs(dst, src): if src == dst: return True visited.add(src) for neighbor in graph[src]: if neighbor not in visted: if dfs(negihbor, dst): return True return False This is a DFS algo. def validPath(n, edges, source, destination): visited = set() visted.add(source) def dfs(n, edges, src, dst): if dst == src: return True if src not in visited: visted.add(src) for neighbor in edges[src]: if dfs(neighbor): return True dfs(n, edges, source, destination) **Same Tree** Corrected GPT code: def traverse(p, q): if p is None and q is None: return True if p is None or q is None or p.val != q.val: return False left_same = traverse(p.left, q.left) right_same = traverse(p.right, q.right) return left_same and right_same return traverse(p, q) Given the roots of p and q. Write a function to check if the trees are the same. def traverse(p,q, same): if not p or q: return if p.val != q.val: return False traverse(p.left, q.left, same) traverse(p.right, q.right, same) return True return traverse(p, q, True) **Balanced Binary Tree** Corrected version of isBalanced(self, root): def check_balance(node): if not node: return 0, True left_depth, is_left_balanced = check_balance(node.left) right_depth, is_right_balanced = check_balance(node.right) cur_depth = max(left_depth, right_depth) + 1 is_balanced = (is_left_balanced and is_right_balanced and (abs(left_depth - right_depth) <= 1) return current_depth, is current_balanced if not root: return True depth, is_balanced = check_balance(root) return is_balanced Ok, my understanding of this problem is wrong. It requires the checking of balance @ every node - not just the min max. Determine if a Binary Tree is height balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one. Ok. For this, we can just find the max height, min height for the tree and see if max depth - min depth > 1. Return false, else return true def isBalanced(self, root): def traverse(node): if not node: return 0 left = traverse(node.left) right = traverse(node.right) return [1 + min(left, right), 1 + max(left, right)] min_depth, max_depth = traverse(root) return max_depth - min_depth < 1 **Max Depth of Binary Tree** Ok, it seems like you made a locgical mistake in how depth is calculated. left = traverse = int. So is right. But to calculate the depth you do return 1 + max(left, right), very similar to return max(left, right) + 1 in the diameter of Binary Tree calculation. def maxDepth(self, root): def depth(node): if not node: return 0 left = depth(node.left) + 1 right = depth(node.right) + 1 return max(left, right) return depth(root) **Invert Binary Tree** Return the root after inverse def invertTree(self, root): if not node: return node.left, node,right = node.right, node.left invertTree(node.left) invertTree(node.right) return root **Binary Tree Postorder Traversal** Right, left, Root - Seems like its actually left, right, root def postorderTraversal(self, root): res = [] def traverse(node): if not node: return traverse(node.right) traverse(node.left) res.append(node.val) traverse(root) return res **Binary Tree Preorder Traversal** Root, Left, Right def preorderTraversal(self, root): res = [] def traverse(node): if not node: return res.append(node.val) traverse(node.left) traverse(node.right) traverse(root) return res **Binary Tree Inorder Traversal** If I recall, its L, R, Right. def inorderTraversal(self, root): res = [] def traverse(node): if not node: return traverse(node.left) res.append(node.val) traverse(node.right) return res **Diameter of Binary Tree** Chat GPT feedback: Incorrect increment. Correct code: def diameterOfBinaryTree(self, root): cur_max = 0 def depth(node): nonlocal cur_max if not node: return 0 left = depth(node.left) right = depth(node.right) cur_max = max(left + right, cur_max) return max(left, right) + 1 depth(root) return cur_max def diameterOfBinaryTree(self, root): cur_max = 0 def depth(node): nonlocal cur_max if not node: return 0 if not node.left and not node.right: return 1 left = depth(node.left) right = depth(node.right) cur_max = max(left + right, cur_max) + 1 return cur_max return depth(root) //Apr 20 2024 **Construct String from Binary Tree** Given root of binary tree. Node = int val, if left((val)()), if right(()(val)), if both: ((val)(val). You also have to mantain a stack for the closing brackets. Under x condition, you pop() and append the closing bracket. def tree2str(self, root): res = '' def dfs(root): if not root: return if not root.left: dfs(root.right) res.append('()(' + str(root.right.val) + ')') Crap. Seems like you have to spend some more time thinking about the rules of the brackets. **Diameter of Binary Tree** Asked GPT to refined and fix code: def diameterOfBinarTree(self, root): cur_max = 0 def depth(node): nonlocal cur_max if not node: return 0 left = depth(node.left) right = depth(node.right) cur_max = max(cur_max, left + right) return 1 + max(left, right) depth(root) return cur_max To solve this you simply find the deepest left and right nodes. Combine the depths, return. def diameterOfBinaryTree(self, root): cur_max = 0 def depth(root): if not root: return 0 if not root.left and not root.right: return 1 left = depth(root.left) right = depth(root.right) return max(cur_max, left + right) return depth(root) **Invert Binary Tree** Attempt 2: def invertTree(self, root): def invert(root): if not root: return root.left, root.right = root.right, root.left invert(root.left) invert(root.left) return root return invert(root) The question is if you have to return any values for the recursive call. The answer is yes (duh). You are manipluating the left and right pointers. First attempt: class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: old_root = root def invert(root): if not root: return root.left = invert(root.left) root.right = invert(root.right) return old_root Ah I forgot about the base case of if not root. Also, how do we just return invert(root)? **Number of Ways to Arrive at Desitnation** LMAO fuk that. I don't wana do shortest path algo yet. **797. All Paths From Source to Target** Question would this work then? def allPathsSourceTarget(self, graph): res = [] def DFS(node, path): path.append(node) if node == len(graph) - 1: res.append(path) else: for neighbor in graph[node]: DFS(neighbor) path.pop() DFS(0, []) return res It appears to me that path is modified in place and only exisits within the recursive call. Asked GPT to help correct my pseudocode: def allPathsSourceTarget(self, graph): res = [] path = [] def DFS(node): path.append(node) if node == len(graph) - 1: res.append(path.copy()) else: for neighbor in graph[node]: DFS(neighbor) path.pop() DFS(0) return res You would want to use DFS to find all paths in a graph as it naturally handles path tracking through recursion. def allPathsSourceTarget(self, graph): res = [] visited = set() def DFS(node, path): visted.add(node) path.append(node.val) if node.val == target: res.append(path) elif node not in visited: for neighbor in node: DFS(neighbor, path) path.pop() return res Asked chatGPT, if you want to track all paths in BFS(), you can do the following: Seems like you want to do BFS using adj List. If == target, append path. def allPathsSourceTarget(self, graph): def BFS(node, path): queue = deque() visisted = set() queue.append(node) visited.append(node) while queue: cur = queue.popleft() for neighbor in cur: if neighbor in visted: return else: queue.append(neighbor) visited.add(neighbor) Question: How the heck do we append path during BFS without using recursion? You have to make an array, and append to that array everytime. If this arr == target, append to res. --Generating Subsets-- So combinations are actually very similar to subets, but you only append when k length has been reached. def combine(nums, k): res = [] def backtrack[start, path]: if len(path) == k: res.append(path) for i in range(start, len(nums)): backtrack(i + 1, path + [nums[i]]) backtrack[0, []] return res def subsets(nums): res = [] def backtrack(start, path): print(path) res.append(path) for i in range(start, len(nums)): backtrack(i + 1, path + [nums[i]]) backtrack[0, []] **1992 Find All Groups of Farmland** With help from GPT: def findFarmLand(land): if not land: return [] R, C = len(land), len(land[0]) res = [] def explore(r,c): if r >= R or or c >= C or land[r][c] == 0: return r-1, c -1 land[r][c] = 0 bottom_r = explore(r + 1, c)[0] right_c = explore(r, c + 1)[1] return bottom_r, right_c for r in range(R): for c in range(C): if land[r][c] == 1: orig_r, orig_c = r, c bottom_r, bottom_c = explore(r, c) return res Given m x n binary matrix. 0 = forested and 1 = farmland. There is no adjacent groups of farmland allowed. So you are returning the top left coordinate and the bottom right coordinate. 1) You want some way to scan the grid for 1s 2) You prob want to do DFS in the + x and - y dir since its perfect square. There is no case where Thought: You can probably get away with doing the search in one direction actually (r+1, c+1) When you start the append first [r,c] You also have to mark the entire rectangle as visited. def findFarmland(self, land): if not land: return R, C = len(land), len(land[0]) res = [] for r in range(R): for c in range(C): if land[r][c] == 1: diagonalSearch(r, c, [r,c]) def diagonalSearch(r, c, path): if r > R or c > C or land[r][c] != 1: path.append(r-1) path.append(c-1) res.append(path) return diagonalSearch(r + 1, c + 1) return res //Apr 19 2024 --Backtracking, combinations, subsets-- A subset is the list of all possible sets (matter does not order). The boiler plate code for subsets: def subsets(nums): res = [] def backtrack(start, path): res.append(path) for i in range(start, len(nums)): backtrack(i + 1, paths + [nums[i]]) backtrack[0, []) return res print(subsets([1,2,3])) **Max Depth of Binary Tree** def maxDepth(self, root): depth = 0 def dfs(root): if not root: return 1 #here we should return 0 since we hit a non exisiting node depth += dfs(root.left) + dfs(root.right) return depth Another problem is we are using depth to accumlate the depth of the tree. **Reverse String** base case: if L > R: return. Why do we want to return None instead of returning a value? if L > R: return s[R], s[L] = s[L], s[R] reverseString(L + 1, R - 1): Ok, so for this problem, we didn't need an explicit base case. The dfs(node.left) + dfs(node.right) calculates the entire sum of the tree. What we want to do is calculate the individual left and right depth by creating a var and setting it to dfs(left,right). Key thing to note is that we want to return if not node. Q: Would this base case also work? if not node.left and not node.right: return 1 This could work too. But you still need the if not node case regardless. def maxDepth(self, root): def dfs(node): if not node: return 0 left_depth = dfs(node.left) right_depth = def(node.right) return max(left_depth, right_depth) + 1 return dfs(root) //Apr 18 2024 **Swap Nodes in Pairs** Base case if not node or node.next, return head. if not head or head.next: return head next_node = self.swapPairs(node.next) #traverse the list Ok, you have a 1st node and a second node. You want the 2nd node to point to the 1st node and the first node to point to the last node??? Ok lets work this problem out together. We have 1->2->3->4. Afterwards: 1 -> 4 2 -> 1 3 -> None 4 -> 3 **894. All Possible Full Binary Trees** Chat GPT solution (no way I would've came up with this myself) def allPossibleFBT(N): # Using a dictionary to memoize the results for different values of N memo = {} def buildFBT(n): if n not in memo: if n == 1: memo[n] = [TreeNode(0)] else: trees = [] for left_size in range(1, n, 2): right_size = n - 1 - left_size for left in buildFBT(left_size): for right in buildFBT(right_size): root = TreeNode(0) root.left = left root.right = right trees.append(root) memo[n] = trees return memo[n] if N % 2 == 0: return [] # Return empty list if N is even, as it's impossible to form a full binary tree return buildFBT(N) Ok. if n == 1: memo[n] = [Treenode(0)]. What does that do? I'm not sure if I understand the syntax. Given a integer n, generate all possible full binary Trees. Base case if n == 0 Recursive case is when you use the nodes to build out the binary Tree. Return the possible ways you can build a binary tree. Almost seems like a permutaion/combination problem. Q: which one is it? More aligned with the principle of combinations rather than permutations. We are selecting possible splits of total nodes and the order of the groups do not matter only the size do. It seems to be the base cases should be n == 0 return 1 (valid tree) and n == 1 return 0 (invalid tree) and backtrack. Ok apperently this base case is not a good solution for the problem. Then what is the correct base case? Would you have to actually build out the tree to solve it? Ok so for the base case: if n == 0: return [] if n == 1: return ([TreenoNode()]) This looks similar to the all possible paths algo. Seems to me that both DFS and BFS would work here. Base case: if not child.left and not child.right Wait this seems to be the all paths algo but with BFS. Recall the BFS algo for binary tree: queue = deque while queue: cur = queue.popleft() #do somthing with cur queue.append(child.left) queue.append(child.right) The all paths algo: res = [] def allPaths(node, path): if not node: return path.append(node.val) if not child.left and not child.right: res.append(path) else: allPaths(node.left) allPaths(node.right) path.pop() So for all possible Full Binary Trees we can do: Ok. What happened here was that I misread the question. I thought you were given a tree, and you look at the subtrees to see how many unique subtrees form a full BST. **231. Power of Two** Same as before. **342. Power of Four** def powerOfFours(n): if n == 0: return False if n == 1: return True return self.powerOfFours(n) and n % 4 == 0 Its not that you don't know recursion, but rather you didn't think about what would make something isPowerOfFour. First and formost, the % must == 0, and the recursive call must == 1. Ok you fucked this one up. There are two basecases: 1) n == 0: return False 2) n == 1: return True else: return n % 4 == 0 Given a int, return if its a power of four, otherwise return False. return n % 4 == 0 and self.isPowerofFourth(n//4) def isPowerOfFour(n): if n == 0: return True isPowerOfFour(n // 4) return False **463. Island Perimeter** There were a few mistakes in my code mainly being that I get the bounds wrong. It should be: if r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0: return 1 We should also mark things as visited by setting it as -1 One thing I've been thinking of is why r < 0, c < 0 instead of <= 0 This is the problem of the day. To count the perimeter, we can simply count the total number of recursive steps. if not grid: return -1 R, C = len(grid), len(grid[0]) dfs(r, c): #1 check bounds if r <= 0 or c <= 0 or r > R or c > C or grid[r][c] != 1: return 1 if grid[r][c] == -1: return 0 return dfs(r+1, c) + dfs(r, c+1) + dfs(r-1, c) + dfs(r, c-1) for r in R: for c in C: if grid[r][c] == 1: res = dfs(r,c) return res //Apr 17 2024 **Remove Linked List Elements** def removeElements(self, head, val): if not head: return head head.next = sself.removeElements(head.next, val) return head.next if head.val == val else head Base case if not node. Recursive case removeElements(node.next) def removeElements(self, head, val): new_head = head def remove(root): if root.val == val: root.next = root.next.next remove(root.next) return new_head **998 Smallest String Starting From Leaf** The problem with my current pruning algo is the fact that it just keeps outputting "{" the entire time. Another attempt at is. You set self.shortest = None. for the pruning step, after you the current path, you do: if self.shorest is None or current_path < self.shortest: self.shortest = current path. Pruning algo: 1) Maintain global or recursive scope min 2) Before making the recursive call, compare cur path len w/ shortest path. If continuing would lead to longer or equal path, skip call 3) Keep updating the shortest path For 1) the shorest path would be a string 'abdbc' for example. The starting state would have to to be a inf str or int. In which we would do the comparision to. Before the recursive call, we would have min(cur path, shorest path). Brain too hurtie. Asked GPT to give me the code: self.shortest = '{' as this is the char that comes after z in ascii def dfs(node, path): if not node: return path.append(char(node.val + 97)) if not node.left and not node.right: cur_path = ''.join(reversed(path)) if cur_path < self.shortest: self.shortest = current_path else: if len(path) < len(self.shortest): dfs(self.left) dfs(self.right) path.pop() dfs(root, []) return self.shorest Now that we solved this question, is there a more optimal solution? What if we keep a running tally of the shorest path encountered, and if the cur path is longer than the shorest path, we break out of this recursive cycle and move onto another track right away? What I've been talking about is a method called pruning. Oh shet. Turns out that the nodes are vals 0-25. We have to convert them to str too: path.append(chr(node.val + 97)) There seems to be a few things wrong with my code. The main problem is that you 1) didnt have a case where res is empty string 2) the path should be from the leaf to root. Not root down to leaf. def smallestFromLeaf(self, root): res = [] def allPaths(node, path): if not node: return path.append(node.val) if not node.left and not node.right: res.append(''.join(reversed(path)) else: dfs(node.left, path) dfs(node.right, path) path.pop() allPaths(root, []) return min(res) if res else '' For this question, we can do dfs. The brute force approach is to add all paths to res and return min. def smallestFromLeaf(self, root): res = [] def allPaths(node, path): if not node: return path.append(node.val) if not node.left and not node.right: res.append(path) else: allPaths(node.left) allPaths(node.right) path.pop() return min(res) --Review DFS and BFS for Binary Trees + N-Node Tree-- def dfs(node): if not node: return dfs(node.left) dfs(node.right) def bfs(node): if not node: return queue = dequeu(node) while queue: node = queue.popleft() #process the node if node.left: queue.append(node.left) if node.right: queue.append(node.right) Now for n-node trees: def dfs(node): if not node: return #do something with the vals for child in node.children: dfs(child) def bfs(node): if not node: return queue = dequeue(node) while queue: node = queue.popleft() #do something for child in node.children: queue.append(node.child) **111 Minimum Depth of Binary Tree** This seems like a DFS problem. You have to keep the min depth (store it somewhere) def minDepth(self, root): dfs(root): if not node.left and not node.right: return 1 left = dfs(node.left) right = dfs(node.right) return 1 + min(left, right) return dfs(root) To visualize how this code would work, we can imagine that all of the leaf nodes start with a 1 (thus the return 1 if not node.left or node.right). When we do left or right = dfs(), we're adding 1 each node we go up. And the return 1 + min (left, right) returns the shortest path from the leaf to the cur node in the unwind. Eventually, when we reach the root, we'll return the shortest depth. **Palindrome Linked List** There is a more elegant recursive solution. We don't reverse the list, but we compare the nodes symmetrically from the front to the back without modifying the list structures. This method aviods reversing the list. The main idea goes as follows - as the recursive call unwinds (stack frames popped off) we compare the nodes encountered on the way back with nodes from the beginning using external reference to maintain state base case if not node. Recursive step - note we don't actually have to reverse the node but rather just compare the values from the top of the call stack with the cur node val. Then we pop off the stack and compare that to node.next. def isPalindrome(self, head): ref = [head] Above, we set the ref to be mutable. But y tho. TLDR, it allows you to keep the global state. def recurse(node): if not Node: return True result = recurse(node.next) if ref[0].val != node.val: return False ref[0] = ref[0].next return result return recuse(head) Ok the thing to keep in mind is once you reach the base case, the unwind is true, until ref[0].val != node.val. Then it just remains false. If that condition is never hit, then it just remains true the entire time, thus is a palindrome. Another way to write the reverse function: def reverseList(node): prev, cur = None, node while cur: cur.next, prev, cur = prev, cur, cur.next return prev new_head = reverseList(slow) Code review with GPT: def isPalindrome(head): if not head or head.next: return True slow = fast = head while fast and fast.next: slow, fast = slow.next, fast.next.next def reverseList(node): if not node or not node.next return node new_head = reverseList(node.next) node.next.next, node.next = node, None return new_head new_head = reverseList(slow) while new_head: if head.val != new_head.val: return False head, new_head = head.next, new_head.next return True You find the length of the list and reverse the other side. And you compare if the node vals are the same through out. You can use the fast and slow pointer to find head2 and size of the list. Don't actually need the size of the list Actually. 12321 is palidrome 123321 is also palidrome f = s = head while f and f.next: s, f = s.next, f.next.next new_head = s def reverseList(node): if not node: return node next_node = reverseList(node.next) node.next.next = node node.next = None return next_node reverseList(s) while head and new_head: if head.val != new_head.val: return False head, new_head = head.next, new_head.next return True --Review-- 3) Sum Root to Leaf Numbers Note that the code fails in the case root = [0,1] when you do not pass res in as a param in allPaths(). Think about why that might be. You wrote or instead of and for if not node.left and not node.right. This is pretty much the same question as the one below. The key diff is now you are appending the str, but turning it to an int. And at the end, you return the sum of res. 2) Binary Tree Paths. Given the root of a binary tree, return all the paths. We can use recursion to solve this. def binaryTreePaths(self, root): res = [] def allPaths(root, path): if not root: return path.append(root.val) if not root.left and not root.left: res.append(path) else: allPaths(root.left, path) allPaths(root.right, path) path.pop() allPaths(root, []) return res Forgot how to format the joining @ "->". res.append('->".join(path)) 1) Design a Hashmap def __init__(self): self.size = 10000 self.buckets = [[] for _ in range(self.size)] def hash(self, key): return key % self.size def put(self, key, value): bucket_index = hash(key) bucket = self.buckets[bucket_index] for i, (k, v) in enumerate(bucket): if k == key: bucket[i] = (key, value) return bucket.append(key, value) Ok, remeber that the keys are values are stored in pairs. One bucket could look like (k1,v1),(k2,v2) etc. If we do self.buckets = [[] for _ in range(10)] 1) Put key1 value a 1.1) Calculate bucket_index = hash(1) % 10 = 1 1.2) bucket = self.buckets[1] 1.3) Because bucket1 is empty (no key), append (key, value) [[], [(1, 'a')], [], [], [], [], [], [], [], []] Question. Could a bucket have mutiple key value pairs? Yes, if there is hash collisions. Ex if bucket size = 10. 2%10 vs 12%10 both == 2. Ok. When placing the key, we don't take the hash - the hash is only for calculating the index of the bucket. def get(self, key): bucket_index = hash(key) bucket = self.buckets[bucket_index] for i, (k, v) in enumerate(bucket): if k == key: return bucket[i][1] return -1 Ok, it works, but we didn't need the indexing of bucket[i] def get(self, key): bucket_index = self.hash(key) # Use the class's hash method bucket = self.buckets[bucket_index] for k, v in bucket: if k == key: return v # Directly return the value return -1 # Return -1 if the key is not found def remove(self, key): bucket_index = self.hash(key) bucket = self.buckets[bucket_index] for i, (k,v) in enumerate(bucket): if k == key: bucket.remove(k,v) Accessing the index is used when we need to replace or update an item directly into the list. The way I implemented remove, the method takes in a single argument. The correct method is: def remove(self, key): bucket_index = self.hash(key) bucket = self.buckets[bucket_index] for item in bucket: if item[0] == key: bucket.remove(item) return # Exiting after removal is important to avoid modification during iteration issues return # Optional: handle the case where the key is not found Ok, notice the huge drop in efficency when you do for item in bucket vs for i, (k,v) in enumerate (bucket). When we are using enumerate, we can directly modify items in the list by index //Apr 16 2024 --Review-- 1) Design a Hashset def __init__(self): self.size = 10000 self.buckets = [[] for _ in range(self.size)] def hash(self, key): return key % self.size def add(self, key): bucket_index = self.hash(key) bucket = self.buckets[bucket_index] if key not in bucket: bucket.append(key) def remove(self, key): bucket_index = self.hash(key) bucket = self.buckets[bucket_index] if key in bucket: bucket.remove(key) def contains(self, key): bucket_index = self.hash(key) bucket = self.buckets[buket_index] if key in bucket: return True **Merge Two Sorted Lists** You are given two sorted lists. L1 and L2. Merge them by splicing together nodes of the two lists. Return the head of the merged linked list. base cases: if not list1, return list2 if not list2, return list1 if list1.val > list2.val: list1 = mergeTwoList(list1, list2.next) return list1 else: list2 = mergeTwoList(list1.next, list2) return list2 Ok, I was pretty close, but I fucked up the traversals. You want to move to the next val of the list. def mergeTwoLists(list1, list2): if not list1: return list2 if not list2: return list1 if list1.val < list2.val list1.next = mergeTwoLists(list1.next, list2) return list1 else: list2.next = mergeTwoLists(list1, list2.next) return list2 **Fibonacci Number** f(n) = f(n-1) + f(n-2), base case n = 1 return 1, n = 0 return 0 **Reverse Linked List** Reverse a linked list using recursion. What is the base case: if not head, return. Q: Do you want to return anything. A: yes, you want to return head. 1-2-3-4-5 In this list the head would just be 5 no? There seems to be a misunderstanding in that the final reversed list 5 will be the new head, but it actaully is 1? The recursion will terminate at the last node 5. So therefor isn't the first val returned 5? Ok, yes, we return 5. The recursive case: node, node.next = node.next, node The hint that GPT gave is that next_node = reverseList(node.next). Q: Why why do we want to set the next_node = reversedList(node.next)? This means that the return of the linked list will be node.next no? Unless we're setting node_node to a param we are going to be defining somewhere in the recursive function. That code snippet could be node.next.next = node 1-2-> points back to 1 node.next = None 1 does not point to anything. The recursive step repeats this. So: 1-2-3-4-5 turn into 5-4-3-2-1 where 1 points to None. I am on the right track with my understanding. The reason that for this question, they did next_node = reverseList(node.next) is that this call will eventually return the new head of the reversed list. Think about why that may be. 1-2-3-4-5. When you hit the base case, the pointer to 5 will be returned which is the new head. So the next_node holds the current node value. Ok. Now lets look at how the reconnecting works. By setting node.next.next = node, we are reversing the pointer. Why we do node.next = None makes sure that reversed node does not point back to it old next node which could create a loop. Given that, for the patter 1-2-3-4-5, we return at the base case 5. The unwind looks like: 4.next.next = 4 which points 5 -> 4 and 4.next = None 3.next.next = 3 which points 4 -> 3 and 3.next = None Etc etc etc. Finally, we return next_node (which is 5) bubbling up the next head. reverseLinked(self, head): if not head: return head node.next.next = node node.next = None next_node = reverseLinked(head.next) We don't need a helper function. Ok, the bigest problem is 1) I need to make the recursive call before doing the swap first- imgaine, you have to traverse to the end of the list and have all the nodes in the call stack before you do the reversal process. if not head or head.next (since we are calling node.next.next) next_node = self.reverseLinked(head.next) head.next.next = head head.next = None return next_node Ok. It seems to me that the next node is returned on every iteration. So in the example 1-2-3-4-5 the return for next node will be: head: 5 -> this is returned as next_node next_node: 4 next_node: 3 next_node: 2 next_node: 1 Is it safe to say that in a recursion problem where we are doing in place manipulation of the node, there should be a case other than the base case that does some form of return during every step. Ok to be 100% honest, the next_node part and the return still kind of confuses me. Its just to return/save the value of the next into the call stack right? **Swap Nodes in Pairs** Given a linked list, swap every two adj nodes and return head. Base case if not node.next or node.next.next (we want to stop if we are @ the 2nd last elem. 1-2-3-4 if not node.next or not node.next.next: return #Recursive case node, node.next.next = node.next.next, node swapPairs(node.next) Correct answer: def swapParirs(self, head): if head is None or head.next is None return head first_node = head second_node = head.next first_node.next = self.swapPairs(second_node.next) second_node.next = first_node return second_node Ok... I am very confused. **Reverse String** We know that the base case, we reduce til the len <= 1. Ok the trick to the recursive case is that we add all the elems exculding the 0th index. At the end, we add the 0th index. Like so: return reverse_string(s[1:])+s[0]) Initial call: ello + h llo + e lo + l o + l Combinding calls o + l -> ol ol + l -> oll oll + e -> olle olle + h -> olleh if len(s) <= 1: return s return reverse_string(s[1:]+s[0]) To implement a in place solution, we can use a helper function to swap elements recursively. The question is 1) why does the helper work where not having the helper failed 2) why do we even need a helper? Can we not just make the recursive call reverseString? The followup to this is then, for recursive functions, if we are introducing a new var, we always want to make a helper function right? def reverseString(self, s): def reverseHelper(L, R): if L < R: s[L], s[R] = s[R], s[L] reverseHelper(L + 1, R - 1) reverseHelper(0, len(s) - 1) Ok one thing I noticed after writing my helper function is the fact that I find it a lot easier to write recursive functions that does not have a return val ex return reverseHelper() or return doSomeThing(reverseHelper) This can be broken up into action oriented (no return val) vs value returning recursion. One thing to think about is when to use action oriented vs value returning recursion. Is there a heuristic? //Apr 15 2024 **Reverse String** We know how to do it using L R pointer, how do we do it using recursion. First and formost, the base case is if we reach the end. Before that can we do s[::-1] - this does not work as we are not doing an in place manimpulation. With recursion questions, there is always 1) base case 2) reduction step 3) combining results. In the context of this problem, we have: def reverse_string(s): if len(s) <= 1: return s return reverse_string(s[1:]+s[0]) **Happy Number** Determine if n is happy. For n to be happy 1) start with + int replace num by sum of sqaures of all digits. 2) Repeat till num == 1 3) If ends with 1 == 1 happy. n = 19 Q: What is the ending condition? Goes through entire loop without returning one. You can detect a cycle by using a set. numbers = set() while n not in numbers: Q: How do you split 19? While n / 10 = 1 n % 10 = 9 R = 9 nvm, there is a python method to do it. num = 12345 digits = [int[d] for d in str(num)] while n not in numbers: squared_digits = [int[2]**2 for d in str[n]] n = sum(squared_digits) if n == 1: return True numbers.add(n) return False **Intersection of Two Arrays** You take one. Make it a set. And iterate through the other arr and see if the elem occures in the set. If yes, append to res. class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: res = set() dup = set(nums1) for num in nums2: if num in dup: res.add(num) return list(res) **Contains Duplicate** dup = set() for num in range(len(nums)): if num in dup: return True dup.add(num) return False **Design Hashmap** Ok, this question is pretty much the same as design hashset. The question that is top of mind is how do we associate a key to a value? Brain is too fried, so I'm going to just use the answer that GPT gave to me: class MyHashMap: def __init__(self): self.size = 1000 self.buckets = [[] for _ in range(size)] def hash(self, key): return key % self.size def put(self, key, value): bucket_index = self.hash(key) bucket = self.buckets[bucket_index] for i, (k, v) in enumerate(bucket): if k == key: bucket[i] = (key, value) return bucket.append((key, value)) Ok, lets go through this function together. First we have bucket_index which is just a call to the hash func. Once we find the bucket, we have touples: (key, value). When using the enumerate, we access 1) the index 2) the touple of (key, value). If k == key (accessed key value), bucket[i] == key. This handles the case where there is already a key and we are simply adding a new value. The other case is if there is no assoicated key in which case we append a key, value in the assoicated bucket. bucket = [val1, val2, val3 ..etc] buckets = [bucket1, bucket2, ..etc] Now that we got that out of the way, let us try to write the get function by ourselves: def get(self, key) -> int: bucket_index = hash(key) bucket = buckets[bucket_index] for (k,v) in bucket: if k == key: return bucket v return -1 Ok lets think about the structure of the bucket again. Each bucket contains a list of: bucket = [(k1,v1), (k2,v2)...etc] def remove(self, key) -> None: bucket_index = hash(key) bucket = buckets[bucket_index] for i, (k,v) in enumerate(bucket): if k == key: bucket.remove((k,v)) #Figure out if this is correct syntax del bucket[i] return Something to keep in mind is when you use the remove method, you don't have to do the enumerate through the bucket. for item in bucket: if item[0] == key: bucket,remove(item) break **Sum Root to Leaf Numbers** class Solution: def sumNumbers(self, root): def allPaths(node, path, res): if not node: return # Add current node's value to the path path.append(str(node.val)) # Check if it's a leaf node if not node.left and not node.right: # Join path into a number and add to results res.append(int(''.join(path))) else: # Continue to traverse the tree allPaths(node.left, path, res) allPaths(node.right, path, res) # Backtrack by removing the last node in the path path.pop() res = [] allPaths(root, [], res) return sum(res) **Binary Tree Paths** Correct method cleaned up by chat GPT: def all_paths(node, path, res): if not node: return path.append(str(node.val)) if not node.left and not node.right: res.append('->'.join(path)) else: all_paths(node.right, path, res) all_paths(node.left, path, res) path.pop() res = [] all_paths(root, [], res) return res We need to continue passing through path and res because we use those params to maintain the state through our functions. Also, we can pass [] as path because we don't need to return it outside of the all_paths func right? Lets say if we need to return the path in the outer function, then we would need to declare path = []. This is a sub problem to Sum Root to Leaf Numbers: def binaryTreePaths(self, root): def all_paths(node, path, res): if not node: return path.append(node.val) if not node.left and not node.right: res.append(path.copy()) else: all_paths(node.left, path, res) all_paths(node.right, path, res) path.pop() def format_res(res): if res.len(1): return str(res[0]) for path in range(len(res)): for node in range(len(path)): res[path] += str(node) + '->' return res res = [] all_paths(root, [], res) format_res(res) **Sum Root to Leaf Numbers** Lets try to solve the all paths: path = [] def all_paths(node, path, res): if not node: return path.append(node.val) if not node.left and not node.right: res.append(path.copy()) else: all_paths(node.left) all_paths(node.right) path.pop() return res Ok, so you want to append all the number as they were a string. And then add it. It seems like in order traversal is the method to go. root.val to str. while root, root.left, root.right. Append val to int onto a res arr. At the end, return sum(res). Recall that the method of an in order traversal is: res = [] if root: traverse(root.left) res.append(node.val) traverse(node.right) traverse (root) For this, you want to do DFS tho. The DFS traversal algo explores the nodes and edges in a graph/tree before backtracking. def dfs(node): if node is None: return res += (to_string(node.val)) dfs(node.left) dfs(node.right) Q: Does this provide a DFS traversal of the entire tree? If the tree looks like: 1 / \ 2 3 / \ 4 5 The output would be 1,2,4,5,3. We need the following traversal: 1,2,4 1,2,5 1,3 You would actually need to do a different algo: def all_paths(root): def dfs(node, path, res): if not node: return path.append(node.val) if node.left is None and node.right is None: res.append(path.copy()) The path.copy() creates a shallow copy of path list. Q: why do we need it? We need to create a copy for all possible path and we do not further modify the new version of path. Ok. Remeber the base case. Generally it is always return None. Once you hit the case of if there are no more paths, then create a copy. The other case is to traverse. At the end, there is a path.pop(). I wonder what that does. The pop removes the last elem in the call stack. This is just standard backtracking. **Design Hashset** There are a few methods for hashset. __init__, add, remove, contains. In the _init_. you're setting the hashset as an empty array. For the add function, if not self.contains(key): self.hashset.append(key). But it seems to me that the self.contains(key) is O(n) as you're traversing through the entire array to check to see if the key is there. Same with the def remove(key) -> None: if self.contains(key): self.hashset.remove(key). Which is also O(n). Ok, lets do the shitty implementaion of the hashmap first: class MyHashSet: def __init__(self): self.hashset = [] def add(self, key): if self.hashset not contains(key): self.hashset.append(key) def remove(self, key): if self.contains(key): self.hashset.remove(key) def contains(self, key) -> bool: if self.hashset.contains(key): return True return False Lets walk through another (proper) method of implementing the hashset under the hood. def __init__(self): self.size = 1000 self.buckets = [[] for _ in range(self.size]] Ok the code above allocates 1000 empty arrays or buckets. My question is, why not just do: self.buckets = []*1000 <- This does not work because it mutiplies and empty list by 1000. One thing you got to think about is what is the diff between a immutable and mutable object. And why is python designed in a way where nums = [0] * 100 = immutable and list = [[]] * 1000 = mutable. Remember, when you are trying to generate a list of 1000 empty arrays, it is mutable (all the pointers reference the same mem location), therefore, you have to inialize it like: def __init__(self): self.size() = 1000 self.bucket = [[] for _ in range(size)] def hash_function(self, key): return key % self.size def add(self, key): bucket_index = self.hash_function(key) if key not in self.buckets[bucket_index]: self.buckets[bucket_index].append(key) Ok, so what you're doing is creating a hash of the bucket_index. Then you are storing the val of the key into the bucket_index elem of the buckets array. The naming is kinda confusing. The key you are suppose to be able to retreive at O(1) along with assoicated val. With the add function, lets see the scenarios. 1) The bucket is empty, therefor, set the val to the hash 2) the bucket is full, then you have to chain. def remove(self, key): bucket_index = self.hash_function(key) if key in self.buckets[bucket_index]: self.buckets[bucket_index].remove(key) At this point, it might be easier to defire bucket: def remove(self, key): bucket_index = self.hash_function(key) bucket = self.buckets[bucket_index] if key in bucket: bucket.remove(key) def contains(self, key): bucket_index = hash_function(key) bucket = self.buckets[bucket_index] if kye in bucket: return True return False //Apr 14 2024 **Design Hashset** You have to design a hashset with using any of the built in hash table libraries. def __init__(self): hashset = [] def add(self, key) -> None: **Rotate Linked List** Correct solution with optimizations: if not head or not head.next or k == 0: return head cur = head size = 1 while cur.next: size += 1 cur = cur.next cur.next = head k = k % size new_tail = head for _ in range(size - k): new_tail = new_tail.next new_head = new_tail.next new_tail.next = None return new_head Give the head of a linked list, roate the list right by k places. Idea: Turn the linked list into a cycle. So connect the tail with the head. Track how long the linked list is. Move the head k times. That is the new head. From new head, move size of linked list times, and break the next. That is the new tail. Return the new head. size = 0 cur = head while cur.next: size += 1 cur = cur.next cur.next = head cur = head for _ in range(k): cur = cur.next new_head = cur cur = new_head for _ in range(size): cur = cur.next cur.next = None return new_head There are a couple of things wrong with how I wrote my code. First and foremost my loop stops counting the size one node ealy because it checks for cur.next. The currect answer is while cur, or to add size +=1 at the end. Something else that is more of an optimization. Because rotating the list result in the same list, we should do k % size to minimize unessary rotations. That is a pretty big brained edge case that I did not think of. The fact that k can be larger than size. Finally, after determining the new head, we have to disconnect list properly. The first case: if not head or not head.next or k == 0: return head size = 1 cur = head while cur: size += 1 cur = cur.next cur.next = head k = k % size new_head = head for _ in range(size - k): new_head = new_head.next new_tail = head for _ in range(size - 1) new_tail = new_tail.next new_tail.next = None return return_head Example k = 10, size = 4 10 % 4 = 2. This is then equal to 2 rotations + 2(complete rotations). Therefore size - k = 4 - 2 = 2. Total number of rotations we need to calculate. Ok. So there seems to have been another error in my implementation. The key change is that after finding the new head, we have to immediately set the new_tail's next to None to break the cycle. We do not need the second loop. **Search in a Binary Search Tree** Ai ya. Yo do not need dfs for dis. Not doing this def serachBST(root, val): def _dfs(root): if not root: return if root.val == val: return True left_search = _dfs(root.left) right_search = _dfs(root.right) return left_serach or right_search Oh its a binary search Tree: def searchBST(root, val): def _dfs(node): if not node: return False # Return False if node is not found if node.val == val: return True # Return True if the value matches elif val < node.val: return _dfs(node.left) # Only search the left subtree if val is less than current node's value else: return _dfs(node.right) # Only search the right subtree if val is greater than current node's value return _dfs(root) # Start the search from the root --Practice Graph Implementations-- **Design a graph using adjList** Based off https://neetcode.io/problems/graph class Graph: def __init__(self): self.adjList = {} def addEdge(self, src, dst): if src not in self.adjList: self.adjList[src] = set() if dst not in self.adjList: self.adjList[dst] = set() self.adjList[src].add(dst) def removeEdge(self, src, dst) -> bool: if src or dst not in self.adjList: #ok, the syntax is wrong but right logic return False self.adjList[src].remove(dst) return True def hasPath(self, src, dst) -> bool: visted = set() return _dfs(src, dst, visited) def _dfs(self, src, dst, visited) -> bool: if src == dst: #This is the base case return True visted.add(src) for neighbor in self.adjList[src]: if neighbor not in visited: if self._dfs(neighbor, dst, visted): return True return False def _bfs(self, src, dst): visited = set() queue = deque() visted.add(src) queue.add(dst) while queue: cur = queue.popleft() if cur == dst: return True for neighbor in adjList[cur]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor, dst) return False **Rotten Oranges** Correct code: class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: if not grid: return -1 R, C = len(grid), len(grid[0]) rotten = deque() directions = [[1, 0], [0, 1], [-1, 0], [0, -1]] res, oranges = 0, 0 for r in range(R): for c in range(C): if grid[r][c] == 1: oranges += 1 elif grid[r][c] == 2: rotten.append([r, c]) while rotten and oranges > 0: for _ in range(len(rotten)): x, y = rotten.popleft() for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < R and 0 <= ny < C and grid[nx][ny] == 1: grid[nx][ny] = 2 oranges -= 1 rotten.append((nx, ny)) res += 1 return res if oranges == 0 else -1 Remeber for rotten oranges, you use bfs, so a queue. 0 = empty, 1 = fresh, 2 = rotten. You can rot oranges by marking a 1 as a 2. One thing to remember is that you have to start the rot evenly. So there could be mutiple areas in which you start the rot. Remember, you hoave to count the total number of steps it takes the orange to rot. if not grid: return -1 R, C = len(grid), len(grid[0]) rotten = dequeu() dir = [[1,0],[0,1],[-1,0],[0,-1]] res = 0 for r in range(R): for c in range(C): if grid[r][c] == '2': rotten.append([r,c]) def bfs(loc): while queue: cur = queue.pop() res += 1 for cur in dir: if cur[r][c] + dir[r][c] == '1': cur[r][c] + dir[r][c] == '2' rotten.append(cur[r][c] + dir[r][c]) else: continue return res Ok, lets think through if this piece of code would in theory work. You go through the entire grid and check the total number of oranges. Ok. What if there is a chance that there is an orange you cannot reach? In that case, you return -1 as well. So we add: oranges = 0 for r in range(R): for c in range(C): if grid[r][c] == '2': rotten.append([r,c]) elif grid[r][c] == '1': count += 1 When you infect an orange after: cur[r][c] + dir[r][c] == '2' Add: count -= 1 return res if count == 0 else return -1 **Island Perimeter** You're counting the number of recusrive calls (number of times the 1 grid tries to expand but fail) if not grid: return - 1 R, C = len(grid), len(grid[0]) res = 0 dfs(r,c): if r > R or c > C or r < 0 or c < 0 or grid[r][c] == 0: return 1 if grid[r][c] == -1: return 0 grid[r][c] = '-1' dfs(r + 1, c) dfs(r - 1, c) dfs(r, c + 1) dfs(r, c - 1) for r in range(R): for c in range(C): if grid[r][c] == 1: res += dfs(r,c) Something to to remeber is the fact that you want to do the addition of the perimeters within the dfs. You also want to mark visited as -1 instead of setting it as 0 to prevent recounting. Ok. You're code is mostly correct? There are some issues. First of all, the values should be 0,1,2. But you are using strings dumb dumb. Instead of pop, you should be using popleft (duh). Also also, cur is a coordinate, not a object. When updating the grid, you are doing ==. Finally you forgot to check to see if it falls out of grid space. //Apr 13 2024 --Practice Graph Implementation-- BFS Rotten Oranges: def orangesRotting(self, grid): if not grid: return -1 R, C = len(grid), len(grid[0]) bfs(r,c): for DFS Number of islands: Remeber to mark the islands as visited by setting the 1s to 0 in the dfs function def numIslands(self, grid): R, C = len(grid), len(grid[0]) res = 0 for r in range(R): for c in range(C): if grid[r][c] == 1: res += dfs(r,c,grid) def dfs(r,c,grid): if r < R and c < C and r >= 0 and c >= 0 and grid[r][c] == 1: grid[r][c] == 0 dfs(r+1, c, grid) dfs(r-1, c, grid) dfs(r, c+1, grid) dfs(r, c-1, grid) return #good practice to put the base case at the start tho Correct ans: def numIslands(self, grid): if not grid: return 0 R, C = len(grid), len(grid[0]) res = 0 def dfs(r, c): if r < R and c < C and r >= 0 and c >= 0 and grid[r][c] == 1: grid[r][c] = "0" dfs(r + 1, c) dfs(r - 1, c) dfs(r, c + 1) dfs(r, c - 1) return for r in range(R): for c in range(C): if grid[r][c] == '1': dfs(r,c) res +=1 return res Ok dumb dumb. Just remeber to have the base case first. **Copy List with Random Pointer** The key is to go through the list and make a copy with nodes points to random nodes. So each node has two pointers: 1) next 2) random. What you want to do is iterate through the list while cur. and cur = cur.next. If the random pointer points to an exisiting node, good, if not, create it and point to it. This is where we hit our first problem. If we already created a random val in the future, and we now have a cur.next that is suppose to point to it, how do we accomplish that? The assumption is that we cannot solve this question in a single run and we need extra O(n) space. You can solve the problem of figuring out the mappings of the random pointers by creating a hash map when going through the first run of the linked list. The key of the map can be the pointers of the orgional node, while the vals that we later look up is the the assoicated deep copy. First thing is first, lets create a hash map: hashmap = {} Now let us iterate thorugh the orgional list, and create the deep copy of only the next vals while adding it to the hashmap. The sub problem to remeber here is to remeber how to create a new node. I'm going to ask GPT for the syntax. A: We can call the new_node = Node(5) keyword. cur = head while cur: copy_cur = Node(cur.val) hashmap[cur] = copy_cur cur = cur.next That creates: 1 - 2 - 3- 4 - 5. But there is no connections. It seems like we have to make all the connections on the second iteration. So that means we have to save cur.next vals as well. We can use an array in the hashmap to store [next] and [random]. cur = head while cur: copy_cur = Node(cur.val) hashmap[copy_cur]['next'] = cur.next hashmap[copy_cur]['random'] = cur.random cur = cur.next What makes more sense? Using the old nodes as keys or the new nodes? I would imagine using the old nodes as keys. Also you don't have to do the hashmap[copy_cur]['next'] and hashmap[copy_cur]['random'] crap. You just need to store the vals of the nodes. cur2 = head while cur2: hashmap[cur2].next = cur2.next hashmap[cur2].random = cur2.random You want to save the head of the new deep copy. CODE: cur = cur2 = head hashmap = {} new_head = Node(cur.val) while cur: cur_copy = Node(cur.val) hashmap[cur] = copy_cur cur = cur.next while cur2: hashmap[cur2].next = hashmap[cur2.next] hashmap[cur2].random = hahsmap[cur2.random] return new_head Ok, I needed to take a mental break here, so I handed the rest to chatGPT. I had a good start, but the proper method to do it is as follows: if not head: return None hashmap = {} cur = head while cur: copy_cur = Node(cur.val) hashmap[cur] = copy_cur cur = cur.next cur = head #damn you dummy, I forgot that we had a reference to the orgional head node while cur: if cur.next: hashmap[cur].next = hashmap[cur.next] if cur.random: hashmap[cur].random = hashmap[cur.random] cur = cur.next return hashmap[head] **Flatten a Multilevel Doubly Linked List** Too lazy to write it correctly and think about all of the edge cases. The corrected version: def flatten(self, head): if not head: return head cur = head while cur: if cur.child: child_tail = self.merge(cur, cur.child) if cur.next: child_tail.next = cur.next cur.next.prev = child_tail cur.next = child_tail child_tail.prev = cur cur.child = None cur = cur.next return head def merge(self, parent, child): current = child while current.next: current = current.next return current Ok, so it looks the the iterative solution might be better organized and easier to understand without the recursive overhead. For the primary flatten function, we iterate over the main list and look for nodes with children. When the node is found, you call the merge func. What the merge function does is locate the last node of the child list. Connect it to the main list node if it exists. Finally (you always seem to forget), you set the child pointer to None. def flatten(self, head): cur = head while cur or cur.child: if cur.child: child_tail = merge(cur.child) if cur.next: cur.next.prev = child_tail child_tail.next = cur cur.next = child_tail child_tail.prev = cur.next cur.child = None def merge(node): while node: node = node.next return node def flatten(self, head): if not head: #return the end of the node return head def some other function to flatten(): You pass node in as a param. if not node: return next_node = node.next if node.child: #you traverse it and return the end of the child and connect that to the next of the next higher tree. child_node = flatten_rec(node.child) #Then there is the case of if next or if child #Lets first work out the steps to reconnect the node #Link the cur node to the child node node.next = child_node child_node.prev = node if next_node: child_node.next = next_node next_node.prev = child_node Ok, in the code above, the one thing you messed up is that when you reach the base case of the recursion, you get the tail. What you also want to store, is the actual val of the child node. next_node = node.next if node.child: child_tail = flatten_rec(node.child) node.next = node.child node.child.prev = node node.child = None if next_node: child_tail.next = next_node next_node.prev = child_tail tail = flatten_rec(next_node) is next_node else child_tail return tail else tail = flatten_rec(next_node) return tail if tail else node We ran into a problem where we return an empty linked lists. I'm only returning the tail node of the flattened list @ the each step. So we have to come up with a method to return the head. def flatten(self, node): if not node: return None next_node = node.next if node.child: child_tail = self.flatten(node.child) node.next = child_tail child_tail.prev = node if node_next: node_next.prev = child_tail child_tail.next = node_next node.child = None return child_node else: return self.flatten(node_next) Ok, this code throws a big fat error when you return child_tail when it == None. To fix this, you have to add if child_tail. GPT helped solution: def flatten(self, node): if not node: return None next_node = node.next #ok that is a pretty big brain iterate through recursion instead of passing node.next as param if node.child: child_tail = self.flatten(node.child) #Ok, here you have to convience youself that child_tail actually returns the tail of the child. --- def flatten(self, head): if not node: return if node.child: node.next.prev = flatten(node.child) flatten(node.next) return node Ok, this is a first draft. The problem I'm thinking about is when we reach the end of the child, how do we reconnect the end of that lower level list back up to point to the next higher level. Seems like you want recursion for this problem. What you are doing is moving to the next node till it has a child. If it does, you want to traverse through all of the child nodes. You end up connecting the end of the child node to the start of the original next node. Q: how do you best traverse this? The first sub problem you have to solve is 1)How do you traverse a linked list recursively? def traverse_list(node): if not node: return None traverse_list(node.next) The advice that GPT gave is to also return the node. Which makes sense-> we need to know how to link the tree back together. To traverse to the child: if node.child: traverse_list(node.child) travse_list(node.next) So this will always traverse down to the child first. We also need to return the node up to the call stack at the end. Ok so now we have two options 1) build a new linked list (seems easier) 2) manipulate the pointers in place. Something else you want to consider is that you have to save a spot for the head pointer at the start and return it. The problem with the base case of None is the fact that we end up skipping the elems are after the child node. So we also need a method to add the next node. HOLY SHIT I got a big brain move. You simply when seeing a child node, save cur.next as well. This way you have a reference to next node on the higher level of the linked list, so you you are popping off the call stack, you can reconnect them then. **Reverse Words in a String II** 1) We want to break up the arr. 2) Iterate through the arr. 3) For reverse each word in the arr in place 4) Return arr s = s.split() for word in s: word = word[::-1] return ' '.join(s) The problem with this is that we are not modifying the orgional list s, instead assigning the a new var. **Reverse Words in a String** Given input string s, reverse the order of the words. s.split(' ') to split the words into arr. The hard part is that you also have to remove extra spaces. The solution seems to be words = s.strip().split() but what does that do? The .strip method in python is used to remove leading spaces sand trailing spaces. The. s.split method splits @ a specified char. If no params are given, it just splits @ whitespace. When you do .reversed(), you return the index not the words, so you have to ' '.join. So putting it all together. return ' '.join(reversed(s.split().split())) **Pascal's Triangle II** So given a rowIndex, return the row. We start each index from 0. It seems like you have a base case of first and 2nd row where you return [1] and [1,1] respectivly. Then, to generate cur row, cur_row = prev_row[i] + prev_row[i+1]. Recall to append a 1 before and after the loop. Outside, you simply have for i in range(rowIndex). res = [[1][1,1]] for i in range(2, rowIndex): res[i].append(1) for j in range(len(res[-2])-1): #calculating cur row val res[-1].append(res[-2][j] + res[-2][j+1]) res[-1].append(1) return res[-1] Correct ans: **Remove K Digits** This is apperently a Leetcode Hard, so I won't work on this just yet. **Rotate Array** nums = nums[k:] + nums[:k] Ok apperently you have to do it in place. I'm thinking you have have a queue, and then popleft() and then then append. But that requires a new DS (queue) so its not in place. The O(n*k) solution is: for i in range(k - 1): nums.append(nums.pop(0)) One way to solve the problem above is to use the slicing operation so that you dont have to create a copy of the OG arr. The pattern to notice is that you pop the last kth elem and append it to the front. So we can write it this way: nums[:] = nums[-k:] + nums[:-K] Something else to consider is the fact that you have to handle cases where k is larger than arr size. You did not think of the edge case where k > len(nums). In that case, we just wrap around. Going back, lets try to figure out what is wrong with the following answer: for i in range(k): nums.append(nums.pop(0)) Ok, so the problem is apprently an 1 off error. My current code rotates k-1 time. So the Q: is why not just use for i in range(k+1)? Then it would rotate the arr +1 times than required. I'm still not sure what the main diff between: nums.append(nums.pop(0)) and nums.insert(0, nums.pop()) The diff between the two lies in which elem are being moved. 1) removes the first elem and moves it to the back 2) You move it to the begining Holy shit, so the thing I've been doing wrong is inserting at the back rather than the start when rotation this arr. Ok, we found two methods to do this. We can also do it with two pointers no? The trick is to take elems @ the back and move them to the front. This is kinda harder to do because you have to swap the pos of every elem to the right by k. Ok. the question you have to figure out is if there is a O(n) time and O(1) space method using two pointers? A: possibly. Apprently there is also another trick where you do it using reversals. Ok, shot in the dark, you reverse the arr nums = [1,2,3,4,5,6,7], k = 3 to [7,6,5,4,3,2,1]. You popoff the last k elem and store them: [7,6,5,4] and [4,3,2,1]. Reverse them both and then add them to form [4,5,6,7,1,2,3,4]. Ok, so with the proper method, is a more explicit version of nums[:] = nums[-k:] + nums[:-k]. k = len(nums) start = 0 end = k while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1 Ok, the big brained move is to 1) reverse the entire arr 2) reverse the first k elems 3)reverse the remaining n-k elem. Ok, lets think through why this would work. starting state: [1,2,3,4,5,6,7] [7,6,5,4,3,2,1], now lets reverse the first k elem [5,4,7,4,3,2,1] now k->n elem [5,4,7,1,2,3,4] This is the correct output k = k % len(nums) n = len(nums) def reverse(start, end): while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1 reverse(0, n-1) reverse(0, k-1) reverse(k, n-1) //Apr 9 2024 **Rotate Array** return nums[:k] + num[k:][::-1] **Min Size Subarray Sum** This is a sliding window problem. Pretty much, if @ target, run the min(cur_min, global_min) return 0 if global_min = float('inf') L, R = 0, len(nums) - 1 _sum, global_min = 0, float('inf') for R in range(len(nums)): _sum += nums[R] while _sum >= target: global_min = min(R - L + 1, global_min) _sum -= nums[L] L += 1 return global_min if global_min != float('inf') else 0 **Max Consecutive Ones** Loop through it. Count max ones. if zero, cur ones = 0. cur_ones, max_ones = 0, 0 for num in nums: if num == 1: cur_ones += 1 max_ones = max(cur_ones, max_ones) else: cur_ones = 0 return max_ones **Remove Element** Given arra nums and int val, remove all vals in nums in place. Return # of elem in nums not equal to val. Ok, if == val, move back. k+= 1, return nums. k = 0 for i in range(len(nums) - 1): if num[i] != val: nums[i], nums[i+1] = nums[i+1], nums[i] k += 1 return k Ok, I'm still kinda ass at in place manipulations. So it turns out the correct method to do it is: for i in range(len(nums)): if nums[i] != val: nums[i], nums[k] = nums[k], nums[i] k += 1 return k **Two Sum II** In a sorted arr, find two numbers such that they add up to target. Return the two index. L, R = 0, len(numbers)-1 while L < R: _sum = numbers[L] + numbers[R] if _sum == target: return [L + 1, R + 1] elif _sum < target: L += 1 else: R -= 1 return [-1,-1] **Array Partition I** Given int arr and 2n ints, they pair up so the sum (a,b) for i is maxed. Return max sum. Are you not just returning the hightest and 2nd highest elem? You pair them largest to smallest. Wait it to min. So you sort the arr. Start from L and R. The largest val * the smallest val. res = 0 nums.sort() L, R = 0, len(nums) -1 while L < R: res += min(nums[L], nums[R]) L += 1 R -= 1 return res Ok this is a dumb ass q. So it seems like you're trying to find the max val given that res += min(nums[L], nums[R]). You don't even need two pointers. res = 0 nums.sort() for i in range(len(nums)-1): res += min(nums[i], nums[i+1]) return res Oops you have to increment i by two. You can do this by using the range function: i in range(0, len(nums)-1, 2). **Reverse String** L, R = 0, len(s) - 1 while L < R: s[L], s[R] = s[R], s[L] return s **Longest Common Prefix** 1) sort strs 2) start the first elem as prefix 3) if prefix != prefix of words prefix != [:len(prefix)-1] 4) prefix.pop() 5) retry. Then you reach the case where you return '' or prefix strs.sort() prefix = strs[0] while not done: #change into proper conditional for str in strs: if prefix != str[:len(prefix)-1]: prefix.pop() break return res Refined version: if not strs: return '' strs.sort() prefix = strs[0] If we decide to pop and empty string we'll have a one index error. The smarter method to do this is to have two loops like so: for s in strs: while not prefix == s[:len(prefix)] prefix = prefix[:-1] if not prefix: return '' return prefix **Reveal Cards In Increasing Order** Given deck where every card is unique. deck[i]. We can order deck however we want. Input: [17,13,11,2,3,5,7] Output: [2,13,3,11,5,17,7] queue = deque(deck) while queue: card = queue.popleft() #take the card from top queue.add(queue.popleft()) #next top at bottom Return odering that would reveal cards in increasing order. Seems to me that you just build the arr. We dont want to add to the left since shifting the index is O(n) Q: can we use the len of the queue to calculate the index of there the elem should go? res = [0] * len(deck) queue = dequeu(deck) while queue: Ok, what you want to do is sort the deck, and then simluate the reverse process with a queue. I think the key thing to notice is that if sorted maps to sorted queue and you run queue on it again, it maps back to sorted. I did not know that property of queues. The boiler plate code for a qeue traversal: queue = dequeue() arr = [...] for elem in arr: if queue: queue.appendleft() def deckRevealedIncreasing(deck): sorted_deck = sorted(deck, reverse = True) queue = deque() for card in sorted_deck: if queue: queue.appendleft(queue.pop()) queue.appendleft(card) return list(queue) //Apr 8 2024 **Squares of Sorted Array** continued The most elegent solution to this problem is if you leverage two pointers and merge directly without prechecking all pos or all neg. N = len(nums) We compute the index of the first non-neg numbers in nums list: first_non_neg = next(i for i, x in enumerate(nums) if x >= 0, N) The next expression finds the next index val. #All postive if nums[0] => 0: return [x**2 for x in nums] #All negative #Q: How do you map backwards from an array if nums[-1] < 0: return [x**2 for x in nums][::-1] L, R = 0, len(nums) - 1 while L <= R: M = (L + R) // 2 if nums[M] >= 0 and nums[M - 1] < 0: #From the above checks, we know M > 1 break elif nums[M] < 0: #can R side L = M + 1 else: R = M - 1 L, R = M - 1, M res = [] while L >= 0 or R < len(nums): if L < 0 or (R < len(nums) and nums[R]**2 < nums[L]**2): res.append(nums[R]**2) R += 1 else: res.append(nums[L]**2) L -= 1 return res Q: How do you write an algo to expand outwards? Start from M 1) while L and R pointer in bounds 2) whichever one is smaller, move and append to the new arr. Lets correct the code with feedback from GPT: The all pos and neg edge cases are correct. To find the pivot elem, if M > 0 and nums[M] >= 0 and nums[M-1] < 0. Everything is the same except you add M > 0 so you dont get a out of bound error. You do M > 0 to not get M[-1]. But I still dont get it. How can there be a case of M == 0, if we checked that the arr must contain + and - vals? The min len must be 2, thus M at the min must be 1. Ok, so the correct answer: if nums[0] >= 0: return [x**2 for x in nums] if nums[-1] <= 0: return [x**2 for x in nums][::-1] L, R = 0, len(nums) - 1 while L <= R: M = (L + R) // 2 if nums[M] < 0: L = M + 1 else: if nums[M - 1] < 0: break R = M - 1 L, R = M - 1, M res = [] while L >= 0 or R < len(nums): if L < 0 or (R < len(nums) and nums[R]**2 < nums[L]**2): res.append(nums[R]**2) R += 1 else: res.append(nums[L]**2) L -= 1 return res //Apr 7 2024 **Squares of Sorted Array** Given sorted array of nums. Return the squares of each number sorted in non-decreasing order. The easy solution is to square everything and return sorted. Recall that map: squared_numbers = [x**2 for x in numbers] return sorted([x**2 for x in nums]) Another solution is to find the pivot elem using binary search. Use binary search to find the pivot (last neg val). From there split the nums arr at the pivot. Reverse the neg elems- but you still end up needing to sort it. Start from the pivot and append to a new res arr. Expand outwords. [-4, -1, 0, 3, 10] -> [16, 1, 0, 3, 100] When comparing, take the squared val. You need binary search for finding the pivot. #All postive if nums[0] => 0: return [x**2 for x in nums] #All negative #Q: How do you map backwards from an array if nums[-1] < 0: return [x**2 for x in nums][::-1] #Contains neg number case L, R = 0, len(nums) - 1 while L <= R: if nums[M]**2 Followup question, is there a version of binary search for Large -> small -> Large again. **Find First and Last Position of Element in Sorted Array** You are given a sorted array. Try to perform normal binary search till you find the target val? You want to continue doing binary serach till the L and R vals of target != target. Its almost as if you have ML, MR (mid left) and (mid right). [5,7,7,8,8,10] L1, R2 = L1, R1 = 0, len(nums) - 1 while L1 <= R1 and L2 <= R2: M1, M2 = (L1 + R1) // 2, (L2 + R2) // 2 if nums[M1] == target and nums[M2] == target and nums[M1-1] < target and nums[M2 + 1] > target: return [M1, M2] if nums[M1] < target: L1 = M1 + 1 if nums[M2] < target: L2 = M2 + 1 if nums[M1] > target: R1 = M1 - 1 if nums[M2] > target: R2 = M2 - 1 return [-1, -1] Ok. The idea is umm.. and idea. But just use two seperate binary seraches. res = [-1, -1] L1, R1 = 0, len(nums) - 1 while L1 <= R1: M1 = (L1 + L2) // 2 if nums[M1] == target: if M == 0 and nums[M1-1] < target: res[0] = M1 break else: R1 = M - 1 if nums[M1] <= target: L1 = M1 + 1 else: R1 = M1 - 1 [...] repeat with M2 return res if res[0] != -1 and if res[1] != -1 else return [-1, -1] [5,7,7,8,8,10] M1 M2 From this you know that M2 >= M1 always. **Search in Rotated Sorted Array** L, R = 0, len(nums) - 1 while L <= R: M = (L + R) // 2 if nums[M] == target: return M if nums[L] <= nums[M]: if nums[L] <= target < nums[M]: L = M - 1 else: R = M + 1 else: if nums[M] < target <= nums[R]: R = M + 1 else: L = M -1 1 return - 1 Q&A Quiz w/ GPT 4: Q: Given arr of nums rotated on some unknown pivot. Ex [0,1,2,4,5,6,7] -> [4,5,6,7,0,1,2]. Find the target val in array. A: Do binary search till you find pivot elem. And then youre doing binary search two times. Once with the logic of if arr[M] < target: L = M + 1 (ascending), if arr[M] > target: L = M + 1 (desending) GPT A: While my method could work, it is not the most efficent. The above method breaks down into two main steps 1) finding the pivot 2) perform standard binary search. However, this method requires two passes through the data. Q: How can we do it in one pass? You can roate the sorted arr with one pass, determining which side of the target falls within the sorted portion. Q: Using binary search to find first occur of target where dups might exist. Return first index. A: else: while arr[L] == target, L -= 1. Return L. GPT A: A better approach that does not risk a O(n) loop looks at 1) if M > 0 and if arr[m-1] == target. R = m - 1. Return m. This way you're doing a 2nd binary search in the range of (last L -> m - 1). Smart! Q: Scenario to lead me to L = M + 1 assuming (L + R) // 2 A: if arr[M] < target **Single Element in a Sorted Array** Given sorted array of ints, every elem appears twice, except one. Return the elem that only returns once. O(1) Space and O(logn) time. We can't sort it because it's O(1) space. Can we use XOR? Probably not since that seems like it only works for detecting doubles of a val. Wait no oops, we can use XOR to detect single val. res = 0 for num in nums: res ^= num return res This is a O(n) solution with O(1) time. We know that it will be some form for binary search. Lower bound = 1st elem upper bound = last elem. WTF is the shrinking condition? We don't know where the single val is located. You have to cut it base on even or odd length of arr. If contain single == odd, else even. [3,3,7,7,10,11,11] ^ M L, R = 0, len(nums) You have to look at [L] and [L + 1] are the same and (R + L) % 2 == 0. If we do M = (L + R) // 2 on the example above, we get (0 + 7) // 2 = 3 (since rounded). Once you get to the mid point, you want to make a L and R scan. If dup on the L side, you know the repeat # in on the right of the arr. Keep doing it till you hit the num. while L < R: M = (L + R) // 2 if nums[M] == nums[M-1]: L = M + 1 else: R = M - 1 return M One thing we want to figure out for Binary Search Problems is when to return L, R, or M. A general rule of thumb is that you return L, when you're finding the first val that satisfies a certain condition. R for last occurance that satisfies condition. While the return M checks if the binary search has a exact match. They did nums[M] == nums[M+1], L = M + 1. The operation flips the last bit of M. That seems to overcomplicate things. The other method is to simply do M % 2 == 1: M -= 1 to always ensure that M is even. Correct solution that I understand: def findSingle(nums): L, R = 0, len(nums) - 1 while L < R: M = (L + R) // 2 isEvenIndex = M % 2 == 0 if (isEvenIndex and nums[M] == nums[M+1]) or (not isEvenIndex and nums[M] == nums[M-1]): L = M + 1 else: R = M return nums[L] **Sqrt(x)** Binary search. Search space from (0->x). while L <= R: M = (L + R) // 2 if M * M < x: L = M + 1 if M * M > x: R = M - 1 return M I believe that the M, the answer, will be returned at the L == R case, in which the loop exits. def mySqrt(x): L, R = 0, x while L <= R: M = (L + R) // 2 if M * M < x: L = M + 1 elif M * M > x: R = M - 1 else: return M # Perfect square case return R # For non-perfect squares, R is the integer part of the sqrt --Review AdjList Graph Design-- Example: { 1: {2, 3}, 2: {4}, 3: {4}, 4: {1} } class graph: def __init__(self): self.adjList = {} def addEdge(self, src, dst): if src not in self.adjList: self.adjList[src] = set() if dst not in self.adjList: self.adjList[dst] = set() self.adjList[src].add(dst) def removeEdge(self, src, dst) -> bool: if src not in self.adjList or dst not in self.adjList: return False self.adjList[src].remove(dst) return True def hasPath(self, src, dst) -> bool: vistied = set() return _dfs(src, dst, vistied) return bfs(src, dst, visited) def _dfs(self, src, dst, visited) -> bool: if src == dst: return True if src not in visited: visted.add(src) for neighbor in adjList[src]: return _dfs(neighbor, dst, visited) return False Ok you fumbled the DFS. if src not in visted: visited.add(src) for neightbor in self.adjList[src]: if self.dfs(neighbor, dst, visited): return True return False def bfs(self, src, dst, visited) -> bool: vistied.add(src) queue = deque() queue.append(src) while queue: cur = queue.popleft() if cur = dst: return True visited.add(cur) for neighbors in self.adjList[cur]: if neighbor not in visited: queue.append(neighbor) vistied.add(neighbor) return False //Apr 5-6 2024 **Valid Perfect Square** The brute for binary search method. You start off with range(0->num). L, R = 0, nums while L < R: M = (L + R) // 2 if M * M < nums: L = M if M * M > nums: R = M if M * M == nums: return True return False Correct solution: class Solution: def isPerfectSquare(self, num: int) -> bool: L, R = 0, num while L <= R: M = (L + R) // 2 if M * M < num: L = M + 1 elif M * M > num: R = M - 1 else: return True return False The key insight here is that L = M + 1 and R = M - 1 is generalizable to most binary search questions. **Arranging Coins** You have n coins and want to build a staircase with coins. Stairs have k rows where ith row have ith coins. Arr pattern: sum of coins: [1,3,6,10,15,21] n 1 2 3 4 5 6 R 21/6. Whats the formula that maps the R to n (number of coins?). The brute force method is to go through each row and do n+1 for each new row till we run out of coins to fill a row. Lets try that: row = 0 while n >= 0: row += 1 n -= row return row - 1 Now lets use binary search to solve this problem. Recall binary search is a method to cut the search space by 1/2 each time. Lets set the ceiling to n, and cut the search space by 1/2 each time. How do we go from R -> n? If we think about it geometrically, the staircase is 1/2 a square. So to get n from row we can do: n = ((r * r + r) // 2) Rearrange n * 2 = r*r + r n * 2 = r(r+1) We can use ax^2 + bx + c = 0 The solution for r = (-1 + (1 + 8 * n) ** 0.5) / 2. You can just floor that for the solution. Also remeber that the formula for arthemtic sum = m + m + 1 // 2 --Review of AdjLit BFS, DFS, Desgin-- Lets start with the design of a graph: class graph: def __init__(self): self.adjList = {} Ok Q: What does the __init__ method actually do in this context? Guess, it inialzies the adjList to a empty hashmap. And the self.adjList simply means that there could be mutiple instances of the same adjList object. Ok, update in knowledge: __init__ is a constuctor which is auto created when new instance of class is made. The word self signifies that the method belongs to cur instance of class meaning each instance of graph can have own seperate adjList ditc. def addEdge(self, src, dst): if src not in self.adjList: self.adjList[src] = set() if dst not in self.adjList: self.adjList[dst] = set() self.adjList[src].add(dst) def removeEdge(self, src, dst) -> bool: if src not in self.adjList[src] or dst not in self.adjList[dst]: return False self.adjList[src].remove(dst) return True def hasPath(self, src, dst) -> bool: vistied = set() return self._dfs(src, dst, vistied) I noticed that when you call another function within the func def such as ins hasPath, you dont have to manually add self as a param? Ex return _dfs(src, dst, vistied). This is because when calling another method from the same class, the self is implicity passed as the first param by python. def _dfs(self, src, dst, visisted)-> bool: if src == dst: return True if src not in visited: for neighbor in self.adjList.get(src, []): #we dont have to format it like that visited.add(neighbor) if self._dfs(neighbor, dst, vistied): return True return False Try again in the afternoon: def _dfs(self, src, dst, visited) -> bool: if src == dst: return True if src not in visted: visted.add(src) for neighbor in adjList[src]: if _dfs(neighbor, dst, visited): return True return False Ok, there might be still some small problems with my implementaion: The biggest being that we do not mark visited within the for loop. By doing that, it means we prematurely, mark the nodes as visited. its not like it will always fail, but it will add un-needed complexity. Aight, let us try with BFS. Remeber for bfs, you need to have a queue, and you keep popping off level by level. def _bfs(self, src, dst, visited) -> bool: queue = deqeue() queue.add(src) visited.add(src) while queue: for _ in range(len(queue)) cur = queue.popleft() if cur.val == target: return True for neighbor in AdjList[cur]: if neightbor not in visted: queue.append(neighbor) visted.add(neightbor) return False A few corrections: 1) for queue you do append instead of add- its not a set 2) you dont do cur.val, you look right at cur. Example: { 1: {2, 3}, 2: {4}, 3: {4}, 4: {1} } **Minimum Size Subarrary Sum Return min length of subarray that sum is greater or equal to target. Else return 0. This is a sliding window problem. You start off with a left pointer and a right pointer @ 0. L pointer shrinks the window (while sum of sub array >= target, shrink left, subtract l val from sub array), else, R++ (we can just do that in a for loop). return length. I read the question wrong the first time. L, total = 0, 0 length, min = 0, float('inf') for R in range(len(nums)): total += num[R] length += 1 while total >= target: min_length = min(length, min_length) L += 1 total -= nums[L] length -= 1 return min_length if min_length != float('inf') else min_length Corrected code: L, total = 0, 0 length, min_length = 0, float('inf') for R in range(len(nums)): total += nums[R] # Corrected typo here length += 1 while total >= target: min_length = min(length, min_length) total -= nums[L] # Subtract the current L, then increment L += 1 length -= 1 return 0 if min_length == float('inf') else min_length **Find All Duplicates in an Array Ok the big brained solution to this is that you mark the indexs you visted by making it -. And the visit goes to the index of the val. [3,2,2,4], the first index marks 4 neg. And by traversing the abs vals of the arr. res = [] for num in nums: index = abs(num) - 1 if nums[index] < 0: res.append(num + 1) else: #mark as - nums[index] = -nums[index] return res Given nums 1-n where each int appears once. Return a arr where intergers appear twice. There is the hash set solution which is O(n) time and O(n) space. dup, res = set(), [] for num in nums: if num not in dup: dup.add(num) else: res.append(num) return res Ok. Now how do we do it without a hash set? We cant sort it because it uses O(n) can we use the XOR operation? Everythime its 0, we append the res? res = [] for num in nums: Nope. The XOR method seems to only work for one repeat val due to the cummalitive property. --Design Graph-- Example of the list: { 1: {2, 3}, 2: {4}, 3: {4}, 4: {1} } Keep in mind whn we are doing if src not in self.adjList or dst not in self.adjList, we are looking at the keys not the vals of the keys. class Graph: def __init__(self) self.adjList = {} def addEdge(self, src, dst): if src not in self.adjList: self.adjList[src] = set() if dst not in self.adjList: self.adjList[dst] = set() self.adjList[src].add(dst) def removeEdge(self, src, dst): if src not in self.adjList or dst not in self.adjList: return False self.adjList[src].remove(dst) return True def hasPath(self, src, dst): #this is just DFS no? visited = set() return self._dfs(src, dst, visited) def _dfs(self, src, dst, visited): if src == dst: return True visited.add(src) for neighbor in self.adjList.get(src, []): if neighbor not in visited: if self._dfs(neightbor, dst, visited): return True return False **Single Number I completely forgot about XOR operations. What you do is set res = 0, and for num in nums, res ^= num. [4,1,2,1,2] res ^= 4 = 0 ^= 4 = 4 4 ^= 1 = 0 Ok, XOR happens at the binary level. Some useful proofs are: A number XORed with itself = 0. A number XORed with 0 is the number itself. XOR is commulative and associative. This means that the order of XOR operations dont matter. DFS(node, target, adjList, visited): if not node: return 0 if node.val == target: return 1 count += 1 visited.add(node) for neighbor in adjList[node]: count += dfs(node, target, adjList, visited) visted.remove(node) return count def BFS(node, adjList, target): visited = set() visited.add(node) queue = deque() queue.add(node) length = 0 while queue: for _ in range(length(queue)): cur = queue.popleft() if cur.val == target: return length for neighbor in adjList[cur]: if neighbor not in visited: visited.append(neighbor) queue.add(neighbor) length += 1 return length //Apr 4 2024 **Clone Graph It seems to me that if you want to make a deep copy of a graph given an reference node + adjacency list you want to do a BFS traversal. And if the new node is not copied, copy it to the new graph. BFT works best because it ensures that we connect every edge to every node, where we would have to manually backtrack for DFS. Given that you written BFS earlier, what is the major diff here I'm thinking. 1) You have to make new nodes and copy the vals of each --DFS, BFS practice --- Practicing traversals using adjacency lists. To initalize, you want a source and destination. class GraphNode: def __init__(self, val): self.val = val self.neighbors = [] You could also use a hashmap: adList = {'a':[], 'b':[]}. Example, given edges: edges = [["A", "B"], ["B", "C"], ["B", "E"], ["C", "E"], ["E", "D"]] build and adList: for src, dst in edges: if src not in adList: adList[src] = [] if dst not in adList: adList[dst] = [] adjList[src].append(dst) DFS to count paths to a target using back tracking: visit = () def dfs(node, target, adList, visit): if node in visit: return 0 if node == target: return 1 count = 0 vist.add(node) for neighbors in adList[node]: conut += dfs(node, target, adList, visit) vist.remove(node) return count BFS to find shortest path to target: def BFS(node, target, adjList): length = 0 visit = set() visit.add(node) queue = deque() queue.append(node) while queue: for i in range(len(queue)): cur = queue.popleft() if cur == target: return length for neighbors in adjList[cur]: if neighbot not in vist: vist.add(neighbor) queue.append(neighbor) length +=1 return length Try again: adList = {'a':[], 'b':[]} cur = 'a':[] def BFS(node, target, adjList): queue = deque() queue.add(node) visit = set() visit.add(node) length = 0 while queue: for i in range(len(queue)) cur = queue.popleft() if cur.val == target: return length for neighbor in adjList[cur]: if neighbor not in visit: visit.add(neighbor) queue.append(neighbor) length += 1 return length **Unique Number of Occurrences Given a arr of int. Return true if # of occurrences of each val is unique. Create a hash map: key = num -> val = # of num occurence. Loop through the vals, add to set, if in set, return False, else return True. numCount, occurance = {}, set() for num in range(len(arr)): if num not in numCount: numCount[num] = 1 else: numCount[num] += 1 for val in numCount.values(): if in occurance: return False else: occurance.add(val) return True **Max Consecutive Ones III You are able to flip k bits. Find the total number of consq ones you can make. Q: where would the prefix sum be useful here? You do prefix sum. You have to make sure that index R - L + k == sum(r) - sum(l). You keep a running total of the max (R - L + k). 0,1,1,0,1 0,1,2,2,3 1st lets create a prefix sum. prefixSum = nums[1] for i in range(1, len(nums)): prefixSum.append(num[i-1] + prefixSum[-1]) L, R = 0, 1 R you move by default. You only move L if you cannot create a consecutive one. You cant do L += 1 since it will be O(n^2). Can you move L -> R? [1,1,1,0,0,0,1,1,1,1,0] l r Had to search to to move l pointer to shrink the window in this sliding window q. We have to move l += 1 i think. And we don't have to calculate the sum of in between L <-> R @ O(n) time each time. So in total the time complexity is O(N). If condition meet, r += 1, else while condition not meet l += 1. Track largestConsecutive. while R < len(nums): if R - L < prefixSum[R] - prefixSum[L] + k: largestConsecutive = max(largestConsecutive, prefixSum[R] - prefixSum[L] + k) R += 1 else: L += 1 return largestConsecutive Ok. Remeber, we only use prefix sum when we need to calculate the sum of elems in a range. We're not doing that here. onesUsed = k while R < len(nums): if nums[R] == 0: oneUsed -= 1 if oneUsed == 0: #shrink window R += 1 Ok, you need to practice your boiler plate code for sliding window problems: There are two types of sliding windows 1) fixed size: for r in range(len(nums)): if r - l + 1 > k: window.remove(nums[L]) L += 1 else nums[R] in window: return True window.add(nums[R]) return False And then, there is var size: for R in range(len(nums)): total += nums[R] while total >= target: length = min(R-L+1, length) total -= nums[L] L += 1 return 0 if length == float('inf') else length So this is a sliding window problem. How would you solve it? L, total = 0, 0 length = -float('inf') for R in range(len(nums)): total += nums[R] while length < total + k: #how do we shrink the window? while sums not consecutive. total += nums[R]. while total + k > R - L: length = max(R - L + 1, length) length -= nums[L] L += 1 L, total, length = 0, 0, 0 for R in range(len(nums)): total += nums[R] while R - L + 1 > total + k: total -= nums[L] L += 1 length = max(R - L + 1, length) return length **Delete the Middle Node of a Linked List Have a f and s pointer. Where f moves 2x s. delete @ s once f reaches end. For the base case of n = 1, delete first node. s = f = head if not s.next: return None if not s.next.next: return head.next while f and f.next: s, f = s.next, f.next.next return head Proper solution: Handle 0 or 1 case: if not head or not head.next: return None if not head.next.next: head.next = None return Head s = f = head while f and f.next s, f = s.next, f.next.next s.next = s.next.next return head 1 3 4 7 1 2 6 s f You have to stop at s.prev prev = s.next if not head or not head.next: return None s = f = head prev = None while f and f.next: prev, s, f = s, s.next, f.next.next prev.next = slow.next return head //Apr 3 2024 **Longest Common Prefix Sort. The prefix starts out as the shortest val. For each elem in inputs, compare to prefix. If val !=, reduce prefix size. Return prefix size or ''. We don't have to have a case for that. strs.sorted() pre = strs[0] reduce = 0 for i in range(len(strs)): for j in range(len(pre - reduce)): if pre[j] != strs[j]: reduce += 1 return pre[:j] Corrected code: return '' if not strs strs.sort() pre, red = strs[0], 0 for i in range(1, len(strs)): for j in range(len( **Implement strStr() Learning about the KMP algo: The naive approach restarts the comparsion from next char of text everytime there is a mis match (this the m*n runtime). You want to build a prefix table (LPS Array). This also stands for longest proper prefix. You build it by setting an empty lsp == len of needle. Example for Prefix Table: Pattern: "ABCDABD" LPS Array: [0, 0, 0, 0, 1, 2, 0] if set(needle) in set(haystack) return indexof(needle[0]). The problem with the set solution is that we do not perserve the order of the elems. We'll use two pointers. L, R. Loop through with L. If left == first index of needle, save, the index. Then while needle, iterate through both needle and haystack. If same, return index, else, index -1, set L = R. for i in range(len(haystack)): if haystack[i] == needle[0]: index = i for j in len(needle): if haystack[j] != needle[j]: i, index = j, -1 break return index if not needle: return 0 for i in range(len(haystack) - len(needle) + 1): #we do this because we do not need to iterate through the entire len of the haystack if the elem left is < than len needle if not needle: return 0 for i in range(len(haystack) - len(needle) + 1): if haystack[i] == needle[0]: match = True for j in range(1, len(needle)): if haystack[i + j] != needle[j]: match = False break if match: return i return -1 This code looks kind of messy. But its O(n) time and O(1) space. There is actually an algo that we could use called the KMP algo that: 1) You create a prefix table for the needle. This stores the len of the longest proper prefix for each prefix of the needle. **Rewrite of Rotten oranges R, C = len(grid), len(grid[0]) rotten = deque() oranges += 1 dir = [[1,0],[-1,0],[0,1],[0,-1]] for r in R: for c in C: if grid[r][c] == 2: rotten.append(r,c) if grid[r][c] == 1: oranges += 1 while rotten: for nr, nc in dir: if not (0<= nr < R or 0<= nc < C) or grid[nr][nc] == 0 or grid[nr][nc] == 2: continue grid[nr][nc] == 2 rotten.append(nr,nc) oranges -= 1 if rotten: time += 1 return time if oranges == 0 else -1 The cracked version using python list comprehension: R, C, time //Apr 2 2024 **Rotton Oranges You want to define R and C. Then you want to create a queue using deque(). The rotton oranges get popped. You also have to iterate through the entire grid to count the total number of oranges. If you hit a time where no oranges get rotten and there is more less rotten than total oranges, return -1, else return time. R, C = len(grid)-1, len(grid[0])-1 rotten = deque() oranges = 0 for r in range(R): for c in range(C): if grid[r][c] == 2: rotten.append((r,c), 0) elif grid[r][c] == 1 fresh += 1 #Q: do we even need: if fresh_oranges == 0: return 0 dir = [[0, 1], [0, -1], [1, 0], [-1, 0]] while rotten: r, c = rotten.popleft() for dr, dc in dir: nr, nc = r + dr, c + dc if not (0<= nr < R and 0 <= nc < C): continue if grid[nr][nc] == 0 or grid[nr][nc] == 2: continue grid[nr][nc] = 2 oranges -= 1 queue.append((nr,nc)) if queue: time += 1 return time if oranges == 0 else -1 //Apr 1 2024 **Rotton Oranges For rotten oranges, we use a queue. Since we're counting the amount of time it takes for all the oranges to rot. **Add Binary Covert two strings into int, add, and convert to binary again. How do convert to int? Loop from the back, first val += 2^(i + 2). Do the same for other int. val1 + val2. To convert to binary: val1, val2 = 0, 0 for i in range(len(a))-1, -1,-1): val1 += 2 ^ (i + 1) How to turn into binary? Gave up on this. while num > 0: r = num % 2 bin = str(r) + bin n // = 2 Do the loop again. Full code: val1, val2, bin = 0, 0, '' for i in range(len(a))-1, -1,-1): val1 += 2 ^ (i + 1) for i in range(len(b))-1, -1,-1): val2 += 2 ^ (i + 1) num = val1 + num2 while num > 0: r = num % 2 bin = str(r) + bin n // = 2 return bin another method = return bin(int(a,2) + int(b,2)) [2:] for i in range(len(a) -1, -1, -1): if a[i] == 1: val1 += 2 ** (i + 1) **Number of Islands To find the number of islands in a grid, you want to loop through the grid and check for 1s. We can't just count the number of ones since mutiple ones can come together to form an island. Once you reach a 1, 1) mark it as visited 2) recursivly spread to other ones. Return count. For the dfs, you have to check bounds. if not grid: return 0 R, C = len(grid)-1, len(grid[0])-1 count = 0 dfs(r,c,grid): if r < 0 or r > R or c < 0 or c > C or grid[r][c] == 0: return else: grid[r][c] = '0' dfs(r + 1, c , grid) dfs(r - 1, c , grid) dfs(r, c + 1 , grid) dfs(r, c - 1 , grid) for r in range(R): for c in range(C): if grid[r][c] == 1: count += 1 dfs(r, c, grid) return count Q: How do we shorten this code. We can use list comprehensions: class Solution: def numIslands(self, grid: List[List[str]]) -> int: def dfs(r, c): if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1': grid[r][c] = '0' list(map(dfs, (r + 1, r - 1, r, r), (c, c, c + 1, c - 1))) return sum(dfs(r, c) or 1 for r in range(len(grid)) for c in range(len(grid[0])) if grid[r][c] == '1') //Mar 31 2024 Find pivot index 1) find the max sum. Then keep a prefix sum of the left sum. And when sum - left sum = left sum, return index, else return false if reached end of the loop. One thing that you messed up it the bounds. If you ls to be at the bottom before the compare. And ls = total sum - left sum - n. Why the -n? Review of diagonal traverse: Notice how that sum of every diagnoal row index is the same [0], [1,0],[0,1]. So we can add these to a hash map where the key is the sum of the index. We create this map using a O(n)^2 traversal looping with i and j. This way we have all the coordinates of the diagnoal traversal mapped out. Notice that the traversal occurs in alternating directions. We can append diagnal row and diagnal row reversed if % 2 != 0. Now loop through apended index elem and return res. Spiral Matrix: For this question you have to figure out a method to 1) shrink the top, left, right, bottom bounds 2) change traversal directions. Todo: Number of Islands Todo: Rotting Oranges //Mar 29 2024 **Pascal's Triangle Solved //Mar 28 2024 **Pascal's Triangle [1] a) 0 [1,1] b) 1 [1,2,1] 2 [1,3,3,1] 3 [1,4,6,4,1] 4 You're doing a len2 scan from l -> r. edges are always 1. Edge case a) b). Rest follows the two scan patt. **Spiral Matrix Q: How do you determine directions: right, down, left, up Instead of subtracting row, and col, you can make sure top < bottom and left < right: top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1 res = [] while top <= bottom and left <= right: #move right while j <= right: res.append(matrix[i][j]) j += 1 top += 1 i += 1 j -= 1 You define r, c = len(matrix), len(matrix[0]). Q: How do you do CW turns? [0,0], [1,0], [2,0] | [1,2], [2,2] | [2,1], [2,0] | [1,0] | [1,1] 0 1 2 3 4 3 2 1 2 -> Sum [0,0], [1,0], [2,0] [1,2], [2,2] [2,1], [2,0] [1,0] [1,1] We go from increase to decrease in len. There does not seem to be and clever math/indices trick to figure out like the diagonal traverse. Brute force. Iterate i -> till R. Turn down. Iterate j till C. Turn Left row, col, i, j, n, res = len(matrix) - 1, len(matrix[0]) - 1, 0, 0, 0, [] while row > 0 or col > 0: if i == 0: #traverse left for i in range(col): res.append(matrix[i][j]) n+=1 elif i == col: #traverse down for j in range(n, row): res.append(matrix[i][j]) elif j == row: #traverse left for i in range(col - n, -1, -1): res.append(matrix[i][j] else: #traverse up for j in range(row - n -1, -1, -1): res.append(matrix[i][j] return res [-,-,-] [|,-,|] [-,-,|] row = 3, 2 col = 3, Ok, it seems like you mesed up the cases for spiraling inwards. You want to set a top, bottom, left, right var. After each right top +1, move down right -1 since you're iterating from the back, move left bottom -=1, move up, l+=1 **Diagonal Traverse d = {} for i in range(len(matrix)): for j in range(len(matrix[i])): if i + j not in d: d[i + j] = [matrix[i][j]] else: d[i + j].append(matrix[i][j]) This builds the dict. The problem is 70% solved. Now you just have to figure out a method to traverse it in a zig zag pattern. You iterate through d[i+j] and if index % 2 == 0 down up, else go up down. Append to res. for key, val in d.items(): if key % 2 != 0: res.append(val) else: res.append(reversed(val)) I gave up and refered to GPT. The trick here is to sum i + j. The key big brained insight is that the elements on the same diagonal has the same i + j sum. Q: How does this help us? Well you could just do sum of diagnal - i to find j. Try mapping out [i,j] = [0,0] | [1,0], [0,1] | [0,2], [1,1], [2,0] | [2,1], [1,2] | [2,2] Try to find the pattern of the [i,j] mapping. [0,0] [1,0], [0,1] [0,2], [1,1], [2,0] [2,1], [1,2] [2,2] | [0,0] | | [1,0], [0,1] | | [2,0], [1,1], [0,2] | | [3,0], [2,1], [1,2], [0,3] | | [4,0], [3,1], [2,2], [1,3], [0,4] | -------------------------------------- Lets splits things up between increase and decrease | [4,1], [3,2], [2,3], [1,4] | | [4,2], [3,3], [2,4] | | [4,3], [3,4] | | [4,4] | R1 i start @ 0. As R += 1, i += 1. For each row, i -= 1. Once longest R is reached. First i always longest R. i -= 1 for every row. The j col, j = j + 1 till len of row, reset = 0. Once it reaches max len, the start of j += 1 each time and j = j + 1. for i in range(len(mat)): append i number of times, append i -> 0 clear() [0] | [1] [0] | [2] [1] [0] | [3] [2] [1] [0] for j in range(len(mat)): append j number of times, append 0 -> i clear() res_i, res_j = [], [] for i, j in range(len(mat)): for _ in range(i - 1, -1, -1): res_i.append(i) for _ in range(j): res_j.append(j) What ends up happening here is that you have [i] [j] in seperate arrs. So you iterate through both at the same time and append val of the mat in res. The way I'm implementing it, we would not heave to clear. res = [] for i,j in range len(res_i): res.append(mat[res_i[i], res_j[i]]) Ok. Lets just try to solve for this pattern: [0] | [1] [0] | [2] [1] [0] | [3] [2] [1] [0] //Mar 27 2024 **Diagonal Traverse lol this question is diabolical. You know that the dir of the traversal goes from 1 -> len(arr) before going back down to 9 again. Let try to understand the problem. Quiz Q 1: What is the sum of indices (i, j) for the top right elem of any matrix? **Plus One Given int. Rep digits where digits[i] is ith digit of int. And you add one. 1st method: turn arr into in, add, return the digits in arr format val = int(for dig in digits n.join('')) Wrong syntax, the correct method: num = int(''.join(map(str, digits)) return the val + 1 to arr num = [int(dig) for dig in str(num)] Ok for this method you have to convert the return digits back to string again. Not worth is. Loop from the back. Add the last val. If the last val == 9, carry = 1, add one again. If there is a carry and you reach index 0, insert @ 0 index and shift everything back. Ok this is not the most run time optimal because of the insert at the start. Instead of inserting at the start, you could do [1] + [rest of arr] since its more run time efficent. for i in range(len(digits) - 1, -1, -1): if digits[i] < 9: digits[i] + 1 return digits digits[i] = 0 return [1] + digits **Largest Number At Least Twice of Others 1) sort it 2) check if [-1] > 2 * [-2] You have to return the index of the largest elem. You only have to store 2 hashs 1) largest val + index 2) 2nd largest val and index. Loop through the arr using enumerate. def dominantIndex(nums): l1, l2 = [float('-inf'), -1], [float('-inf'), -1] # Initialize with -1 for indices for i, n in enumerate(nums): if n > l1[0]: l2[0], l2[1] = l1[0], l1[1] l1[0], l1[1] = n, i elif n > l2[0]: l2[0], l2[1] = n, i if l1[0] >= 2 * l2[0]: return l1[1] else: return -1 More readable two pass approach: max_val = max(nums) max_index = nums.index(max_val) for i, n in enumerate nums: if i != max_index and n * 2 > max_val: return -1 return max_index One thing to note - you can find the index by simply calling nums.index(max_val) which I assume is also O(n) Linked List questions are hurting me, so I'm going to move into arrays. **Find Pivot Index prefixsumR = prefixsumL Q: what is the shortest method to write a prefix sum: ls, rs, n = nums, nums, len(nums) for i in range(1, n): ls[i] += ls[i - 1] for i in range(n - 1, -1, -1): rs[i] += rs[i + 1] if rs[i] == ls[n - i]: return nums[n - i] return -1 Ok, it seems like you overly complicated the heck out of this question. The most elegent method to solve it is to sum all the nums. Check for left sum. If left sum = total sum - left sum, return i, else return -1. sum_, ls = sum(nums), 0 for i, n enumerate(nums): return i if ls == sum - ls - n else ls += n return -1 **Flatten a Mutilevel Doubly Linked List [Incomplete] It seems like you're just putting the child list right after cur node. This is an insertion problem. Loop through the linked list. If child, insert child and everything in the child layer between cur, and the next node. We can do this iterativly or recursivly. Lets try both methods. With the iterative method: cur = head while cur: if cur.child: tmp_layer = cur.next cur = cur.child while cur.next: Q: what if there is another nested child? cur = cur.next I'm pretty sure you NEED recursion to solve this. Because there could be up to n levels no? For the iterative solution you need a 1) helper function 2) a maunal call stack to maintain. Seems pretty dumb to solve this problem this way. Recursive solution: What is the base case? If cur.next = None, return if head is None: return if head.child = None flatten(head.next) else: flatten(head.next) You have to relink to the next node @ the same level of cur before iterating through all the child though. Base case + recursive step: The true base case is when cur.next and cur.child all == None. After you find a node with a child, you want to explore it completely. Recursively call on this function on the child node. flatten(cur.child). Relinking Nodes: You want to save cur.next somehow in the call stack before traversing the child. Seems like BFS with a queue like structure? Everytime you hit a child, you want to add to queue, and everytime that the call stack is complete, you dequeue the top layer (cur.next) and continue traversing cur.next. Why is it that you don't have to check for a termination condition? I thought when solving linked lists problems recursively, you always have to return None or something if base case is hit. As for relinking nodes cur = cur.child. if cur is None: return None OK, I had to cheat for this portion. As I've guessed, you have a temp storage for cur.next. You need that to relink everything after you've traversed through all of the child nodes one layer down. Then you call flatten(cur.child). Ok the one thing I didn't think of is that you need to find the last child - that is the one you have to link back up with the higher level. The process of relinking the nodes are 1) lastchild.next = tmp, tmp.prev = lastchild. That is if tmp though. I'm still a little confused even when given the code. So lets walk through the DFS step by step. lastChildNode = cur.child while lastChildNode.next: lastChildNode = lastChildNode.next With this, you're iterating till you find the last child node in a level. This is how you know where to link the end of the child to the start of the top level. lastChildNode.next = next_temp if next_temp: next_temp.prev = lastChildNode This simply relinks the child level with the parent level. **Add Two Numbers (Iterative) Ok so it turns out that I did not need to reverse the nodes. Correct code: You should initialize a dummy node. set cur as dummy so you can iterate over it. Also, you forgot to iterate prev1 and prev 2. Other than that its correct and you just return dummy.next. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode: c1, c2, prev1, prev2 = l1, l2, None, None while c1: c1.next, prev1, c1 = prev1, c1, c1.next while c2: c2.next, prev2, c2 = prev2, c2, c2.next dummy = ListNode(0) cur = dummy carry = 0 while prev1 or prev2 or carry: val1 = prev1.val if prev1 else 0 val2 = prev2.val if prev2 else 0 total = val1 + val2 + carry carry = total // 10 cur.next = ListNode(total % 10) cur = cur.next if prev1: prev1 = prev1.next if prev2: prev2 = prev2.next return dummy.next Draft code: c1, c2, prev1, prev2 = l1, l2, None, None while c1: c1.next, prev1, c1 = prev1, c1, c1.next while c2: c2.next, prev2, c2 = prev2, c2, c2.next carry = 0 while prev1 or prev2: val1 = prev1.val if prev1 else 0 val2 = prev2.val if prev2 else 0 sum = val1 + val2 + carry carry = sum // 10 val = sum % 10 cur = ListNode(val) cur = cur.next //Mar 26 2024 **Add Two Numbers (Iterative) The tricky thing about the iterative solution is that you have to look from R -> L and its a singly linked list. Is there a way to solve it in O(n) time and O(1) space. Is there a way to solve this problem without having to reverse the linked list? 1) Reverse the linked Lists prev1, prev2, c1, c2 = None, None, l1.head, l2.head while l1 or l2: c1.next, c2 = prev1, prev2 prev1, prev2 = c1, c2 c1, c2 = c1.next, c2.next The problem with this code is that it does not handle the edge cases where the lists are shorter. The proper method is: c1, c2, prev1, prev2 = l1, l2, None, None while c1 or c2: if c1: c1.next, prev1, c1 = prev1, c1, c1.next elif c2: c2.next, prev2, c2 = prev2, c2, c2.next elif not c1 and c2: c1.val, c1 = 0, c1.next else: c2.val, c1 = 0, c2.next Ok, we'll handle the edge cases during the addition phase where sum = val1 + val2 + carry. c1, c2, prev1, prev2 = l1, l2, None, None while c1: c1.next, prev1, c1 = prev1, c1, c1.next while c2: c2.next, prev2, c2 = prev2, c2, c2.next 1) calculate sum 2) calculate carry 3) create and link new node from val 4) reverse nodes while c1 or c2: **Add Two Numbers (Recursive) According to GPT, you need: def addTwoNumbers(l1, l2, carry=0): The base case is if carry == 0 and not l1 and not l2. Then you return. To handle the cases of if there is a val for diff len of linked lists, if l1 = 0 or if l2 = 0. val1 = l1.val if l1 else 0 same with val2 sum = val1 + val2 carry = sum // 10 cur_val = sum % 10 cur_node = ListNode(cur.val) recursive case: next1 = l1.next if l1 else None same w/ next2 cur_node.next = addTwoNumbers(nex1, next2, carry) This questions suits recursion pretty well. The base case is if l1 and l2 = None. The recursive case, you want to pas l1, l2 and carry. if l1.val + l2.val > 10: addTwoNumbers(l1.val + l2.val - 10 ,1) #(sum, carry) else: addTwoNumbers(l1.val + l2.val, 0) Ok. What do yo make equal to addTwoNumbers? cur.next = addTwoNumbers? How do you handle the carry from a previous recursion? The trivial solution is wrong - you did not read the questions properly- you're doing addition. The algo for the carry: either 1 or 0. num1 + num2, if > 10, -10 and carry = 1, else carry = 0. Since I'm lazy, I'm going to convert array to int, add, and convert to list again. arr1, arr2 = [], [] while l1 or l2: if l1: arr1.append(l1.val) l1 = l1.next if l2: arr2.append(l2.val) l2 = l2.next num1 = int("".join(str(n) for n in arr1)) num2 = int("".join(str(n) for n in arr2)) res = num1 + num2 return [int(digit) for digit in str(num)] The return expects a linked list, so just build one and return that Trivial Solution arr1, arr2 = [], [] while l1 or l2: if l1: arr1.append(l1.val) l1 = l1.next if l2: arr2.append(l2.val) l2 = l2.next res = [0] * len(arr1) for i in range(len(arr1)-1, -1 ,-1): res[-i-1] = arr1[i] + arr2[i] return res Ok. Did not read the problem correctly. There is a carry term. **Merge Two Sorted Lists Ok, lets try to use recursion to solve this. What is the base case? If not l1 or l2. What is the minimizing case? if l1 smaller, l2 = mergeTwoList(l1.next), else l1 = mergeTwoList(l2.next). if l2 = None: return l1 if l1 = None: return l2 if l1.val < l2.val: l2 = mergeTowLists(l1.next) else: l1 = mergeTwoLists(l2.next) First step is to create a dummy prehead node. Q: why is that helpful? This way we don't have to deal with the edge cases of 0 or 1 node in l1 or l2. The condition to decide whether the node from l1 or l2 should be attached to cur node is which is smaller. Compare l1.val to l2.val. Append the smaller one. cur.next = l1, l1 = l1.next. cur = cur.next to iterate. Once all the nodes are attached, you have two cases, where l1 = None or l2 = None. Take the one that is not None, and cur = l2/l1.next. Return head. dummy = newNode(None, next = head) cur = dummy while l1 and l2: if l1.val < l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next if l1 is not None: cur.next = l1 if l2 is not None: cur.next = l2 return dummy.next The case that you missed is that you also have to return l1 and return l2 inside the case of l1.val <> l2.val. Why is that //Mar 25 2024 **Merge Two Sorted Lists I remeber that there was a way to do it recursively and iterivly. Lets try solving it with a while loop first. while l1 and l2, if l1 smaller, add that first, else add l2. when adding the flow looks something like (when comparing next vals). **Palindrome Linked List Q: How do we do it in O(n) time and O(1) space? It seems like we would have to move 2 pointers at different speeds. The tricky part here is that its a uni-directional linked list. 1 -> 2 -> 3 -> 3 -> 2 -> 1 So using the fast and slow pointers you can find the midpoint. The tricky thing is how we do the comparisions. 1) you cant have a set, hash, or any other external storage 2) you can't create prev pointer (counts as extra storage) But you can reverse the linked list before the midpoint. Recall reversing a linked list: cur.next = prev prev = cur cur = cur.next count, cur, cur2, prev, f = 0, head, head, None, head while f and f.next: count += 1 cur = cur.next f = f.next.next for _ in range(count//2): cur2.next = prev prev = cur2 cur2 = cur.next for _ in range(count//2): if cur2.val != cur.val: return False cur, cur2 = cur.next, cur2.next return True Few things to observe 1) Count is not needed. 2) You didn't handle the case of if not head or head.next. if not head or not head.next: return True s = f = head prev = None while f and f.next: f, s.next, prev, s = f.next.next, prev, s, s.next if f: s = s.next while prev and s: if prev.val != slow.val: return False prev, s = prev.next, s.next return True The most trivial method to do this is to traverse through the linked list and append each elem onto an array. Then you perform is Palindrome on the arry. for i in range(len(arr) // 2) and for j in range(len(arr)//2) is the same. res, cur = [], head while cur: res.append(cur.val) cur = cur.next for i in range(len(res)//2): if res[i] != res[-i-1]: return False return True **Odd Even Linked List You offset odd and even. Store where even started. Iterate while even and even.next. The key is you are not just iterating through via .next.next but rather you have to update the nodes with odd.next = odd.next.next, then move odd. Ok, my main mistake is the fact that I traversed the linked list twice. No need for that. First and foremost, if there is no head, I should return None - that is the edge case. Set odd = head and even to be one offset. while there is even and even.next (since thats the longest node). Holy smokes, the idea of setting an evenHead is pretty smart. evenHead = even. Store all the odd vals and even vals. Then combine the linked list. cur, odd = even = head e, o = 0, 0 while odd.next: odd = odd.next.next o += 1 while even.next: even = even.next.next e += 1 for _ in range(e+o): cur = odd.next if odd.next == None: cur = even.next return cur Ok, you can't do odd.next.next. You have to start them offset by eachother. **Remove Linked List Elements Loop through the linked list. If val cur.val == val remove. Keep going till head == null. You can look to see if cur.next.val == val. Since this is a singly linked list. we only really have to move one pointer. cur.next = cur.next.next. We don't have to worry about two pointers. cur = head while cur.next: if cur.next.val == val: cur.next = cur.next.next cur = cur.next return head Q1: My code would return 1 -> 2 -> 6 -> 4 -> 5 -> None? Q2: For Q2 you can check and modify the head pointer before the while loop, or easier yet, use a tmp dummy node For the edge cases of these linked list, its good to have a dummy node: dummy = ListNode(next=head) cur = dummy while cur.next: if cur.next.val == val: cur.next = cur.next.next else: cur = cur.next return dummy.next //Mar 24 2024 **Reverse a linked while loop. You have a tmp store. tmp = cur.next cur.next = cur.prev cur.prev = cur.next cur = tmp The elegent way to implement is cur, prev = head, None while there is a cur, cur.next = prev, prev = cur, cur = cur.next. So what you wrote above was wrong. **Intersection of Two LinkedLists Most elegent version of the solution does not require counting. If any of the list elems are empty, return None. You set a and b to their respective heads. while a != b, you keep looping. a = a.next if a else headB b = b.next if b else headA Followup: write solution that is O(m+n) time and O(1) mem. So I cheated a bit and looked at the solution for O(1) space. You calculate the len of both arr and offset the len of the longer one by starting at len(long) - len(short). a, b, len_a, len_b = headA, headB, 0, 0 while a: a = a.next len_a += 1 while b: b = b.next len_b += 1 if len_a > len_b: diff = len_a - len_b for _ in range(diff): a = a.next while a and b: a, b = a.next, b.next if a == b: return a class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: a, b = headA, headB len_a, len_b = 0, 0 # Calculate the length of list A while a: len_a += 1 a = a.next # Calculate the length of list B while b: len_b += 1 b = b.next # Reset pointers to the start of each list a, b = headA, headB # Adjust the starting point for the longer list if len_a > len_b: for _ in range(len_a - len_b): a = a.next else: for _ in range(len_b - len_a): b = b.next # Find the intersection while a != b: a = a.next b = b.next # Either both are None (no intersection) or both are at the intersection point return a Can we not store the vals of a1 and b1 in a hash? If val in hash, return. a = headA b = headB a_list = set() while a.next: a_list.add(a) a = a.next while b.next: if b in a_list: return b b = b.next return None Corrected code: class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: a_nodes = set() # Traverse the first list and add all nodes to the set a = headA while a: a_nodes.add(a) a = a.next # Traverse the second list and check each node against the set b = headB while b: if b in a_nodes: return b # Intersection found b = b.next return None # No intersection **Linked List Cyle II Shortened version according to GPT. Cycle detection is still the same. The diff starts to happen while you're in the outer loop. if s == f. while head != s, you move head. s = f = head while f and f.next: s, f = s.next, f.next.next Code: s = f = head while f and f.next: f, s = f.next.next, s.next if s == f: break cycle, ptr = 1, ptr.next while ptr != s: ptr = ptr.next cycle += 1 ptr1 = ptr2 = head for _ in range(cycle-1): ptr1, ptr2 = ptr1.next, ptr2.next return ptr1 peudo code I: step 1 c1, c2 = 0, -1 s = f = head while f and f.next: f = f.next.next s = s.next c1 += 1 if f == s: break #observation, we don't even have to track c1 here step 2 ptr = s.next while ptr != s: ptr = ptr.next c2 += 1 step 3 ptr1 = ptr2 = head while c2 >= 0: ptr2 = ptr2.next c2 -= 1 res = 0 while ptr1 != ptr2: ptr1 = ptr1.next ptr2 = ptr2.next res += 1 return res The first thing we want to establish is that f can cross s at an 'arbitrary' location dependent on 1) where the cycle starts 2) the size of the cycle (number of nodes). This means if we can find 2) the size of the cycle, we can reverse engineer to where the cycle starts based on where they cross. Step 1: To solve this, there is a couple of questions we have to answer 1) To detect if there is a cycle, we start both s and f at head, moving f 2x as fast as s. If s == f, there is a cycle. Step 2: To determine the size of the cycle you take the point where s == f. And s = s.next, fast = fast.next.next. Doing it with a cycle len of 4, (1,2,3,4 nodes) it seems like s moves 2x the length of the list before f catches up. So would the equation just be count s moved since s==f // 2? step 3: You just do count s==f location - size of cycle? Ok for step 2, you can just keep looping f till s == fast again and track the count. Ok, now the giga brain move is set up another ptr1 and ptr2. You move ptr1 by len of cycle at a time. ptr2 1 step at a time? ' You initalize ptr1 to be n steps ahead and iterate 1 @ a time. Q: why does this work? Since you know that one point is exactly n len further ahead, you know that pt1 will == pt2 in which its the start of the linked list. Just to clearify for step 2 you start @ s == f, and you only iterate 1 ptr till you hit s==f again. And you simply count the number of increments? Its the same as normal cycle detection, but you simply add an index counter no? There is the base case: if not head or not head.next: return -1 f = s = head p = 0 while f and fast.next: p += 1 f = fast.next.next s = slow.next if f == s: return p return -1 This does not work because the point in which f and s meet does not mean its where the cycle starts Read into Two Pointer in LinkedList: To determine if cycle, you can use hash table or f and s pointer. Q: How would you do cycle detection and find the start of a cycle? **Linked List Cycle Pretty much, you move fast twice fast as slow. If fast == slow, return true, else return false. Q: what is the while condition? While fast.next.next and slow.next. **Design Linked List def deleteAtIndex(self, index): if index == 0: self.head = self.head.next self.size -= 1 elif index == self.size: self.tail = self.tail.prev self.size -= 1 elif index > size: return -1 else: cur = self.head while cur.next and index < size: cur = cur.next index -= 1 cur.next.prev = cur.prev cur.prev.next = cur.next Lets compare how my code is diff from GPTs. If index < 0 or index >= self.size return -1. Valid, this is a more general case. If index == 0, self.head = self.head.next. If self.head you also have to remove the tail that pointed back to the prev head. The other case is if there is no more head, then you set self.tail = None. If its at the end, there are two cases as well. -> wait no the other case where the list = empty just activates the condition above to remove head. self.tail = self.tail.prev, self.tail.next = None. You dont have to do while cur.next since its already managed by index. The key is that you do cur.prev.next = cur.next before cur.next.prev = cur.prev. The correct code: def deleteAtIndex(self, index): if index < 0 or index >= self.size: return -1 elif index == 0: self.head = self.head.next if self.head: self.head.prev = None else: self.tail = None elif index == self.size - 1: self.tail = self.tail.prev self.tail.next = None else: cur = self.head while index > 0: cur = cur.next index -= 1 cur.prev.next = cur.next cur.next.prev = cur.prev self.size -= 1 return 0 //Mar 22 2024 **Design Linked List Ok, lets first make a class called ListNode which should contain the def for node, and node val. I forgot the def. But I think you need something along the lines of 1) new node 2) node vals: class ListNode: def __init__(self, val): self.val = val self.prev = None self.next = None For the above, its the inital initialization. For the MyLinkedList class, you want to define that the self.left. For the def of myLinkedList, it can vary a lot by if its a singly, or doublely linked list. Generally, for the node class you want to declare the val, prev and next. For the init for the MyLinkedList you would want to set the head, tail vals. One intresting thing you can also add is the size of the linked list. For example, if you constantly need to know the length of the list, instead of having to iterate through the list at O(n) time, you can look at the size attribute which is O(1). class MyListNode: def __init__(self): self.head = None self.tail = None self.size = 0 Ok, now for the def of add at head. There are two possible scenarios 1) its an empty linked list 2) its not a empty list. 1) If list, head = ListNode(val), tail = head, size = 1 2) Else head.prev = ListNode(val), head = head.prev, size += 1 def addAtHead(self, val): if not head: head = ListNode(val) tail = head size = 1 else: tmp = head head.prev = ListNode(val) head = head.prev head.next = tmp size += 1 There is a few issues with how I wrote addAtHead. I mainly forgot to had self. Ok self = making changes to instance in python class. if not self.head: self.head = ListNode(val) self.tail = self.head self.size = 1 else: tmp = self.head self.head = ListNode(val) self.head.next = tmp tmp.prev = self.head self.size += 1 What I fogot was to make tmp.prev = self.head. I feel like there is a better name for tmp. maybe old_head. Try to shorten: self.head = ListNode(val) if not self.head else (self.head.prev = ListNode(val, self.head, None) For the case of adding at tail, similar to adding at head, there are two cases: 1) adding tail to an empty arr 2) adding tail to an non empty arr. Question: how to add to the tail of an arr? def addAtTail(self, val): if not self.tail: self.head = ListNode(val) self.tail = self.head self.size = 1 else: self.tail.next = ListNode(val) self.tail.next.prev = self.tail self.tail = self.tail.next self.size += 1 Another way to write the else case of addaAtHead: else: self.head.prev = ListNode(val) self.head.prev.next = self.head self.head = self.head.prev self.size += 1 val <-> 1 <-> 2 <-> 3 ^ h def get(self, index): if index > self.size or index < 0: return -1 cur = self.head while index > 0: cur = cur.next index -= 1 return cur.val def addAtIndex(self, index, val): if index > self.size or index < 0: return -1 elif index == size: addAtTail(val) elif index == 0: addAtHead(val) else: new_node = ListNode(val) cur = self.head while index > 0: cur = cur.next index -= 1 new_node.next = cur.next new_node.prev = cur cur.next.prev = new_node cur.next = new_node self.size += 1 def deleteAtIndex There are 4 links that you have to break. //Mar 21 2024 Started studying recursion **Reverse String Base case. When the string is empty, return res. Else keep returning reverseString(s[-1]) if not s: return res res.append(reverseString(s[-1)]) The problem is that you have to declare res outside. And you need to create a helper function. 2nd try res = [] def helper(s): if not s: return res helper(s.pop()) The problem with this helper code is that its simplying the index I want to remove. The solution that takes advantage of the call stack uses the following approach: The base case is if the index reaches len(s) // 2. That means you made every swap possible from the l and r side. The recursive case is s[i], s[-i-1] = s[-i-1], s[i]. Then you simply call the function iterating index + 1 def reverseString(s, i=0): if i >= len(s) // 2: return s[i], s[-i-1] = s[-i-1], s[i] reverseString(s, i+1) **Squares of a Sorted Array We are not allowed to 1) sort 2) square the elem. Take everything < 0, abs val it. reverse. nums1. nums2 = other half. loop through nums1 and nums2. Append to res in that order. nums1, res = [], [] i = 0 while nums[i] < 0: nums1.append(nums[i] i += 1 nums1 = reversed(nums1) k = 0 for j in range(i, len(nums)): while num[j] > nums1[k]: res.append(nums1[k]) k+=1 res.append(nums[j] return res Clean up mistakes: def sortedSquares(nums): nums1, res = [], [] i = 0 while i < len(nums) and nums[i] < 0: nums1.append(abs(nums[i])**2) i += 1 nums1 = list(reversed(nums1)) k = 0 for j in range(i, len(nums)): while k < len(nums1) and nums1[k] < nums[j]**2: res.append(nums1[k]) k += 1 res.append(nums[j]**2) while k < len(nums1): res.append(nums1[k]) k += 1 return res **Find All Numbers Disappeared in an Array There is a few edge cases to consider 1) if the skip num is at the start 2) if the skip num is at the end, 3) if there are repeats (not really a edge case to worry about). The question is if we can do it in O(n) time. Lets try the leetcode cheat sheet: https://leetcode.com/explore/interview/card/cheatsheets/720/resources/4725/ Arr is not sorted and its asking to find specific elems. The solution therefore uses a hashmap. Remeber you can only do O(n), but that does not mean you have to do only one pass. Q: Does 1-n include numbers bigger than n in the input? Assume no. Find len(nums). Turn that into a set. Loop through nums. If not in set, append to solution. arr, res = set(), [] for i in range(len(nums)): arr.add(i) for num in nums: if num not in arr: res.append(num) return res Ok that was pretty poo poo brained of you. You make nums a set, and check if its not in arr! n = len(nums) nums = set(nums) res = [] for i in range(n): if i not in nums: res.append(i) return res Problem: You have to one index the arr. We fixed that by simply doing n+1 and not appending the 0th i elem. //Mar 20 2024 **Third Maximum Number O(n) solution means that we would not be able to sort. What if you maintain a res arr. For example res = [3rd largest, 2nd largest, largest]. Also we do not need a set. for num in nums: if num > 3rd < 2nd, replace 3rd if nums > all, replace largest if nums > 2nd < largest, replace 3rd. Else do nothing res = [float('-inf')] * 3 for num in nums: if num > res[0] and num < res[2]: res[0] = num elif num > res[1] and num < res[2]: res[1] = num elif num > res[2]: res[2] = num if len(res) >= 3: return res[0] else: return res[-1] The problem we face with this solution is that when comparing num < res[2] to neg inf, its always true. Therefore, you have to swap. Lets convience ourselves with an example: With [3,2,1], you get a res of [3, inf, inf]. Therefore you have to perform a swap everytime you add. Shift everything to the right in the new arr: res[0], res[1], res[2] = num, res[0], res[1] //Mar 19 2024 **Move Zeros You have a read and write pointer. [0,1,0,3,12] r w If == 0, move r up and r, w = r, w, swapping the elems [1,0,0,3,12] r w Lets start with w = 0, r = 1 [0,1,0,3,12] w r If nums[w] == 0, nums[r], nums[w] = nums[r], nums[w], w += 1, r += 1 [1,0,0,3,12] w r [1,0,0,3,12] w r swap [1,0,3,0,12] -> This fails The trick is to do it swap if its not 0. And if you do the swap, increment l. **Replace Elements with Greatest Element on Right Side For these replace elem questions, you normally want to iterate from R -> L. Why? So you don't have to look foward and backtrack. The array is not sorted. for i in range(len(arr) - 1, - 1, -1). set num[-1] = -1. next val == max(cur, cur[i+1] 2nd last elem == max(cur, -1). Why not manually set arr[-2] = arr[-1], arr[-1] = -1 arr[-1] = -1 for i in range(len(arr)-2, -1, -1): arr[i] = max(arr[i+1], arr[i]) return arr Input: [17,18,5,4,6,1] Answer: [18,18,5,4,1,-1] Expected: [18,6,6,6,1,-1] Ok, you can't manually set arr[-2]. What if you just set arr[-1]? [17,18,5,4,6,-1] for i in range(len(arr) -2, -1, -1): arr[i] = max(arr[i+1], arr[i]) arr[-1] = -1 return arr It seems like they are shifting everything to the left by +1. I'm too brain dead - the new solution suggested by GPT is as follows. You set max_val = -1. And for i in range(len(arr)-1,...) tmp = cur val, set cur to max_val, and max_val is now = max(max_val, temp). Q: Just for practice, can you solve this problem via swapping? #todo **Valid Mountain Array if cur always larger than prev (increse). Second there is decrease, only allow decrease. If increase again return false. 1) while increase, always increase increase = True for i in range(1, len(arr)): if arr[i] < arr[i+1] and increase: #this is the peak of the mountain increase = False if not increase and arr[i] > arr[i+1]: return False return True Try again while a while loop i, downhill = 1, False while arr[i] > arr[i-1]: i += 1 downhill = True while arr[i] < arr[i-1]: i += 1 return i == len(arr) **Check if N and Its Double Exist It seems like you have to iterate two pointers i and j. Return true if: 1) i != j 2) i and j within arry bounds 3) the val of i == 2x that of j. Make a set. If new val, add to set. If the val you see // 2 is in set with no reminders. Return true. Else return false. dup = set() for num in arr: if num % 2 == 0 and num // 2 in dup: return True elif num not in dup: dup.add(num) return False This code breaks here because it can only make a comparison to j after its's been added. A cheecky fix is to dup = set(arr). if num%2 == 0 and num // 2 in dup, return True. It broke with the following test case: [-2,0,10,-19,4,6,-8]. This fails because 0//2 and %2 == 0. Don't add 0 to set. One way is to never all 0s to the set. res_set = {x for x in arr if x! = 0}. You also have a if case for 0 zeros. Jank as hell. Visit the proper way to do it via deletions. 1) sort the reversed(sorted(arr)). Have i, j pointer. Move j by default. Move i if arr[j] * 2 < arr[i] i+= 1. arr = reversed(sorted(arr)) while j < len(arr) - 1: if arr[j] * 2 == arr[i]: return True elif arr[j] * 2 < arr[i]: i += 1 j += 1 return False //Mar 18 2024 Count the # of zeros. Iterate backwords. This way you don't have to worry about shifting vals in the indexes. [1,0,2,3,0,4,5,0] ^ You have a zero count which is 3 in this case. You hit the case of if i + zeros < n: which it fails. arr[i] == 0, so you -= 0. zeros = 2. You also go into the case of i + zeros < n which it fails. Do nothing. [1,0,2,3,0,4,5,0] ^ zeros = 2... you keep moving left till arr[i+zeros] < len(arr). What about the case of case of zeros at the back of the index that we would not duplicate? Why are we counting those? I would assume that we would push elements out of the array. But we solve this problem by decrementing everytime we see an 0. For the array [1,2,0,3,0,4,0] ^ i + zeros = 6 + 3 = 9 > len(arr). We then hit the case of arr[i] == 0: zero -= 1. i + zeros > n. Continue loop. Merge Sorted Array The cheating way to do it is to use extra space. declare nums3 = []. Loop through nums1 and nums2. Sort it. And for every i-th elem in num you set as nums1[i]. tmp = [] for num in nums1: tmp.append(num) for num in nums2: tmp.append(num) for i, num in enumerate(sorted(tmp)): nums1[i] = num //Mar 16 2024 881 Boats to Save People For the problem you want to sort the arr. You'll most likely run into the case where there is 1 boat per person because of the limit. You want to check if people[i] and people[i+1] <= limit. If yes, we move the pointer to +2, else + 1 and we increment the number of boats by one. reversed(people.sorted()) Actually the order of the sort does not matter that much. i, boats = 0, 0 people.sort() while i < len(people) - 2 if people[i] + people[i + 1] <= limit: boats += 1 i += 2 else: boat += 1 i += 1 return boats Refined code: boats, i = 0, 0 people.sort() while i < len(people): if i + 1 < len(people) and people[i] + people[i + 1] <= limit: boats += 1 i += 2 else: boats += 1 i += 1 return boats #1,2,4,5 The code fails at the test case above. So we need two pointers L and R that converge towards the center. Recall even with the L and R pointer there is a case of += 2 boat and += 1 boat. If people [L] + people[R] < target. boats += 1, R += 1. If smaller than target boat += 2 L+= 1, R -=1 boats, L, R = 0, 0, len(people) while L < R: if people[L] + people[R] < target: boat += 2 L += 1 R -= 1 else: boat += 1 R -= 1 return boats We can simplify the expression more: if people[L] + people[R] <= limit: L += 1 R -= 1 boats +=1 return boats This way we do not have to manually handle the +1 or +2 boat cases. //Mar 6 2024 Answers: 1) The two different (parts?) of graphs are the vertices (nodes or values) and the edges (connect different nodes). 2) The most efficient way to represent a graph where the nodes are connected to a lot of other nodes is through adjacency lists. You can represent another node val by simply adding another char to the list. 3) Between DFS and BFS to find the shortest path of a unweighted graph, I would imagine you would want to use DFS. DFS, goes all the way to the end before trying again. The probability that you find a shortest path that way vs traversing slowing and equally in all directions is a lot higher sooner. 4) For depth first search you either use recursion or simulate the call stack using a stack. Iterative: stack = [first node] while stack: for every node connected to first node: stack.append(connected nodes) cur = stack.pop() do something with cur Recursive: dfs(node): if node = null: return for every node connected to first node: cur = dfs(cur) 5) Shortest path finding for a map app? Correct Answers: 1) Directed vs undirected graphs 2) Dense graphs should use [?] if its unweighted, use a 2D boolean array. Why? Complexity = O(V^2) 3) For shortest path, BFS is more useful - Why? It guarantees the first time a node is reached //Mar 7 2024 Q1: How would you iterate over each cell in the grind? A1: In a grind there are rows(r) and columns (c). To traverse through the grid, [col][row]. The ways you can move are left ([c][r-1]), right ([c][r+1]), up ([c-1][r]), down ([c+1][r]). GPT4 method to iterate: for r in range(len(gird)): for c in range(len(grid[0])): #process cell grid[r][col] Q2: Given a cell, how do you check if its land and start DFS from it? A2: Oh I think I understand where this is going. Loop through the grid at O(n^2) till you find and island (1). Then you do DFS to mark all of the 1s in that insland as visited (maybe by changing 1 -> 0). And you have some external counter var for the # of islands. To answer your Q2: if grid[r][c] == 1: dfs(grid[r + 1][c]) dfs(grid[r - 1][c]) dfs(grid[r][c + 1]) dfs(grid[r][c - 1]) GPT4: The base case for DFS is 1) the bounds check 2) the land check. To check for bounds you do: 1. if r < 0, r > len(gird), c < 0 or c > len(grid) 2. or grid[r][c] = '0' Then you set the island to 0. Q3: How would you now describe handling the recursive DFS calls to ensure we fully explore each island? A3: This recusrive call allows the function to navigate through the entire island by checking if there is any other peice of island around it in all directions. This applies to all the connected grid[r][c]. The only way for the recursion to end is if the call stack completes by hitting grid[r][c] == 0 or its out of bound, both meaning that the island ended. Implement the DFS Function: dfs(grid, r, c): if r < 0 or c < 0 or r > len(grid) or c > len(grid[r]) or grid[r][c] == 0: return islands += 1 grid[r][c] = 0 dfs(grid, r + 1, c) dfs(grid, r - 1, c) dfs(grid, r, c + 1) dfs(grid, r, c - 1) Q4: Can you think of any optimizations or edge cases? A4: If the grind is all zero or 1, you can either return 0 or 1. However that will be O(n^2) no? I wonder if there is a more efficent way to handle these edge cases. 1st attempt at writing func: class Solution: def numIslands(self, grid: List[List[str]]) -> int: islands = 0 for r in range(len(grid)): for c in len(grid[r]): if grid[r][c] == 1: dfs(grid, r, c) islands += 1 def dfs(grid, r, c): if r < 0 or c < 0 or r > len(grid) or c > len(grid[r]) or grid[r][c] == 0: return grid[r][c] = 0 dfs(grid, r + 1, c) dfs(grid, r - 1, c) dfs(grid, r, c + 1) dfs(grid, r, c - 1) return islands Problem #463 def islandPerimeter(self, grid: List[List[int]]) -> int: def dfs(grid, r, c, calls): if r < 0 or c < 0 or r > len(grid) or c > len(grid[r]) or grid[r][c] == 0: return calls += 1 dfs(grid, r + 1, c, calls) dfs(grid, r - 1, c, calls) dfs(grid, r, c + 1, calls) dfs(grid, r, c - 1, calls) for r in range(len(grid)): for c in len(grid[r]): if grid[r][c] == 1: dfs(r, c, 0) #The key thing to realize is that the number of times that the island is touching water is simply the number of calls on the call stack Max Area of Island: class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: ROWS, COLS = len(grid), len(grid[0]) def dfs(r, c): if r<0 or c<0 or r>=ROWS or c>=COLS or grid[r][c] == 0: return 0 grid[r][c] = 0 area = 1 area += dfs(r+1, c) area += dfs(r-1, c) area += dfs(r, c+1) area += dfs(r, c-1) return area maxArea = 0 for r in range(ROWS): for c in range(COLS): if grid[r][c] == 1: maxArea = max(maxArea,dfs(r, c)) return maxArea Problem 994. Rotting Oranges: def orangesRotting(self, grid: List[List[int]]) -> int: ROWS, COLS = len(grid), len(grid[0]) def dfs(grid, r, c): if r < 0 or c < 0 or r >= ROWS or c >= COLS or grid[r][c] == 0 or grid[r][c] == 2: return grid[r][c] = 2 dfs(r+1, c) dfs(r-1, c) dfs(r, c+1) dfs(r, c-1) for r in range(ROWS): for c in len(COLS): if grid[r][c] == 2: dfs(grid, r, c) DFS does not work for rotting oranges as the uniform spread alone with the time tracking makes it easier to do BFS. To visit the next cell, add to queue, you loop through its neighbors, by [r+1][c], [r-1][c], [r][c+1], [r][c-1] and cur is simply queue.pop() checking if its == 0, 1, or 2. If its 2, spread the rot. += 1 to level. You set the 1s you visited to 2 to ensure you don't revisit. You keep repeating this while stack to ensure that all the oranges are rotten. The only conditions in which the stack is empty is 1) you reached every part of the grid 2) all the surroundings are either 2 or 0, meaning that there is no more oranges to rot. form collections import deque def prepareInitialQueue(grid): ROWS, COLS = len(grid), len(grid[0]) rottenOrangesQueue = deque() for r in range(ROWS): for c in range(COLS): if grid[r][c] == 2: rottenOrangesQueue.append((r, c), 0) return rottenOrangesQueue Mon Mar 11 2024 392. Is subsequence [SOLVED ON PLANE] s_set, tmp = set(s), '' for i in range(len(t)): if i in range(len): if t[i] in s_set: tmp += t[i] if tmp == s: return True else: return False #Q, what if there are repeated letters in the subset - don't have to worry about it as it is a subsequence problem 334. Increasing Triplet Subsequence #Recall that a greedy algo works for a problem where you can solve it by just solving #the local optimum #The first part to the problem is that you solve the sub problem of [i, j] and nums[i] #< nums[j] #Q: what is the starting condition? i, j, k = 0, 1, 2 while i < len(nums) - 2 and j < len(nums) -1 and k < len(nums): if nums[i] < nums[j] < nums[k]: return True elif nums[i] > nums[j] #iterate till you solve it i += 1 elif nums[i] < nums[j] > nums[k]: j += 1 else: k += 1 return False Q what is the logic to iterate? [1, 2, 3, 4, 5] i j k In this example we return true [2, 1, 5, 0, 4, 6] i j k #The index condition will be taken care of the i, j, k loop #you want to return False unless triplet found #Another way to solve it- solve for the i j case first with a loop. #Start another loop with k where i, j = 0, 1 while i < len(nums) - 2 and j < len(nums) - 1: if nums[i] > nums[j]: j += 1 Save vals From now you can only iterate k We can actually rewrite that as i, j = 0, 1 while j < len(nums) - 1: if nums[i] > nums[j]: j += 1 else: break k = j while k < len(nums) - 1: if nums[j] > nums[k] k += 1 else: return True return True Ok now lets try to break this. Imagine the test case: [5,4,3,1,2,3] -> this should return true @ for 1, 2, 3. However we're not moving i. So this fails. Q: how do you increment i? [5,4,3,1,2,2,8,1] -> This should return True i j q: would it work if you save the min val that j has passed for i to index to? if nums[i] > j_min: move i to j_min position [5,4,3,1,2,2,8,1] i j j_min = 1 1ST HALF CODE i, j, j_min = 0, 1, nums[1] while j < len(nums) - 1: if nums[i] > nums[j] j += 1 j_min = min(j_min, nums[i]) if nums[i] > j_min: i = j else: return True return False Now add the k index -TODO... March 12 2024 1171. Remove Zero Sum Consecutive Nodes from Linked List You could use a while loop, although recursion is the most elegant solution. The first sub problem to solve: How to remove the consecutive elements: if cur.val == cur.next.val: delete Q: How do you delete two nodes at once? [1, 2, -3, 3, 1] Mar 13 2024 Ok let me walk you through what I am thinking. You have the vars i, j, k to track which indexes are able to return True. The starting condition has to be i, j, k = 0, 1, 2. The min possible val for nums[1] Next, the while loop of while j < len(nums) - 2 and k < len(nums) - 1: works because if j > len(nums)-2, or k = len(nums)-1, that means nums[i] < nums[j] < nums[k] and i < j < k would not be possible so we break it. Otherwise its fair game. Ok look at the line if nums[i] > nums[j]: That means we have to move j up to search for a j value that might fulfil nums[i] < nums[j] < nums[k]. We have to ensure that k > j. The mistake I made was j += 1 and k += 1 right away where I should've done if j = k, then k += 1. Now we need to keep j_min = min(j_min, nums[i]) because lets say in the example [5,4,3,1,2,2,8,1] we don't want to keep incrementing j till the end while i stays @5. Therefore if the j_min or a passed j value is smaller than i, we would want to move i there. Thus the code: j_min = min(j_min, nums[i]) if nums[i] > j_min: i = j j += 1 The problem with that is that you end up storing the lowest possible value. What you have to do instead is reset j_min and k_min at every cycle of the loop to the possible vals instead of the global min. while j < len(nums) - 2 and k < len(nums) - 1: j_min = nums[i] k_min = nums[j] Ok now we add the k elem. Now we can repeat the logic for nums[j] > nums[k]. At the start of every loop, we set k_min = nums[j]. And then: if nums[j] > nums[k]: k += 1 k_min = min(k_min, nums[j]) if nums[j] > k_min: j = k k += 1 Easy proof: if not nums[i] > nums[j] and not nums[j] > nums[k], that means nums[i] < nums[j] < nums[k] no? How can nums[i] be bigger than nums[k] if nums[i] < nums[j] and nums[j] < nums[k] for example? class Solution: def increasingTriplet(self, nums: List[int]) -> bool: i, j, k = 0, 1, 2 while j < len(nums) - 2 and k < len(nums) - 1: j_min = nums[i] k_min = nums[j] if nums[i] > nums[j]: j += 1 if j == k: k += 1 j_min = min(j_min, nums[i]) if nums[i] > j_min: i = j j += 1 if nums[j] > nums[k]: k += 1 k_min = min(k_min, nums[j]) if nums[j] > k_min: j = k k += 1 else: return True return False [] TODO: FIGURE OUT WHAT IS WRONG WITH THIS ******** Q: to self-> why does this code not work? According to GPT: To counter the dumb ass shit it said: 1) j_min and k_min 200 Number of Islands: Do DFS on all the islands, set them to 0. # of islands += 1. Return # of islands => Input: Grid ROW, COL = len(grid) - 1, len(grid[0]) - 1 #loop through the arry to find islan num = 0 for r in ROW: for c in COL: if grid[r][c] == 1: dfs(grid, r, c) num += 1 dfs(grid, r, c): if r < ROW and c < COL and r >= 0 and c >= 0 and not grid[r][c]: return grid[r][c] = 0 dfs(grid, r + 1, c) dfs(grid, r - 1, c) dfs(grid, r, c + 1) dfs(grid, r, c - 1) return num 605 Can Place Flowers input: flowerbed [], n int #What you do is simply find the max number of flowers you should be able to plant for i in range(len(flowerbed) - 1): if flowerbed[i] == 0 and flowerbead[i-1] == 0 and flowerbead[i+1] == 0 count += 1 There are a few edge cases for first and last elem = 0 [0, 0, 1, 0 , 0, 0, 1] We can solve this by if flowerbed[0] and flowerbed[1] both == 0, += 1. Start on the 3rd index. For range(3, len(flowerbed) - 3) Q; How about [...1, 0, 0] we can handle that case by only iterating till the 2nd last elem Putting this all together: count = 0 if flowerbead[0] == 0 and flowerbed[1] == 0: count += 1 if flowerbed[-1] == 0 and flowerbed[-2] == 0: count += 1 for i in range(4, len(flowerbed) - 4): if flowerbed[i] == 0 and flowerbed[i-1] == 0 and flowerbed[i+1] == 0 count += 1 return count >= n Ok. For the edge cases, what you could do is just set the vals to 1. Edge case of len(1)? Solved by having a case of len(flowerbed) == 0 238. Product of Array Except Self [1,2,3,4] -> [24,12,8,6] Try mutiplicative prefix sum: [1, 2, 6, 24] [24,24,12,4 ] Val * last val [1,2,6,12] [2,6,12,4] The problem I ran into above is the fact that I did in inclusive left_arr, right_arr, res = len(nums) * [1], len(nums) * [1], [] for i in range(1, len(nums)): left_arr[i] = nums[i-1] * left[i-1] for i in range(len(nums) - 2, -1, -1) right_arr[i] = nums[i+1] * left[i+1] for i in range(len(nums)): res.append(left_arr[i] * right_arr[i]) 930. Binary Subarrays With Sum This is a sliding window problem with a binary sum. Lets pretend its not binary. How would you generally solve a sliding window problem? LOL I thought it would be legit binary calculation. No we just counting the numbers of ones. We can do that with a prefix sum easily. nums = [1,0,1,0,1], goal = 2 In this example the prefix sum [1,1,2,2,3] if R - L + 1 = goal Ok now that we figured out how to efficently calculate the sum of window elems lets make the sliding window prefix = [num[0]] for i in range(1, len(nums)): prefix.append(prefix[-1] + nums[i]) L, R, solutions = 0, 0, 0 while R < len(nums): if L == 0: if goal == prefix[R]: solutions += 1 R += 1 elif prefix[R] - prefix[L - 1] == goal: solutions += 1 R += 1 elif prefix[R] - prefix[L] + 1 < goal: R += 1 else: L += 1 return solutions The correct method to calcualte the prefix sum is actually [R] - [L-1] Corrected version of the code according to GPT4: prefix = [0] for nums in nums: prefix.append(prefix[-1] + num) L, R, solutions = 0, 0, 0 while R < len(prefix) - 1: cur_sum = prefix[R + 1] - prefix[L] if cur_sum == goal: solutions += 1 R += 1 elif cur_sum < goal: R += 1 else: L += 1 return solutions This is a repeat of 930. Binary Subarrays With Sum Q1: A sub array is a smaller portion of an array defined by a left and right bound. Q2: The naive way is to brute force at O(n^2). Have an i and j pointer. Iterate i by one and every time iterate j from i -> len(nums). Q3: Sliding window can be applied for this problem because we know that if a previous sub array overshot the target, ex [1,1,1,0] where target = 2, we know that we can skip over a portion of the arrays thus turning this to O(n^2). Q4: Basic Sliding Window: solutions == 0 l, r = 0, 0 while l < len(nums) - 1: if nums[l] + nums[r] == target: solutions += 1 r += 1 #try to increase r, if its a 0, we can continue adding solutions elif nums[l] + nums[r] < target: r += 1 else: l += 1 One thing I'm thinking with this code is if we might be overshooting with R. Would we ever have l += 1 and then set r = l? Q5: In the above code, you would increase l += 1 if sum nums[l] nums[r] > target to shrink the window Q6: If the sum of l and r == target, we can increase a counter. Q7: One edge case that my code previously failed at is: [0,0,0,0,1,0,0,0,0] target == 0. I remeber failing a test case similar where the return val was 1 larger than it should've been. Ok. What is wrong with the current sliding window implementaion? Q: how to we handle the case of sum == target? Brainstorming: 1) Move right foward 2) mark l and r val as visited solution in set 3) try l -= 1, r += 1 The key is that we have to check if nums[l] + nums[r] == target repeat while nums[l] + nums[r] == target: solutions += 1 r += 1 Still not refined enough. Lets try to traverse through a prefix sum? Its not the most efficent For the sliding window, if you're not using the prefix sum, you can +- the number 1s in the window by doing a check to see if nums[l], nums[r] == 0 or 1. You can keep a sum count this way at O(1) space and O(n) time complexity pesudo code: solutions, window_sum = 0, 0 while l < len(nums) if wind_sum == target: solutions += 1 r += 1 window_sum += nums[r] elif window_sum < target: r += 1 window_sum += nums[r] else: window_sum -= nums[l] l += 1 Refined version l, r = 0, 0 window_sum = 0 solutions = 0 while r < len(nums): window_sum += nums[r] while window_sum > target < 1 <= r: window_sum -= nums[l] l += 1 if window_sum == target: solutions += 1 tmp_l = 1 while temp_l < r and nums[tmp_l] == 0: solutions += 1 temp_1 += 1 735. Asteroid Collision Pop from the stack twice. That will be the collisions. If same direction, append both to stack. If oppsite dir, append only the bigger one to the new stack. Q: do you continue till no more collisons? It seems like it. First step lets add to the stack: stack = [] while asteroids: a1 = asteroids.pop() a2 = asteroids.pop() if (a1 > 0 and a2 > 0) or (a1 < 0 and a2 < 0): stack.append(a1) stack.append(a2) elif a1 > a2: stack.append(a1) else: stack.append(a2) Cool, now that we have this, how do we keep crashing them till? A: We should create a def func that we call till 1) empty 2) all > 0 3) all < 0 neg, pos = False, False while stack or (not neg and pos) or (not pos and neg): for i in range(len(asteroids)): if neg and pos: neg, pos = False, False collide(asteroids) elif asteroids[i] > 0: pos = True else: neg = True def collide(asteroids): stack = [] while asteroids: a1 = asteroids.pop() a2 = asteroids.pop() if (a1 > 0 and a2 > 0) or (a1 < 0 and a2 < 0): stack.append(a1) stack.append(a2) elif a1 > a2: stack.append(a1) else: stack.append(a2) return stack Question: why do we not need another def function for this problem Few assumptions: The collision logic is not complex enough to need to be abstracted out into its own function- it can all be handles in a while loop stack = [] for asteriod in asteriods: collison = False while stack and asteriod < 0 < stack[-1]: Ok so with while stack and asteroid < 0 < stack[-1]: you're appending all of the neg val asteroid Think about the base case. By default, there is no collision, you stack.append. Then there is the collision case: If we face an asteriod and the stack is not empty we check which one is bigger. The key here is to mark collision as True and break that while loop so we don't hit the case of if not collision, stack.append. 2126. Destroying Asteroids The key to this problem is that you can sort the asteroids. That gives the planet the best chance because that max the size of the planet at every interval. Don't need stack. sorted(asteroids) for asteroid in asteroids: if mass > asteroid: mass += asteroid else: return False return True 739. Daily Temperatures Use a stack. We're trying to map: [73,74,75,71,69,72,76,73] -> [1,1,4,2,1,1,0,0] pop from the tempatures stack. Add to another tmp stack. I think the trick is how many times you have to pop from the tmp stack till you get a val that is larger. stack = [tempatures.pop()] res = [] while tempatures: count = 0 tempature = tempatures.pop() while tempature > stack[-1]: stack.pop() count += 1 res.append(count) stack.append(tempature) Lets manually go through an interation: [73,74,75,71,69,72,76,73] tempature = count = Stack = Res = This approach is not correct. Apprently you track the index of each day in the stack. If given a specific day's tmp, the most simple method is to iterative till next warmer tmp and count # of iterations. However, you could the index of the last highest tmp into the stack. And then to find number of days, you can do last higher index - cur index to find the number of days. You want to store the index val of the date. Q: When do you add to stack? Q: When do you pop from the stack? Wait wtf is a monotonic stack? Mar 15 2024 For a problem where you need to find the next greater element in array, why would you not want a regular stack? To be fair, I'm not sure how you would solve it efficiently with a regular stack. The brute force method to solve this is to iterate through i and make a comparsion to j every time which is O(n^2). Another way I wrote the other day for a similar question is to count the number of times a tmp stack gets popped(). This still seems O(n^2) as you would have to pop n elem, and add it again for the next iteration. What I'm thinking about is if there is a O(n) way to just count the number of pops. Perhapes making a set of the index + vals? When you encounter an element greater than stacks top elem, I would guess that you keep popping until the last elem of the stack is larger? no idea lol. on 5 hours of sleep too tired to work it out myself (is that bad that I'm this lazy?) Q: How does this provide O(n) run time? Recall for a monotonic stack, you only add the largest elem, and you keep popping from the stack till you 1) find an elem 2) there is no more elems in the arry. My knee jerk response is to count the number of pops. My but I recall that a problem stored the index elems. When you come upon the largest elem you find the diff between the index vals to find out how far they are apart from another.