**Number of Islands**

- Given a 2d grid map of ’1’s (land) and ’0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
- Want to count the number of islands

```
class Solution:
def numIslands(self, grid):
rc = len(grid)
if(rc == 0):
return 0
cc = len(grid[0])
if (cc == 0):
return 0
count = 0
for r in range(rc):
for c in range(cc):
if grid[r][c] == "1":
grid = self.connected(grid, r, c)
count += 1
return count
def connected(self, grid, r, c):
if(grid[r][c] == "0"):
return grid
translations = [[0, 1], [1, 0], [0, -1], [-1, 0]]
rc = len(grid)
cc = len(grid[0])
grid[r][c] = "0"
for t in translations:
if(0 <= r + t[0] < rc and 0 <= c + t[1] < cc):
grid = self.connected(grid, r + t[0], c + t[1])
return grid
```

BFS can be used. Union Find can also solve this problem.

- Attempt #1

```
import string
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.val = None
self.isEnd = False
self.children = dict(
zip(string.ascii_lowercase, [None for i in range(26)]))
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
node = self
children = node["children"]
firstLetter = True
for l in word:
if children[str(l)] is not None:
node = children[str(l)]
children = node["children"]
else:
children[str(l)] = Trie()
node = children[str(l)]
node.val = l
children = node["children"]
node.isEnd = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
root = self
stack = [{"node": root, "index": 0}]
success = False
while len(stack):
n = stack.pop()
print(n)
if(n["index"] == len(word)):
success = True if (
word[-1] == n["node"]["val"]
and n["node"].isEnd) else False
if success:
return True
else:
for c in n["node"]["children"].values():
if (c is not None and c.val == word[n["index"]]):
stack.append({"node": c, "index": n["index"] + 1})
return False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
root = self
stack = [{"node": root, "index": 0}]
success = False
while len(stack):
n = stack.pop()
if(n["index"] == len(prefix)):
success = True if (
prefix[-1] == n["node"]["val"]) else False
if success:
return True
else:
for c in n["node"]["children"].values():
stack.append({"node": c, "index": n["index"] + 1} if (
c is not None and c.val == prefix[n["index"]]
) else {"node": c, "index": 0})
return False
```

```
import collections
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.isWord = False
self.children = collections.defaultdict(Trie)
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
if self.search(word):
return
else:
node = self
for l in word:
node = node.children[l]
node.isWord = True
def search(self, word, node=None):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self
for l in word:
if l in node.children:
node = node.children[l]
else:
return False
return node.isWord
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self
for l in prefix:
if l in node.children:
node = node.children[l]
else:
return False
return True
```

**Rotate Image**

- You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).

```
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
matrix.reverse()
self.transpose(matrix)
def transpose(self, matrix):
N = len(matrix)
for i in range(N):
for j in range(i + 1, N):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
return matrix
```

**📕**

**Word Break**

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

- Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1:
- Solution

```
import re
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
if len(s) == 0:
return False
hash = {}
return self.search(s, wordDict, hash)
def search(self, s, words, memo):
if s in memo:
return memo[s]
if len(s) == 0:
return True
matches = []
for w in words:
if re.match(w, s) is not None:
matches.append("".join(re.split(w, s, 1)))
for m in matches:
res = self.search(m, words, memo)
if res == True:
return res
memo[s] = False
return memo[s]
```

`self`

in pyton is equivalent to `this`

in javascript
- Strategy - use a trie, and do bfs with the trie```
class Trie(object):
def __init__(self):
self.cache = {}
@cache
def insert(self, word):
pass
def cache(f):
def method(obj, s):
if s not in obj.cache:
obj.cache[s] = f(obj, s)
return obj.cache[s]
return method
```

- Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

```
class Solution:
def maxProduct(self, nums: List[int]) -> int:
maximum = -float('inf')
N = len(nums)
A = [[None for i in range(N)] for j in range(N)]
for i, num in enumerate(nums):
A[i][i] = num
maximum = max([num, maximum])
for i in range(N):
for j in range(i + 1, N):
A[i][j] = A[i][j - 1] * nums[j]
if(A[i][j] > maximum):
maximum = A[i][j]
return maximum
```

`float('inf')`

2. you can use one array… how would you do that?Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

```
import collections
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
if n == 0:
return 0
A = [[0 for i in range(n)] for j in range(n)]
for e in edges:
[u,v] = e
A[u][v] = 1
A[v][u] = 1
visited = {}
count = 0
stack = []
for u in range(n):
if u in visited:
continue
else:
count+=1
stack.append(u)
while(len(stack)):
cur = stack.pop()
if cur in visited:
continue
else:
visited[cur] = True
neighbors = A[cur]
for i, nb in enumerate(neighbors):
if nb == 1:
stack.append(i)
visited[u] = True
return count
```

**Unique Paths**

- A robot is located at the top-left corner of a
`m x n`

grid (marked ‘Start’ in the diagram below). - The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
- How many possible unique paths are there?

```
import math
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if(m < 2 or n < 2):
return (1 if m + n >= 2 else 0)
A = [[1 for i in range(n)] for j in range(m)]
for i in range(1, m):
for j in range(1, n):
A[i][j] = A[i - 1][j] + A[i][j - 1]
return A[m - 1][n - 1]
```

```
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return root
root.left, root.right = self.invertTree(
root.right), self.invertTree(root.left)
return root
```

**Meeting Rooms**

Given an array of meeting time intervals consisting of start and end times `[[s1,e1],[s2,e2],…]`

(`s_i < e_i`

), determine if a person could attend all meetings.

```
from heapq import heappush, heappop
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
l = []
[heappush(l, el) for el in intervals]
if len(l) < 2:
return True
while len(l) > 1:
interval1 = heappop(l)
interval2 = heappop(l)
if self.conflictExists(interval1, interval2):
return False
heappush(l, interval2)
return True
def conflictExists(self, one, two):
return one[0] < two[0] < one[1] or two[0] < one[1] < two[1] or one[0] <= two[0] <= two[1] <= one[1]
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort(key = lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i-1][1] > intervals[i][0]:
return False
return True
```

```
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort(key = lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i-1][1] > intervals[i][0]:
return False
return True
```

**Longest Substring without Repeating characters**

```
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""
Input:
Output:
Edge Cases:
Constraints:
Approaches:
* Brute Force: Every length of substring and check O(n^2)
* Sliding Window using two pointers and a dictionary
"""
seen = {l: False for l in s}
beg, end, res = 0, 0, 0
while beg < len(s):
while end < len(s) and not seen[s[end]]:
seen[s[end]] = True
end += 1
res = max(res, end - beg)
if end == len(s):
break
seen[s[beg]] = False
beg += 1
return res
```

- Two Pointers: Increment end pointer while no repeating characters

**🍩 Climbing Stairs**

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

```
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
dp = [1, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2])
return dp[-1]
```

- Negative Indices nums[-1]
- It is fibonacci

**Recursive Solution:** `dp[i] = dp[i-1] + dp[i-2]`

**Contains Duplicate**

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

```
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
seen = {}
for num in nums:
if num in seen:
return True
else:
seen[num] = True
return False
```

Lessons & Mental Model

You can extract unique elements from a list by creating a set object

**🥓 Merge Two Sorted Lists**

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

- Input:
`1->2->4, 1->3->4`

- Output:
`1->1->2->3->4->4`

```
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
root = ListNode(None)
node = root
while(l1 and l2):
node.next = (l1 if l1.val <= l2.val else l2)
l1 = l1.next if node.next is l1 else l1
l2 = l2.next if node.next is l2 else l2
node = node.next
node.next = l1 if l1 else l2
return root.next
```

- This is like the merge step in mergesort

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

### First Attempt

```
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adj = self.adjacencyList(numCourses, prerequisites)
status = [0 for _ in range(numCourses)] # status = 0 means not visited
for n in range(numCourses):
if not self.detectCycle(adj, n, status): # DFS
return False
return True
def detectCycle(self, adj, node, status):
if(status[node] == -1): # status = -1 means visiting
return False
if(status[node] == 1): # status = 1 means done
return True
status[node] = -1
neighbors = adj[node]
for neighbor in neighbors:
if not self.detectCycle(adj, neighbor, status):
return False
status[node] = 1
return True
def adjacencyList(self, size, edges):
adj = [[] for _ in range(size)]
while edges:
i, j = edges.pop()
adj[i].append(j)
return adj
```

- The key insight is that if we see a node that we have finished exploring a node, we have a cycle
- In DFS, each node can be white (undiscovered), grey (visited), black (complete)

**🌳 Binary Tree Max Path Sum**

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

```
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
if(not root):
return 0
if(not root.left and not root.right):
return root.val
q = [root]
nodes = []
parent = {}
allPairs = set()
while q:
cur = q.pop(0)
nodes.append(cur)
nbs = [cur.left, cur.right]
for nb in nbs:
if nb is not None:
parent[nb] = cur
q.append(nb)
for i in range(len(nodes)):
for j in range(i, len(nodes)):
if tuple([nodes[j], nodes[i]]) not in allPairs:
allPairs.add((tuple([nodes[i], nodes[j]])))
pathsums = {p: None for p in allPairs}
allPairs = list(allPairs)
while(allPairs):
cur = allPairs.pop(0)
if pathsums[cur] is None:
self.pathSum(cur, pathsums, parent)
return max(filter(None, pathsums.values()))
def pathSum(self, pair, ps, parent):
q = [[pair[0], pair[0].val]]
while(q):
cur, d = q.pop(0)
if cur == pair[1]:
ps[pair] = d
return ps
nbs = [cur.left, cur.right,
(None if cur not in parent else parent[cur])]
for nb in nbs:
if nb is not None:
q.append([nb, d + nb.val])
```
```

```
def maxPathSum(self, root: TreeNode) -> int:
if not root:
return 0
self.res = -float('inf')
self.oneSideSum(root)
return self.res
def oneSideSum(self, node):
if not node:
return 0
leftST = max(0, self.oneSideSum(node.left))
rightST = max(0, self.oneSideSum(node.right))
self.res = max(self.res, leftST + rightST + node.val)
return max(leftST, rightST) + node.val
```

- Really think about the problem statement. I initially thought this was an All Pairs Shortest Path problem and tried to solve it with a variation of the Floyd Warshall Algorithm. This meant that I needed to go through the tree and create parent references, and then look at all paths. This was a working solution, but it was too slow.
- The actual solution is to find the maximum sum at each

Reverse a singly linked list.

```
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
s = []
node = head
while(node and node.next):
tmp = node.next
node.next = None
s.append(node)
node = tmp
tail = node
while s:
node.next = s.pop()
node = node.next
return tail
```

- You can use a stack to reverse a list (i.e. process in reverse order)

**🐑**

**Clone Graph**

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

```
class Solution:
def cloneGraph(self, node: 'Node', clones={}) -> 'Node':
if not node:
return None
if node in clones:
return clones[node]
clone = Node(node.val, [])
clones[node] = clone
for nb in node.neighbors:
clone.neighbors.append(self.cloneGraph(nb, clones))
return clone
```

Solution:

Lessons Learned:

- You want to use a hashmap to hash nodes to their clones and return the cached clone if the node has been seen and cloned before

**Reorder List**

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

```
from collections import defaultdict
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
I: Head of LL
O: Reordered List (e.g. 1->2->3->4 => 1->4->2->3)
C: Modify head in-place (No additional memory)
E: Empty List => returns None
"""
if head is None or head.next is None:
return head
l1, l2 = self.splitList(head)
l2 = self.reverseList(l2)
self.mergeList(l1, l2)
def splitList(self, ll):
l1, l2 = ll, None
fast = ll
slow = ll
while(fast and fast.next):
slow = slow.next
fast = fast.next
fast = fast.next
l2 = slow.next
slow.next = None
return l1, l2
def reverseList(self, ll):
stack = []
node = ll
while node is not None:
stack.append(node)
tmp = node
node = node.next
tmp.next = None
if stack:
res = stack.pop()
node = res
else:
return node
while stack:
node.next = stack.pop()
node = node.next
return res
def mergeList(self, l1, l2):
cur1 = l1
cur2 = l2
while(cur2):
tmp1, tmp2 = cur1.next, cur2.next
cur1.next, cur2.next = cur2, tmp1
cur1, cur2 = tmp1, tmp2
```

Solution: https://leetcode.com/problems/reorder-list/discuss/447242/python-solution

Lessons Learned:

- Break the problem down into helper functions

**Word Search**

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

```
from collections import deque, defaultdict
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
"""
I:
O:
C:
E:
Approach:
BFS
"""
if not word:
return True
for row in range(len(board)):
for col in range(len(board[0])):
if(word[0] == board[row][col]):
if(self.dfs(word, 0, board, row, col)):
return True
return False
def dfs(self, word, idx, grid, gridRow, gridCol):
char = grid[gridRow][gridCol]
if char != word[idx]:
return False
elif idx == len(word) - 1:
return True
grid[gridRow][gridCol] = ""
transformations = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for rT, cT in transformations:
if(0 <= rT + gridRow < len(grid) and 0 <= cT + gridCol < len(grid[0])):
if(self.dfs(word, idx + 1, grid, rT + gridRow, cT + gridCol)):
return True
grid[gridRow][gridCol] = char
return False
```

Solution:

https://leetcode.com/problems/word-search/discuss/27660/Python-dfs-solution-with-comments

Lessons Learned:

- searching for existence usually means dfs
- deque

**🕶**

**Decode Ways**

- A message containing letters from A-Z is being encoded to numbers using the following mapping:
- ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.

```
class Solution:
def numDecodings(self, s: str) -> int:
if not s:
return 0
if len(s) == 1:
return 0 if s=="0" else 1
if s[0] == "0":
return 0
l = len(s)
dp = [0] * l
for i in range(l):
dp[i] = 0 if s[i] == "0" else (1 if 2 < int(s) <= 9 else 2)
for i in in range(l):
if dp[i] == 2:
dp[i] -= 1 if int(s[j:j+2]) > 26
print([dp[i-1]* (dp[i] if dp[i] != 0 else 1) for i in range(1,l)])
```

```
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == "0":
return 0
l = len(s)
dp = [1] + [0] * l
for i in range(1, l + 1):
dp[i] += (dp[i - 1] if s[i - 1] != "0" else 0)
dp[i] += (dp[i - 2] if (i > 1 and 10 <= int(s[i - 2:i]) <= 26) else 0)
return dp[-1]
```

**Longest Consecutive Sequence**

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

- Input:
`[100, 4, 200, 1, 3, 2]`

- Output:
`4`

- Explanation: The longest consecutive elements sequence is
`[1, 2, 3, 4]`

. Therefore its length is`4`

.

### First Attempt (TLE)

```
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
if len(nums) == 2:
return 2 if abs(nums[0] - nums[1]) == 1 else 1
mn = float('inf')
mx = -float('inf')
output = []
counts = {}
for num in nums:
if num != float('inf') and num != float('inf'):
mn = min(mn, num)
mx = max(mx, num)
for num in nums:
if num != float('inf') and num != float('inf'):
if(num not in counts):
counts[num] = 1
else:
counts[num] += 1
for j in range(mn, 0):
if(j in counts):
output.append(j)
for i in range(mx + 1):
if(i in counts):
output.append(i)
beg, end = 0, 0
length = 1
for i in range(1, len(output)):
end += 1
if (abs(abs(output[i]) - abs(output[i - 1])) != 1):
length = max(length, end - beg)
beg, end = i, i
# print(output)
# print(counts, end='\n')
return max(length, end - beg + 1)
```

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

```
class Solution:
def hasCycle(self, head: ListNode) -> bool:
"""
I: LL Node
O: Boolean
C: O(1) space if possible
E: not head or not head.next
"""
if not head or not head.next:
return False
slow = head
fast = head.next
hashmap = {slow: True}
while fast and fast.next:
if fast in hashmap:
return True
hashmap[slow] = True
slow = slow.next
fast = fast.next.next
return False
```

`slow = head, fast = head.next`

**Spiral Matrix**

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

```
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
if not len(matrix):
return res
while matrix:
res.extend(matrix.pop(0))
if matrix and matrix[0]:
res.extend([row.pop() for row in matrix])
if matrix:
res.extend(matrix.pop()[::-1])
if matrix and matrix[0]:
res.extend([row.pop(0) for row in matrix][::-1])
return res
```

**Pacific Atlantic Water Flow**

```
class Solution:
def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
res = []
if not matrix:
return res
rc = len(matrix) # row count
cc = len(matrix[0]) # column count
self.dir = [[0, 1], [1, 0], [-1, 0], [0, -1]] # Directions
pacific = [[False for _ in range(cc)] for _ in range(rc)]
atlantic = [[False for _ in range(cc)] for _ in range(rc)]
# Which nodes can the sides reach?
for i in range(rc): # for the sides
self.dfs(matrix, rc, cc, i, 0, pacific)
self.dfs(matrix, rc, cc, i, cc - 1, atlantic)
# Which nodes can the top/bottom reach?
for i in range(cc): # for the top and bottom
self.dfs(matrix, rc, cc, 0, i, pacific)
self.dfs(matrix, rc, cc, rc - 1, i, atlantic)
for i in range(rc):
for j in range(cc):
if pacific[i][j] and atlantic[i][j]:
res.append([i, j])
return res
def dfs(self, grid, m, n, i, j, visited):
if(visited[i][j]):
return
visited[i][j] = True
for d in self.dir:
x, y = d[0] + i, d[1] + j
if (0 <= x < m and 0 <= y < n and grid[i][j] <= grid[x][y]):
self.dfs(grid, m, n, x, y, visited)
```

- I initially wanted to do a depth first search from every node to see if it termination condition could be reached. The termination condition was complicated and that kept on screwing my algorithm up. Instead the correct way to implement was to do a Depth first search from the outer layer of the matrix.
`self.directions = …`

`x, y = dir[0] + i, dir[1] + y`

- You can actually use a matrix to store results/path, instead of a hash table

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

```
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
return (self.preorderTraversal(root))
def preorderTraversal(self, root):
if not root:
return ",None"
return "," + str(root.val) + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
return self.buildTree(data[1:].split(','))
def buildTree(self, l):
if not l:
return
first = l.pop(0)
root = None if first == "None" else TreeNode(int(first))
if not root:
return root
root.left = self.buildTree(l)
root.right = self.buildTree(l)
return root
```

```
from collections import deque
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
serialized = []
q = deque([root])
while(q):
cur = q.popleft()
serialized.append("None" if cur is None else str(cur.val))
if serialized[-1] != "None":
q.append(cur.left)
q.append(cur.right)
return ",".join(serialized)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
data = deque(data.split(','))
val = data.popleft()
root = None if val == "None" else TreeNode(int(val))
q = deque([root])
while q:
cur = q.popleft()
if cur:
left, right = data.popleft(), data.popleft()
cur.left = None if left == "None" else TreeNode(int(left))
cur.right = None if right == "None" else TreeNode(int(right))
q.append(cur.left)
q.append(cur.right)
return root
```

- Preordered Traversal is the same as BFS
- deque takes an iterable

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

- nums =
`[1, 2, 3]`

- target =
`4`

- The possible combination ways are:
`(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)`

Note that different sequences are counted as different combinations.

Therefore the output is 7.

```
from collections import defaultdict
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
"""
I: Array, Target Integer
O: Number of ways to add numbers in the list to add up to target num
C:
E: Positive numbers? Negative Numbers? Zeros? Empty list?
Approach:
* Observation: The ways to add numbers in an array to add up to a target is the union of the ways to add up numbers in every subset of nums
* Ex: cS4([1,2,3,4], 5) = cS4([2,3,4], 5) + cS4([1,3,4], 5) + cS4([1,2,4], 5) + cS4([1,2,3], 5) = ... = cS4([1], 5) + cS4([2], 5) + cS4([3], 5) + cS4([1]) + .... +
1. Selected: Recursion, with Memoization since each subset will eventually end up calling the same problems
2. Bottom up DP - dp[i][j] = dp[i]
3. Similar to an unbounded knapsack problem
"""
self.cache = [-1] * (target + 1)
count = 0
for num in nums:
count += self.dfs(nums, target - num)
return count
def dfs(self, nums, target):
if target < 0:
return 0
res = 0
if self.cache[target] != -1:
return self.cache[target]
if target == 0:
return 1
for num in nums:
res += self.dfs(nums, target - num)
self.cache[target] = res
return res
```

- ⭐️Bonus: Which question is this question similar to? How are they different?

- It is not varying the subarray, but rather the “target” and counting the ways that nums can make each “subtarget”
- => The subproblem is dp[i] += dp[i - nums[j]] if nums[j] > i where i is the “sub-target”
- Q: In the solution, why is the outer loop the amount, and not the nums? (A: Permutations, not combinations)

### Bonus: Which question is this question similar to? How are they different?

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

### First Attempt

Code:

```
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [1] + [0] * amount
for coin in coins:
for i in range(amount + 1):
if i - coin >= 0:
dp[i] += dp[i - coin]
return dp[amount]
```

Solution:

https://leetcode.com/problems/coin-change-2/discuss/99222/Video-explaining-how-dynamic-programming-works-with-the-Coin-Change-problem

Lessons Learned:

- Q: Why is the outer loop the coins and not the amount?

**Meeting Rooms 2**

- Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

- Input:
`[[0, 30],[5, 10],[15, 20]]`

- Output:
`2`

- Input:
`[[7,10],[2,4]]`

- Output:
`1`

```
from heapq import heappop, heappush
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort()
finishTimes = []
heappush(finishTimes, intervals[0][1])
for interval in intervals[1:]:
if finishTimes[0] <= interval[0]:
heappop(finishTimes)
heappush(finishTimes, interval[1])
return len(finishTimes)
```

`heapify`

from`heapq`

only heapifies one element, and does it in place- to sort a list of objects you can pass a lambda function like below to the sort method

`key = lambda x: x.start`

- Note: To get a reverse list you want to use
`[::-1]`

Solution

**Top K Frequent Elements**

Given a non-empty array of integers, return the k most frequent elements.

- Input:
`nums = [1,1,1,2,2,3]`

,`k=2`

- Output:
`[1,2]`

- Input:
`nums = [1]`

,`k = 1`

- Output:
`[1]`

- Note: You may assume k is always valid,
`1 ≤ k ≤ number of unique elements`

. Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

```
from collections import defaultdict
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if not nums or not k:
return None
frequencyTable = defaultdict(int)
for num in nums:
frequencyTable[num] += 1
return sorted(frequencyTable.keys(), key=lambda x: frequencyTable[x], reverse=True)[:k]
```

- Cant use
`.sort`

method on dict keys

**Subtree of Another Tree**

Given two non-empty binary trees `s`

and `t`

, check whether tree `t`

has exactly the same structure and node values with a subtree of `s`

. A subtree of `s`

is a tree consists of a node in `s`

and all of this node’s descendants. The tree `s`

could also be considered as a subtree of itself.

```
Example 1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
```

```
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not s and not t:
return True
if not s or not t:
return False
if (self.sameTree(s, t)):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def sameTree(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)
```

1. Think in terms of subroutines

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

```
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
return max(self.simple_rob(nums[1:]), self.simple_rob(nums[:-1]))
def simple_rob(self, nums):
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
l = len(nums)
dp = [0] * l
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, l):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return max(dp)
```

Solution

Lessons

Given a `m x n`

matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

- Input: [ [1,1,1], [1,0,1], [1,1,1]] Output: [ [1,0,1], [0,0,0], [1,0,1]]
- Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5]] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0]]

- Follow up: A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?

```
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
if not matrix:
return
rows = set()
cols = set()
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
rows.add(i)
cols.add(j)
def zeroRows(m, r_idx):
for i in range(len(m[r_idx])):
m[r_idx][i] = 0
return m
def zeroCols(m, c_idx):
for i in range(len(m)):
m[i][c_idx] = 0
return m
while(len(rows)):
matrix = zeroRows(matrix, rows.pop())
while(len(cols)):
matrix = zeroCols(matrix, cols.pop())
```