Some notes about DSA

### Big O#

• Neetcode
• Big O Cheat Sheet
• Recursive with multiple branches: O(branches^depth), if not repeated work, O(n).
• Fibonacci: O(2^n), with memoization: O(n)
• Permutations, TSP: O(n!)

### Reacto#

• Read the problem, ask clarifying questions, assumptions
• Examples, edge cases
• Approach, pseudocode
• Code
• Test, edge cases
• Optimize, space and time complexity

### Legend#

• 🅱️ Blind 75 / 🗿 Neetcode / 🏢 Google
• ☀️ Easy / ⛅ Medium / ⛈️ Hard

## Arrays#

``````for n in nums:
# need to shrink?
if cur_sum+n < n: ...
# update result
if cur_sum > max_sum: ...
``````
``````for r in range(len(nums)):
if r-l+1 == k:
...
``````

### Basic & Hashing#

• 🅱️Contains Duplicate☀️: 💡

• `nums = [1,2,3,1]` => `true`

• Hashset seen / sort and check i and i+1

• O(n) time, O(n) space
``````def containsDuplicate(self, nums: List[int]) -> bool:
"""O(n) time, O(n) space"""
seen = set()

for n in nums:
if n in seen:
return True
return False

def containsDuplicate(self, nums: List[int]) -> bool:
"""O(nlogn) time, O(1) space"""
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return False
``````
• 🅱️Valid Anagram☀️: 💡

• `s = "anagram", t = "nagaram"` => `true`

• 2 Counters / 1 counter and decrease / sort

• O(w) time, O(1) space
``````def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
count_s = Counter(s)
count_t = Counter(t)
return count_s == count_t
``````
• 🅱️🏢Two Sum☀️: 💡

• `nums = [2,7,11,15], target = 9` => `[0,1]`

• Hashmap seen and store index, look for complement

• O(n) time, O(n) space
``````def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, n in enumerate(nums):
if target - n in seen:
return seen[target - n], i
seen[n] = i
``````
• 🅱️Group Anagrams⛅: 💡

• `strs = ["tea","tan","ate","nat"]` => `[["nat","tan"],["ate","tea"]]`

• Counter for each string, use tuple as key

• O(strings*average_lenth) time, O(strings) space
``````def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for word in strs:
groups[tuple(sorted(Counter(word).items()))].append(word)
return list(groups.values())
``````
• `nums = [1,1,1,2,2,3], k = 2` => `[1,2]`

• Counter, list of frequencies (len(nums)), iterate from end

• O(n) time, O(n) space
``````def topKFrequent(self, nums: List[int], k: int) -> List[int]:
groups_by_freq = [[] for _ in range(len(nums)+1)]
for n, count in Counter(nums).items():
groups_by_freq[count].append(n)
result = []
for i in range(len(nums), -1, -1):
for n in groups_by_freq[i]:
result.append(n)
if len(result) >= k:
return result
return result
``````
• `nums = [1,2,3,4]` => `[24,12,8,6]`

• Prefix product, Suffix product.

• O(n) time, O(1) space
``````def productExceptSelf(self, nums):
ans = [1]*len(nums)
suf, pre = 1, 1
for i in range(len(nums)):
ans[i] *= pre
ans[-1-i] *= suf
pre *= nums[i]
suf *= nums[-1-i]
return ans
``````
• partially filled 9x9 grid

• sets, `squares[(r // 3, c // 3)].add(board[r][c])`

• O(1) time, O(1) space
``````def isValidSudoku(self, board: List[List[str]]) -> bool:

for row in board:
numbers = [n for n in row if n != "."]
if len(set(numbers)) != len(numbers):
return False

for i in range(9):
numbers = [row[i] for row in board if row[i] != "."]
if len(set(numbers)) != len(numbers):
return False

squares = defaultdict(set)
for r in range(9):
for c in range(9):
block = squares[(r // 3, c // 3)]
if board[r][c] != "." and board[r][c] in block:
return False
return True
``````
• Create single string and split it back

• Length + Separator

• O(n) encode, O(n) decode
``````def encode(self, strs):
res = ""
for s in strs:
res += str(len(s)) + "#" + s
return res

def decode(self, s):
res, i = [], 0

while i < len(s):
j = i
while s[j] != "#":
j += 1
length = int(s[i:j])
res.append(s[j + 1 : j + 1 + length])
i = j + 1 + length
return res
``````
• `nums = [100,4,200,1,3,2]` => `4`

• Set and start if n-1 not in set

• O(n) time, O(n) space
``````def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
hashset = set(nums)
result = 1
for n in hashset:
if (n-1) not in hashset:
length = 0
cur = n
while cur in hashset:
cur = cur+1
length += 1
result = max(result, length)
return result
``````

### Two Pointers#

• 🅱️Valid Palindrome☀️: 💡

• `s = "A man, a plan, a canal: Panama"` => `true`

• Two pointers, `if not s[i].isalnum(): i += 1`

• O(n) time, O(1) space
``````def isPalindrome(self, s: str) -> bool:
l = 0
r = len(s)-1
while l < r:
while l < len(s) and not s[l].isalnum(): l += 1
while r >= 0 and not s[r].isalnum(): r -= 1
if l >= r:
return True
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1

return True
``````
• 🗿Two Sum II⛅: 💡

• `numbers = [2,7,11,15], target = 9` => `[1,2]`

• 2 pointers.

• O(n) time, O(1) space
``````def twoSum(self, numbers: List[int], target: int) -> List[int]:
l = 0
r = len(numbers)-1
while l < r:
cursum = numbers[l] + numbers[r]
if cursum == target:
return [l+1, r+1]
if cursum < target:
l += 1
else:
r -= 1
return None
``````
• 🅱️3Sum⛅: 💡

• `nums = [-1,0,1,2,-1,-4]` => `[[-1,-1,2],[-1,0,1]]`

• sort, for each i, 2 pointers (l = i+1, r = len(nums)-1)

• O(n^2) time, O(n) space (sorting)
``````def threeSum(self, nums: List[int]) -> List[List[int]]:
result = set()
nums.sort()
for i in range(len(nums)):
l, r = i+1, len(nums)-1
while l < r:
sum3 = nums[l] + nums[r] + nums[i]
if sum3 == 0:
l += 1
r -= 1
elif sum3 < 0:
l += 1
else:
r -= 1
return result
``````
• `height = [1,8,6,2,5,4,8,3,7]` => `49`

• start from both ends, move the smaller one

• O(n) time, O(1) space
``````def maxArea(self, height: List[int]) -> int:
result = 0
l, r = 0, len(height)-1
while l < r:
result = max(result, min(height[l], height[r])*(r-l))
if height[l] < height[r]:
l += 1
else:
r -= 1
return result
``````
• `height = [0,1,0,2,1,0,1,3,2,1,2,1]` => `6`

• using 2 pointers, update result before moving the pointer

• O(n) time, O(n) space
``````def trap(self, height: List[int]) -> int:
leftmax, rightmax = 0, 0
l, r = 0, len(height)-1
result = 0

while l <= r:
if leftmax <= rightmax:
result += max(min(leftmax, rightmax)-height[l], 0)
leftmax = max(leftmax, height[l])
l += 1
else:
result += max(min(leftmax, rightmax)-height[r], 0)
rightmax = max(rightmax, height[r])
r -= 1
return result
``````

### Sliding Window#

• `prices = [7,1,5,3,6,4]` => `5`

• Kadane’s algorithm / Two pointers (start from 0, 1)

• O(n) time, O(1) space
``````def maxProfit(self, prices: List[int]) -> int:
result = 0
cheapest = prices[0]
for p in prices:
result = max(result, p-cheapest)
cheapest = min(cheapest, p)
return result
``````
• `s = "abcabcbb"` => `3` (“abc”)

• Hashmap (seen, index), left = max(left, seen[c]+1)

• O(n) time, O(1) space
``````def lengthOfLongestSubstring(self, s: str) -> int:
result = 0
l = 0
last_seen = {}
for i, c in enumerate(s):
if c in last_seen:
l = max(l, last_seen[c]+1)  # do not decrease!
last_seen[c] = i
result = max(result, i-l+1)
return result
``````
• `s = "ABAB", k = 2` => `4` (replace both A with B)

• Window with most repeating, shrink `if windowLen - max(count.values()) > k`

• O(n) time, O(1) space
``````def characterReplacement(self, s: str, k: int) -> int:
result = 0
l = 0
char_count = {}
for r, c in enumerate(s):
char_count[c] = char_count.get(c, 0) + 1
if (r-l+1) > max(char_count.values())+k:
char_count[s[l]] -= 1
l += 1
result = max(result, r-l+1)
return result
``````
• `s1 = "ab" s2 = "eidbaooo"` => `true`

• Counter, sliding window of size len(s1)

• O(n) time, O(1) space
``````def checkInclusion(self, s1: str, s2: str) -> bool:
cntr, w = Counter(s1), len(s1)
for i in range(len(s2)):
if s2[i] in cntr:
cntr[s2[i]] -= 1
if i >= w and s2[i-w] in cntr:  # shrink
cntr[s2[i-w]] += 1
if all([cntr[i] == 0 for i in cntr]):
return True
return False
``````
• `s = "ADOBECODEBANC", t = "ABC"` => `"BANC"`

• Counter, if all window counter >= counter, shrink, i = 0, for j in …

• O(n) time, O(1) space
``````def minWindow(self, s: str, t: str) -> str:
need = collections.Counter(t)
l = 0
result = ""
for r, c in enumerate(s):
need[c] -= 1
if all(v <= 0 for v in need.values()):
while l < r and need[s[l]] < 0:
need[s[l]] += 1
l += 1
if not result or r-l+1 < len(result):
result = s[l:r+1]
return result
``````
• `nums = [1,3,-1,-3,5,3,6,7], k = 3` => `[3,3,5,5,6,7]`

• l, r pointers, Monotonic dec deque, store idx, pop everything smaller than current

• O(n) time, O(k) space
``````def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
result = []

q = deque()
l = 0
for r in range(len(nums)):
while q and nums[q[-1]] < nums[r]:
q.pop()

q.append(r)
if l > q[0]:
q.popleft()

if r-k+1 >= 0:
result.append(nums[q[0]])
l += 1

return result
``````

## Stack#

• 🅱️Valid Parentheses☀️: 💡

• `s = "()[]{}"` => `true`

• store last opened in stack, check stack empty at the end

• O(n) time, O(n) space
``````def isValid(self, s: str) -> bool:
stack = []
close_to_open = {"}": "{", ")": "(", "]": "["}
for p in s:
if p in close_to_open:
if not stack or close_to_open[p] != stack[-1]:
return False
stack.pop()
else:
stack.append(p)
return len(stack) == 0
``````
• 🗿Min Stack⛅: 💡

• `push(val)`, `pop()`, `top()`, `getMin()`

• stack, append((min_so_far, val)), `min_so_far = min(val, self.stack[-1][0])`

• O(1) time, O(n) space
``````def __init__(self):
self.stack = []

def push(self, val: int) -> None:
if not self.stack:
self.stack.append((val, val))
else:
min_so_far = min(val, self.stack[-1][0])
self.stack.append((min_so_far, val))

def pop(self) -> None:
return self.stack.pop()[1]

def top(self) -> int:
return self.stack[-1][1]

def getMin(self) -> int:
return self.stack[-1][0]
``````
• `tokens = ["2","1","+","3","*"]` => `9`

• `b, a = stack.pop(), stack.pop()``return stack[0]`

• O(n) time, O(n) space
``````def evalRPN(self, tokens: List[str]) -> int:
stack = []
operators = {
"+": lambda a,b: a+b,
"-": lambda a,b: a-b,
"*": lambda a,b: a*b,
"/": lambda a,b: int(a/b),
}
for t in tokens:
if t not in operators:
stack.append(int(t))
else:
b, a = stack.pop(), stack.pop()
stack.append(operators[t](a, b))
return stack[0]
``````
• `n = 3` => `["((()))","(()())","(())()","()(())","()()()"]`

• stack, backtracking, dfs(opened, closed), `if opened < n`, `if closed < opened`

• O(2^(2n)) time, O(n) space
``````def generateParenthesis(self, n: int) -> List[str]:
result = []
path = []

def dfs(opened, closed):
if opened == closed == n:
result.append("".join(path))
return
if opened < n:
path.append("(")
dfs(opened+1, closed)
path.pop()

if closed < opened:
path.append(")")
dfs(opened, closed+1)
path.pop()

dfs(0, 0)
return result
``````
• `T = [73,74,75,71,69,72,76,73]` => `[1,1,4,2,1,1,0,0]`

• init result = [0]*len, stack of pending, while tmp[i] > tmp[stack[-1]], pop and update

• O(n) time, O(n) space
``````def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
result = [0]*len(temperatures)
pending = []
for i, t in enumerate(temperatures):
while pending and temperatures[pending[-1]] < t:
prev = pending.pop()
result[prev] = i-prev
pending.append(i)
return result
``````
• 🗿Car fleet⛅: 💡

• `target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]` => `3`

• Sort by position, start from end, calculate time to reach, ignore if faster

• O(nlogn) time, O(n) space
``````def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
stack = []
for p, s in sorted([(p,s) for p, s in zip(position, speed)], reverse=True):
time = (target-p)/s
if stack and time <= stack[-1]:
continue
stack.append(time)
return len(stack)
``````
• `heights = [2,1,5,6,2,3]` => `10`

• stack.append((start, h)), if decreasing, pop and update maxArea and current start

• O(n) time, O(n) space
``````def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
stack = []

for i, h in enumerate(heights):
start = i
# found a decrease in height
while stack and stack[-1][1] > h:
index, height = stack.pop()
maxArea = max(maxArea, height * (i - index))
start = index  # we can start from the leftmost index that is higher
stack.append((start, h))

for i, h in stack:
maxArea = max(maxArea, h * (len(heights) - i))
return maxArea
``````

Remember it can be used on a range of values

• 🗿Binary Search☀️: 💡

• `nums = [-1,0,3,5,9,12], target = 9` => `4`

• while l <= r, mid = (l+r)//2

• O(logn) time, O(1) space
``````def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)-1
while l <= r:
mid = (l+r)//2
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return -1
``````
• `matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3` => `true`

• calculate `row = mid // len(matrix[0])`, `col = mid % len(matrix[0])`

• O(logmn) time, O(1) space
``````def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
l, r = 0, len(matrix)*len(matrix[0])-1
while l <= r:
mid = (l+r)//2
row = mid // len(matrix[0])
col = mid % len(matrix[0])
if matrix[row][col] == target:
return True
if matrix[row][col] < target:
l = mid+1
else:
r = mid-1
return False
``````
• `piles = [3,6,7,11], H = 8` => `4`

• binary search over speed, `l, r = 1, max(piles)`

• O(nlogm) time, O(1) space
``````def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
result = r
while l <= r:
mid = (l+r)//2
hours = sum(math.ceil(p/mid) for p in piles)
if hours <= h:
result = min(result, mid)
r = mid-1
else:
l = mid+1
return result
``````
• `nums = [4,5,6,7,0,1,2], target = 0` => `4`

• see which side is sorted and then `if target > nums[mid] or target < nums[l]`

• O(logn) time, O(1) space
``````def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)-1

while l <= r:
mid = (l+r) // 2
if target == nums[mid]:
return mid

if nums[l] <= nums[mid]:
if nums[l] <= target <= nums[mid]:
r = mid-1
else:
l = mid+1

else:
if nums[mid] <= target <= nums[r]:
l = mid+1
else:
r = mid-1
return -1
``````
• `nums = [3,4,5,1,2]` => `1`

• stop `if nums[l] < nums[r]`, move `l` if `nums[mid] >= nums[l]`

• O(logn) time, O(1) space
``````def findMin(self, nums: List[int]) -> int:
start, end = 0, len(nums)-1
curr_min = float("inf")

while start < end:
mid = (start+end) // 2
curr_min = min(curr_min, nums[mid])

if nums[mid] > nums[end]:
start = mid + 1
else:
end = mid - 1

return min(curr_min, nums[start])
``````
• `set(k, v, time)`, `get(k, time)`

• `if values[m][1] <= timestamp: res = values[m][0], l = m + 1`

• O(logn) time, O(n) space
``````def __init__(self):
self.store = {}

def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.store:
self.store[key] = []
self.store[key].append((value, timestamp))

def get(self, key: str, timestamp: int) -> str:
if key not in self.store:
return ""
res = ""
values = self.store[key]
l, r = 0, len(values)-1
while l <= r:
m = (l+r)//2
if values[m][1] <= timestamp:
res = values[m][0]
l = m+1
else:
r = m-1
return res
``````
• `nums1 = [1,2], nums2 = [3,4]` => `2.5`

• Binary search on the shorter array until `Aleft <= Bright and Bleft <= Aright`.

• O(log(m+n)) time, O(1) space
``````def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A, B = nums1, nums2
total = len(nums1) + len(nums2)
half = total // 2

if len(B) < len(A):
A, B = B, A

l, r = 0, len(A) - 1
while True:
i = (l + r) // 2  # A
j = half - i - 2  # B

Aleft = A[i] if i >= 0 else float("-inf")
Aright = A[i + 1] if (i + 1) < len(A) else float("inf")
Bleft = B[j] if j >= 0 else float("-inf")
Bright = B[j + 1] if (j + 1) < len(B) else float("inf")

# partition is correct
if Aleft <= Bright and Bleft <= Aright:
# odd
if total % 2:
return min(Aright, Bright)
# even
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright:
r = i - 1
else:
l = i + 1
``````

• 🅱️Reverse Linked List☀️: 💡

• `head = [1,2]` => `[2,1]`

• store previous, save cur.next in temp

• O(n) time, O(1) space
``````def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None

while cur:
next_cur = cur.next
cur.next = prev
prev = cur
cur = next_cur
return prev
``````
• `l1 = [1,2,4], l2 = [1,3,4]` => `[1,1,2,3,4,4]`

• dummy first node, curr node, while l1 and l2, add remaining

• O(n) time, O(1) space
``````def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
p1 = list1
p2 = list2
dummy = ListNode()
cur = dummy

while p1 and p2:
if p1.val > p2.val:
p1, p2 = p2, p1
cur.next = p1
cur = cur.next
p1 = p1.next

if p1: cur.next = p1
if p2: cur.next = p2

return dummy.next
``````
• `lists = [[1,4,5],[1,3,4],[2,6]]` => `[1,1,2,3,4,4,5,6]`

• Merge two lists at a time, `for i in range(0, len(lists), 2)`

• O(nlogk) time, O(1) space
``````def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists or len(lists) == 0:
return None

while len(lists) > 1:
mergedLists = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if (i + 1) < len(lists) else None
mergedLists.append(self.mergeList(l1, l2))
lists = mergedLists
return lists[0]
``````
• `head = [1,2,3,4]` => `[1,4,2,3]` (L0 -> Ln -> L1 -> Ln-1 -> L2…)

• find mid, reverse second half, merge two lists

• O(n) time, O(1) space
``````def reorderList(self, head: Optional[ListNode]) -> None:
while fast and fast.next:
slow = slow.next
fast = fast.next.next

p2 = self.reverse(slow)
# merge
while p1 and p2:
tmp1 = p1.next
tmp2 = p2.next
p1.next = p2
p2.next = tmp1
p1 = tmp1
p2 = tmp2

def reverse(self, node):
...
``````
• `head = [1,2,3,4,5], n = 2` => `[1,2,3,5]`

• Two pointers, move one n steps ahead.

• O(n) time, O(1) space
``````def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
fast = slow = head
for _ in range(n):
fast = fast.next
if not fast:
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
``````
• `head = [[3,null],[3,0],[3,null]]` => `[[3,null],[3,0],[3,null]]`

• `old_to_new = {None: None}`, two passes, copy and then update next and random

• O(n) time, O(n) space
``````def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
old_to_new = {None: None}
while cur:
copy = Node(cur.val)
old_to_new[cur] = copy
cur = cur.next

while cur:
copy = old_to_new[cur]
copy.next = old_to_new[cur.next]
copy.random = old_to_new[cur.random]
cur = cur.next
``````
• 🗿 🏢Add Two Numbers⛅: 💡

• `l1 = [2,4,3], l2 = [5,6,4]` => `[7,0,8]`

• carry = sum_ // 10, remain = p1 or p2, etc.

• O(max(m,n)) time, O(max(m,n)) space
``````def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
carry = 0
while l1 or l2 or carry:
cur.next = ListNode()
cur = cur.next
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
cur.val = v1 + v2 + carry
if cur.val >= 10:
cur.val = cur.val % 10
carry = 1
else:
carry = 0
if l1: l1 = l1.next
if l2: l2 = l2.next
``````
• 🅱️Linked List Cycle☀️: 💡

• `head = [3,2,0,-4], -4 -> 2` => `true`

• Floyd’s Tortoise and hare / hashset of seen

• O(n) time, O(1) space
``````def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: return True
return False

def hasCycle(self, head: Optional[ListNode]) -> bool:
seen = set()
if id(head) in seen: return True
return False
``````
• `nums = [1,3,4,2,2]` => `2`

• Floyd’s cycle detection, `slow = nums[slow]; fast = nums[nums[fast]]`, slow2

• O(n) time, O(1) space
``````def findDuplicate(self, nums: List[int]) -> int:
slow, fast = 0, 0
while True :
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break

slow2 = 0
while True:
slow = nums[slow]
slow2 = nums[slow2]
if slow == slow2:
return slow
``````
• 🗿LRU Cache⛅: 💡

• `LRUCache(int capacity)`, `get(int key)`, `put(int key, int value)`

• double linked list (easy remove/insertion), dict key -> node, dummy head and tail

• O(1) time, O(capacity) space
``````def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}

self.left = Node(0, 0)
self.right = Node(0, 0)
self.left.next = self.right
self.right.prev = self.left

def get(self, key: int) -> int:
if key in self.cache:
self.remove(self.cache[key])
self.insert(self.cache[key])
return self.cache[key].val
return -1

def put(self, key: int, value: int) -> None:
if key in self.cache:
self.remove(self.cache[key])
self.cache[key] = Node(key, value)
self.insert(self.cache[key])

if len(self.cache) > self.cap:
lru = self.left.next
self.remove(lru)
del self.cache[lru.key]

def remove(self, node):
prev, nxt = node.prev, node.next
prev.next, nxt.prev = nxt, prev

def insert(self, node):
prev, nxt = self.right.prev, self.right
prev.next = node
self.right.prev = node
node.next = nxt
node.prev = prev
``````
• `head = [1,2,3,4,5], k = 2` => `[2,1,4,3,5]`

• groupPrev, groupNext, reverse `while curr != groupNext`

• O(n) time, O(1) space
``````def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
count = 0
while node and count < k:
node = node.next
count += 1
if count < k:
return prev

def reverse(self, head, count):
prev = None
while count > 0:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
count -= 1
return curr, prev
``````

## Trees#

Careful with recursion limit (bound to the application stack)

• 🅱️Invert Binary Tree☀️: 💡

• `root = [4,2,7,1,3,6,9]` => `[4,7,2,9,6,3,1]`

• `r.right, r.left = self.invert(r.left), self.invert(r.right)` or stack

• O(n) time, O(height) space
``````def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = [root]
while stack:
node = stack.pop()
if node is None: continue
node.left, node.right = node.right, node.left
stack.append(node.left)
stack.append(node.right)
return root

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
``````
• `root = [3,9,20,null,null,15,7]` => `3`

• `return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1`

• O(n) time, O(height) space
``````def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
``````
• `root = [1,2,3,4,5]` => `3`

• def dfs(node) that returns depth, update global diameter

• O(n) time, O(height) space
``````def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0
self.dfs(root)
return self.diameter

def dfs(self, node):
if not node:
return 0
left = self.dfs(node.left)
right = self.dfs(node.right)
self.diameter = max(self.diameter, left+right)
return 1 + max(left, right)
``````
• `root = [3,9,20,null,null,15,7]` => `true`

• def dfs(node) that returns depth, update global balanced

• O(n) time, O(height) space
``````def isBalanced(self, root):
self.bal = True
self.dfs(root)
return self.bal

def dfs(self, node):
if not node: return 0
lft, rgh = self.dfs(node.left), self.dfs(node.right)
if abs(lft - rgh) > 1: self.bal = False
return max(lft, rgh) + 1
``````
• 🅱️Same Tree☀️: 💡

• `p = [1,2,3], q = [1,2,3]` => `true`

• check None, check val and recursive call

• O(n) time, O(height) space
``````def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None and q is None:
return True
if p is None or q is None:
return False
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
``````
• `s = [3,4,5,1,2], t = [4,1,2]` => `true`

• `isSameTree(s, t) or isSubtree(s.left, t) or isSubtree(s.right, t)`

• O(n*m) time, O(n+m) space
``````def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not root:
return False
if self.is_same_tree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
``````
• `root = [3,9,20,null,null,15,7]` => `[[3],[9,20],[15,7]]`

• `while level: ans.append([node.val for node in level]); level = [...]` or queue

• O(n) time, O(n) space
``````def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
level = [root]
result = []
while level:
new_level = []
level = [l for l in level if l]
if level:
result.append([n.val for n in level])
for n in level:
new_level.append(n.left)
new_level.append(n.right)
level = new_level
return result
``````
• `root = [1,2,3,null,5,null,4]` => `[1,3,4]`

• Level order, right most

• O(n) time, O(n) space
``````def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []

result = []
level = [root]
while level:
result.append(level[-1].val)
new_level = []
for n in level:
if n.left:
new_level.append(n.left)
if n.right:
new_level.append(n.right)
level = new_level
return result
``````
• `root = [3,1,4,3,null,1,5]` => `4`

• dfs, stack = [(node, max_so_far)]

• O(n) time, O(height) space
``````def goodNodes(self, root: TreeNode) -> int:
if not root:
return 0

result = 0
def dfs(node, max_so_far):
nonlocal result
if not node:
return

max_so_far = max(max_so_far, node.val)
if node.val >= max_so_far:
result += 1

dfs(node.left, max_so_far)
dfs(node.right, max_so_far)

dfs(root, root.val)
return result
``````
• `preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]` => `[3,9,20,null,null,15,7]`

• recursive, pop(0) from preorder, find index in inorder, split inorder

• O(n^2) time, O(n) space
``````def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return
ind = inorder.index(preorder.pop(0))  # optimize with deque
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder, inorder[:ind])
root.right = self.buildTree(preorder, inorder[ind+1:])
return root
``````
• `root = [1,2,3]` => `6`

• dfs, allow split or not, nonlocal max

• O(n) time, O(height) space
``````def maxPathSum(self, root: Optional[TreeNode]) -> int:
max_path = float("-inf")
def get_max_gain(node):
nonlocal max_path
if node is None:
return 0

gain_on_left = max(get_max_gain(node.left), 0)
gain_on_right = max(get_max_gain(node.right), 0)
current_max_path = node.val + gain_on_left + gain_on_right
max_path = max(max_path, current_max_path)

return node.val + max(gain_on_left, gain_on_right)

get_max_gain(root)
return max_path
``````
• `serialize(self, root)` and `deserialize(self, data)`

• Preorder travelsal, `"1,2,N,N,3,4,N,N,5,N,N"`

• O(n) time, O(n) space
``````def serialize(self, root):
values = []
def preorder(node):
if node:
values.append(str(node.val))
preorder(node.left)
preorder(node.right)
else:
values.append('#')
preorder(root)
return ' '.join(values)

def deserialize(self, data):
values = list(reversed(data.split()))
def preorder():
value = values.pop()
if value == '#':
return None
node = TreeNode(int(value))
node.left = preorder()
node.right = preorder()
return node
return preorder()
``````

BST: nodes left < node < nodes right

• `root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8` => `6`

• cur, left `if p<cur and q<cur`, right `if p>cur and q>cur` else return

• O(n) time, O(1) space
``````def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur = root
while cur:
if p.val < cur.val and q.val < cur.val:
cur = cur.left
elif p.val > cur.val and q.val > cur.val:
cur = cur.right
else:
return cur
``````
• `root = [2,1,3]` => `true`

• `validate(n.left, min_val, n.val) and validate(n.right, n.val, max_val)`

• O(n) time, O(height) space
``````def isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.validate(root)

def validate(self, node, min_val=None, max_val=None):
if not node:
return True
if min_val is not None and node.val <= min_val:
return False
if max_val is not None and node.val >= max_val:
return False
return self.validate(node.left, min_val, node.val) and self.validate(node.right, node.val, max_val)
``````
• `root = [3,1,4,null,2], k = 1` => `1`

• inorder traversal, return res[k-1] (or iterative inorder with stack)

• O(n) time, O(height) space
`````` def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
count = []
self.helper(root, count)
return count[k-1]

def helper(self, node, count):
if not node:
return

self.helper(node.left, count)
count.append(node.val)
self.helper(node.right, count)
``````

## Tries#

• `insert(word)`, `search(word)`, `startsWith(prefix)`

• TrieNode has `children` dict and `end` bool

• O(n) time, O(n) space
``````class TrieNode:
def __init__(self):
self.children = {}
self.end = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word: str) -> None:
curr = self.root
for c in word:
if c not in curr.children:
curr.children[c] = TrieNode()
curr = curr.children[c]
curr.end = True

def search(self, word: str) -> bool:
curr = self.root
for c in word:
if c not in curr.children:
return False
curr = curr.children[c]
return curr.end

def startsWith(self, prefix: str) -> bool:
curr = self.root
for c in prefix:
if c not in curr.children:
return False
curr = curr.children[c]
return True
``````
• `addWord(word)`, `search(word)`

• trie, recursive dfs(idx, node) for “.”

• O(c) time, O(c) space
``````
class TrieNode:
def __init__(self):
self.children = {}  # a : TrieNode
self.word = False

class WordDictionary:
def __init__(self):
self.root = TrieNode()

def addWord(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.word = True

def search(self, word: str) -> bool:
def dfs(j, root):
cur = root

for i in range(j, len(word)):
c = word[i]
if c == ".":
for child in cur.children.values():
if dfs(i + 1, child):
return True
return False
else:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.word

return dfs(0, self.root)
``````
• 🅱️Word Search II⛈️ 💡

• `board, words = ["oath","pea","eat","rain"]` => `["eat","oath"]`

• build words trie from each cell, dfs

• O(mn\4^mn) time, O(n) space
``````class TrieNode:
def __init__(self):
self.children = {}
self.isWord = False
self.refs = 0

cur = self
cur.refs += 1
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.refs += 1
cur.isWord = True

def removeWord(self, word):
cur = self
cur.refs -= 1
for c in word:
if c in cur.children:
cur = cur.children[c]
cur.refs -= 1

class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:

ROWS, COLS = len(board), len(board[0])
res, visit = set(), set()

def dfs(r, c, node, word):
if (
r not in range(ROWS)
or c not in range(COLS)
or board[r][c] not in node.children
or node.children[board[r][c]].refs < 1
or (r, c) in visit
):
return

node = node.children[board[r][c]]
word += board[r][c]
if node.isWord:
node.isWord = False
root.removeWord(word)

dfs(r + 1, c, node, word)
dfs(r - 1, c, node, word)
dfs(r, c + 1, node, word)
dfs(r, c - 1, node, word)
visit.remove((r, c))

for r in range(ROWS):
for c in range(COLS):
dfs(r, c, root, "")

return list(res)
``````

## Heap & Priority Queue#

• Binary Tree
• Heap invariant: each node is <= than its children.
• Implemented as array: root at `0`, children `2i+1` & `2i+2`, parent at `(i-1)//2`
• `KthLargest(int k, int[] nums)`, `add(num) -> int`

• simple minheap, pop if len > k, return heap[0]

• O(logk) time, O(k) space
``````def __init__(self, k: int, nums: List[int]):
heapq.heapify(nums) # O(n)
self.heap = nums
self.k = k

def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
while len(self.heap) > self.k:
heapq.heappop(self.heap) # O(logk)
return self.heap[0]
``````
• `stones = [2,7,4,1,8,1]` => `1`

• Heapify, pop 2 largest, push diff, repeat while len > 1

• O(nlogn) time, O(n) space
``````def lastStoneWeight(self, stones: List[int]) -> int:
result = [-s for s in stones]
heapq.heapify(result) # n
while len(result) > 1: # n times
y = heapq.heappop(result)  # logn
x = heapq.heappop(result)
if x != y:
heapq.heappush(result, y-x) # logn
# nlogn
return -result[0] if result else 0
``````
• `points = [[1,3],[-2,2]], K = 1` => `[[-2,2]]`

• simple maxheap (-dist, x, y), pop if len > k

• O(nlogk) time, O(k) space
``````def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
heap = []
for (x, y) in points:
dist = -(x*x + y*y)
if len(heap) == K:
heapq.heappushpop(heap, (dist, x, y))
else:
heapq.heappush(heap, (dist, x, y))
return [(x,y) for (dist,x, y) in heap]
``````
• `nums = [3,2,1,5,6,4], k = 2` => `5`

• quickselect,

• O(n) avg time, O(n) space
``````def findKthLargest(self, nums, k):
if not nums: return
pivot = random.choice(nums)
left =  [x for x in nums if x > pivot]
mid  =  [x for x in nums if x == pivot]
right = [x for x in nums if x < pivot]

L, M = len(left), len(mid)

if k <= L:
return self.findKthLargest(left, k)
elif k > L + M:
return self.findKthLargest(right, k - L - M)
else:
return mid[0]
``````
• `tasks = ["A","A","A","B","B","B"], n = 2` => `8`

• max_heap of times, queue, `while max_heap or q`, increase time

• O(n) time, O(n) space
``````def leastInterval(self, tasks: List[str], n: int) -> int:
maxHeap = [-cnt for cnt in count.values()]
heapq.heapify(maxHeap)  # O(n)

time = 0
q = deque()  # pairs of [-cnt, idleTime]
while maxHeap or q:
time += 1

if not maxHeap:
time = q[0][1]
else:
cnt = 1 + heapq.heappop(maxHeap)
if cnt:
q.append([cnt, time + n])
if q and q[0][1] == time:
heapq.heappush(maxHeap, q.popleft()[0])
return time
``````
• `postTweet`, `getNewsFeed`, `follow`, `unfollow`

• heap, followerset per user, tweetmap per user

• O(nlogn) time, O(n) space
``````def __init__(self):
self.count = 0
self.tweetMap = defaultdict(list)  # userId -> list of [count, tweetIds]
self.followMap = defaultdict(set)  # userId -> set of followeeId

def postTweet(self, userId: int, tweetId: int) -> None:
self.tweetMap[userId].append([self.count, tweetId])
self.count -= 1

def getNewsFeed(self, userId: int) -> List[int]:
res = []
minHeap = []

for followeeId in self.followMap[userId]:
if followeeId in self.tweetMap:
index = len(self.tweetMap[followeeId]) - 1
count, tweetId = self.tweetMap[followeeId][index]
heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

while minHeap and len(res) < 10:
count, tweetId, followeeId, index = heapq.heappop(minHeap)
res.append(tweetId)
if index >= 0:
count, tweetId = self.tweetMap[followeeId][index]
heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])
return res

def follow(self, followerId: int, followeeId: int) -> None:

def unfollow(self, followerId: int, followeeId: int) -> None:
if followeeId in self.followMap[followerId]:
self.followMap[followerId].remove(followeeId)
``````
• `addNum(num)` and `findMedian()`

• 2 heaps, max heap for left, min heap for right, balance

• O(logn) time, O(n) space
``````class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
# two heaps, large, small, minheap, maxheap
# heaps should be equal size
self.small, self.large = [], []  # maxHeap, minHeap (python default)

def addNum(self, num: int) -> None:
if self.large and num > self.large[0]:
heapq.heappush(self.large, num)
else:
heapq.heappush(self.small, -1 * num)

if len(self.small) > len(self.large) + 1:
val = -1 * heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small) + 1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -1 * val)

def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -1 * self.small[0]
elif len(self.large) > len(self.small):
return self.large[0]
return (-1 * self.small[0] + self.large[0]) / 2
``````

## Backtracking#

• Subsets:
• append to path, dfs, pop, dfs
• if don’t want duplicates while loop to increase idx before second dfs
• Combinations:
``````for j in range(i, n+1):
path.append(j)
dfs(j+1)
path.pop()
``````
• Permutations:
``````def backtrack(first = 0):
if first == n:
output.append(nums[:])
for i in range(first, n):
nums[first], nums[i] = nums[i], nums[first]
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first]
``````

• 🗿Subsets⛅: 💡

• `nums = [1,2,3]` => `[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]`

• dfs with backtracking, result and path

• O(n*2^n) time, O(n) space
``````def subsets(self, nums: List[int]) -> List[List[int]]:
result = []

path = []
def dfs(i):
if i == len(nums):
result.append(path[:])
return

path.append(nums[i])
dfs(i+1)
path.pop()
dfs(i+1)

dfs(0)
return result
``````
• `candidates = [2,3,6,7], target = 7` => `[[7],[2,2,3]]`

• dfs, backtracking, append path to global res

• O(2^target) time, O(target) space
``````def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []

path = []
def dfs(i, t):
if t == 0:
result.append(path[:])
return
if i >= len(candidates) or t < 0:
return

path.append(candidates[i])
dfs(i, t-candidates[i])
path.pop()
dfs(i+1, t)

dfs(0, target)
return result
``````
• `nums = [1,2,3]` => `[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`

• stack of

• O(n*n!) time, O(n!) space
``````def permute(self, nums: List[int]) -> List[List[int]]:
stack = [(nums, [])]
res = []
while stack:
nums, path = stack.pop()
if not nums:
res.append(path)
continue
for i in range(len(nums)):
stack.append((nums[:i] + nums[i+1:], path+[nums[i]]))
return res
``````
• 🗿Subsets II⛅: 💡

• `nums = [1,2,2]` => `[[2],[1],[1,2,2],[2,2],[1,2],[]]`

• sort, `while i+1 < len(nums) and nums[i] == nums[i+1]:`

• O(n*2^n) time, O(n) space
``````def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()

def backtrack(i, subset):
if i == len(nums):
res.append(subset[::])
return

# All subsets that include nums[i]
subset.append(nums[i])
backtrack(i + 1, subset)
subset.pop()
# All subsets that don't include nums[i]
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
i += 1
backtrack(i + 1, subset)

backtrack(0, [])
return res
``````
• `candidates = [10,1,2,7,6,1,5], target = 8` => `[[1,1,6],[1,2,5],[1,7],[2,6]]`

• dfs(pos, target), path = [], top if target <= 0

• O(2^n) time, O(n) space
``````def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()

res = []

def backtrack(cur, pos, target):
if target == 0:
res.append(cur.copy())
return
if target <= 0:
return

prev = -1
for i in range(pos, len(candidates)):
if candidates[i] == prev:
continue
cur.append(candidates[i])
backtrack(cur, i + 1, target - candidates[i])
cur.pop()
prev = candidates[i]

backtrack([], 0, target)
return res
``````
• 🅱️Word Search💡

• `board = [["A","B","C","E"],["S","F","C","S"],...], word = "ABCCED"` => `true`

• dfs, backtracking, mark visited

• O(mn\*4^l) time, O(l) space
``````def exist(self, board: List[List[str]], word: str) -> bool:
ROWS, COLS = len(board), len(board[0])
path = set()

def dfs(r, c, i):
if i == len(word):
return True
if (
min(r, c) < 0
or r >= ROWS
or c >= COLS
or word[i] != board[r][c]
or (r, c) in path
):
return False
res = (
dfs(r + 1, c, i + 1)
or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1)
or dfs(r, c - 1, i + 1)
)
path.remove((r, c))
return res

# To prevent TLE,reverse the word if frequency of the first letter is more than the last letter's
count = defaultdict(int, sum(map(Counter, board), Counter()))
if count[word[0]] > count[word[-1]]:
word = word[::-1]

for r in range(ROWS):
for c in range(COLS):
if dfs(r, c, 0):
return True
return False

# O(n * m * 4^n)
``````
• `s = "aab"` => `[["a","a","b"],["aa","b"]]`

• res = [], path = [], dfs(pos), for j in range(i, len(s))

• O(n*2^n) time, O(n) space
`````` def partition(self, s: str) -> List[List[str]]:
res, part = [], []

def dfs(i):
if i >= len(s):
res.append(part.copy())
return
for j in range(i, len(s)):
if self.isPali(s, i, j):
part.append(s[i : j + 1])
dfs(j + 1)
part.pop()

dfs(0)
return res

def isPali(self, s, l, r):
while l < r:
if s[l] != s[r]:
return False
l, r = l + 1, r - 1
return True
``````
• `digits = "23"` => `["ad","ae","af","bd","be","bf","cd","ce","cf"]`

• digit_to_char map, dfs, backtracking

• O(n*4^n) time, O(n) space
``````def letterCombinations(self, digits: str) -> List[str]:
res = []
digitToChar = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "qprs",
"8": "tuv",
"9": "wxyz",
}

def backtrack(i, curStr):
if len(curStr) == len(digits):
res.append(curStr)
return
for c in digitToChar[digits[i]]:
backtrack(i + 1, curStr + c)

if digits:
backtrack(0, "")

return res
``````
• 🗿N Queens⛈️: 💡

• `n = 4` => `[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]`

• dfs(row): for c in range(n), col, pos_diag, neg_diag sets

• O(n!) time, O(n²) space
``````def solveNQueens(self, n: int) -> List[List[str]]:
col = set()
posDiag = set()  # (r + c)
negDiag = set()  # (r - c)

res = []
board = [["."] * n for i in range(n)]

def backtrack(r):
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return

for c in range(n):
if c in col or (r + c) in posDiag or (r - c) in negDiag:
continue

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
``````

## Graphs#

• Dijkstra’s Algorithm: shortest path algo, greedy, O(ElogV) time

``````shortest = {}
heap = [(0, src)]
while heap:
w, node = heapq.heappop(heap)
if node in shortest:
continue
shortest[node] = w
for d, w2 in adj[node]:
if d not in shortest:
heapq.heappush(heap, (w + w2, d))
``````
• Prim’s Algorithm: MST, O(ElogV) time, O(V) space

``````heap = []
for n, w in adj[0]:
heapq.heappush(heap, (w, 0, n))
visited = set()
while heap:
w, s, d = heapq.heappop(heap)
if d in visited:
continue
mst.append((s, d))
for n, w2 in adj[d]:
if n not in visited:
heapq.heappush(heap, (w2, d, n))
``````
• Kruskal: Union Find

• Topological Sort: Alien dict, dfs to the end and reverse, O(V+E) time, O(V) space

### Basic#

• 🅱️🏢Number of Islands⛅: 💡

• `grid = [["1", "0"], ["0", "1"]]` => `2`

• skip visited (mark 0 or set), dfs (4 directions) on 1s.

• O(cells) time, O(cells) space
``````def numIslands(self, grid: List[List[str]]) -> int:
result = 0

visited = set()
def dfs(i, j):
if (i, j) in visited: return
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]): return
if grid[i][j] != "1": return
for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
dfs(ii, jj)

for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1" and (i, j) not in visited:
result += 1
dfs(i, j)

return result
``````
• 🅱️Clone Graph⛅: 💡

• Node with val, neighbors.

• cache[old] = copy, for n in neighbors: copy.neighbors.append(dfs(n))).

• O(v+e) time, O(v) space
``````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
``````
• 🗿 🏢Max Area of Island⛅: 💡

• `grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],...,[0,0,0,0,0,0,0,1,1,1,0,0,0]]` => `6`

• return 1 + dfs(4 directions), max_area = max(max_area, dfs)

• O(mn) time, O(mn) space
``````def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
visit = set()

def dfs(r, c):
if (
r < 0
or r == ROWS
or c < 0
or c == COLS
or grid[r][c] == 0
or (r, c) in visit
):
return 0
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)

area = 0
for r in range(ROWS):
for c in range(COLS):
area = max(area, dfs(r, c))
return area
``````
• grid of heights.

• start from edge and dfs(x, y, ocean, last_height) to higher, return set intersection

• O(mn) time, O(mn) space
``````def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
pacific = set()
atlantic = set()

for i in range(len(heights)):
for j in range(len(heights[0])):
if i == 0 or j == 0:
if i == len(heights)-1 or j == len(heights[0])-1:

# pacific
stack = list(pacific)
while stack:
i, j = stack.pop()
for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
if (ii, jj) in pacific:
continue
if self.is_valid(ii, jj, heights) and heights[ii][jj] >= heights[i][j]:
stack.append((ii, jj))

stack = list(atlantic)
while stack:
i, j = stack.pop()
for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
if (ii, jj) in atlantic:
continue
if self.is_valid(ii, jj, heights) and heights[ii][jj] >= heights[i][j]:
stack.append((ii, jj))

return list(pacific.intersection(atlantic))

def is_valid(self, i, j, heights):
return 0 <= i <= (len(heights)-1) and 0 <= j <= (len(heights[0])-1)
``````
• `board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]`

• dfs regions connected to edge, mark temporary, flip rest.

• O(mn) time, O(1) space
``````def solve(self, board: List[List[str]]) -> None:
ROWS, COLS = len(board), len(board[0])

def capture(r, c):
if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":
return
board[r][c] = "T"
capture(r + 1, c)
capture(r - 1, c)
capture(r, c + 1)
capture(r, c - 1)

# 1. (DFS) Capture unsurrounded regions (O -> T)
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
capture(r, c)

# 2. Capture surrounded regions (O -> X)
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == "O":
board[r][c] = "X"

# 3. Uncapture unsurrounded regions (T -> O)
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == "T":
board[r][c] = "O"
``````
• `grid = [[2,1,1],[1,1,0],[0,1,1]]` => `4`

• BFS, `while queue: minutes+=1 for i in range(len(queue))`, check if any remain

• O(nm) time, O(nm) space
``````def orangesRotting(self, grid: List[List[int]]) -> int:
q = collections.deque()
fresh = 0
time = 0

for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == 1:
fresh += 1
if grid[r][c] == 2:
q.append((r, c))

directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
while fresh > 0 and q:
length = len(q)
for i in range(length):
r, c = q.popleft()

for dr, dc in directions:
row, col = r + dr, c + dc
# if in bounds and nonrotten, make rotten
# and add to q
if (
row in range(len(grid))
and col in range(len(grid[0]))
and grid[row][col] == 1
):
grid[row][col] = 2
q.append((row, col))
fresh -= 1
time += 1
return time if fresh == 0 else -1
``````
• `rooms = [[2147483647,-1,0,2147483647],...,[2147483647,2147483647,2147483647,-1]]`

• BFS, `while queue` pop left, add to queue if `rooms[r][c] > rooms[i][j]+1`

• O(nm) time, O(nm) space
``````def walls_and_gates(self, rooms: List[List[int]]):
ROWS, COLS = len(rooms), len(rooms[0])
visit = set()
q = deque()

if (
min(r, c) < 0
or r == ROWS
or c == COLS
or (r, c) in visit
or rooms[r][c] == -1
):
return
q.append([r, c])

for r in range(ROWS):
for c in range(COLS):
if rooms[r][c] == 0:
q.append([r, c])

dist = 0
while q:
for i in range(len(q)):
r, c = q.popleft()
rooms[r][c] = dist
addRooms(r + 1, c)
addRooms(r - 1, c)
addRooms(r, c + 1)
addRooms(r, c - 1)
dist += 1
``````
• 🅱️Course Schedule⛅: 💡

• DFS cycle detection (visited set, cycle set).

• O(v+e) time, O(v) space
``````def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# dfs
preMap = {i: [] for i in range(numCourses)}

# map each course to : prereq list
for crs, pre in prerequisites:
preMap[crs].append(pre)

visiting = set()

def dfs(crs):
if crs in visiting:
return False
if preMap[crs] == []:
return True

for pre in preMap[crs]:
if not dfs(pre):
return False
visiting.remove(crs)
preMap[crs] = []
return True

for c in range(numCourses):
if not dfs(c):
return False
return True
``````
• 🗿 🏢Course Schedule II⛅: 💡

• `numCourses = 2, prerequisites = [[1,0]]` => `[0,1]`

• DFS topological sort, return [] if cycle, visited and cycle set

• O(v+e) time, O(v) space
``````def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
prereq = {c: [] for c in range(numCourses)}
for crs, pre in prerequisites:
prereq[crs].append(pre)

output = []
visit, cycle = set(), set()

def dfs(crs):
if crs in cycle:
return False
if crs in visit:
return True

for pre in prereq[crs]:
if dfs(pre) == False:
return False
cycle.remove(crs)
output.append(crs)
return True

for c in range(numCourses):
if dfs(c) == False:
return []
return output
``````
• `edges = [[1,2], [1,3], [2,3]]` => `[2,3]`

• union find, return edge if cycle (parent(x) == parent(y))

• O(n) time, O(n) space / actually O(inv_ackerman(n))
``````def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
parents = {}

def find_parent(n):
y = parents.get(n, n)
if y != n:
y = find_parent(y)
parents[n] = y
return y

def union(n1, n2):
p1 = find_parent(n1)
p2 = find_parent(n2)
if p1 == p2:  # cycle
return False
parents[p1] = p2
return True

for n1, n2 in edges:
if not union(n1, n2):
return [n1, n2]
``````
• `n = 5, edges = [[0, 1], [1, 2], [3, 4]]` => `2`

• union find

• O(n+m) time, O(n) space
``````class UnionFind:
def __init__(self):
self.f = {}

def findParent(self, x):
y = self.f.get(x, x)
if x != y:
y = self.f[x] = self.findParent(y)
return y

def union(self, x, y):
self.f[self.findParent(x)] = self.findParent(y)

class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
dsu = UnionFind()
for a, b in edges:
dsu.union(a, b)
return len(set(dsu.findParent(x) for x in range(n)))
``````
• `n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]` => `true`

• adj list, DFS cycle detection, `dfs(0, prev=-1) and n == len(visit)`

• O(e+v) time, O(e+v) space
``````def validTree(self, n, edges):
if not n:
return True
adj = {i: [] for i in range(n)}
for n1, n2 in edges:

visit = set()

def dfs(i, prev):
if i in visit:
return False

for j in adj[i]:
if j == prev:
continue
if not dfs(j, i):
return False
return True

return dfs(0, -1) and n == len(visit)
``````
• 🗿Word Ladder⛈️: 💡

• `beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]` => `5`

• BFS, queue, create adj list with patterns `pattern = word[:i] + '*' + word[i+1:]`

• O(m^2*n) time, O(m^2*n) space
``````def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0

nei = collections.defaultdict(list)
wordList.append(beginWord)
for word in wordList:
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1 :]
nei[pattern].append(word)

visit = set([beginWord])
q = deque([beginWord])
res = 1
while q:
for i in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1 :]
for neiWord in nei[pattern]:
if neiWord not in visit:
q.append(neiWord)
res += 1
return 0
``````

• `tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]` => `["JFK","MUC","LHR","SFO","SJC"]`

• adj list, sort (lexico), dfs

• O(n_flights^max_airport_f) time, O(n_airports+n_flights) space
``````def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = {u: collections.deque() for u, v in tickets}
res = ["JFK"]

tickets.sort()
for u, v in tickets:

def dfs(cur):
if len(res) == len(tickets) + 1:
return True
if cur not in adj:
return False

for v in temp:
res.append(v)
if dfs(v):
return res
res.pop()
return False

dfs("JFK")
return res
``````
• `points = [[0,0],[2,2],[3,10],[5,2],[7,0]]` => `20`

• Prim’s algorithm, visited set, heappop cheapest edge

• O(ElogV) time, O(v) space
``````def minCostConnectPoints(self, points: List[List[int]]) -> int:
N = len(points)
adj = {i: [] for i in range(N)}  # i : list of [cost, node]
for i in range(N):
x1, y1 = points[i]
for j in range(i + 1, N):
x2, y2 = points[j]
dist = abs(x1 - x2) + abs(y1 - y2)

# Prim's
res = 0
visit = set()
minH = [[0, 0]]  # [cost, point]
while len(visit) < N:
cost, i = heapq.heappop(minH)
if i in visit: continue
res += cost
for neiCost, nei in adj[i]:
if nei not in visit:
heapq.heappush(minH, [neiCost, nei])
return res
``````
• `times = [[2,1,1],[2,3,1],[3,4,1]]`, `N = 4`, `K = 2` => `2`

• Dijkstra’s algorithm, visited set instead of dist

• O(elogv) time, O(e+v) space
``````def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
edges = collections.defaultdict(list)
for u, v, w in times:
edges[u].append((v, w))

minHeap = [(0, k)]
visit = set()
t = 0
while minHeap:
w1, n1 = heapq.heappop(minHeap)
if n1 in visit:
continue
t = w1

for n2, w2 in edges[n1]:
if n2 not in visit:
heapq.heappush(minHeap, (w1 + w2, n2))
return t if len(visit) == n else -1
``````
• 🗿 🏢Swim in Rising Water⛈️: 💡

• `grid = [[0,2],[1,3]]` => `3`

• Simple Dijkstra, `heapq.heappush(heap, (max(t, grid[r][c]), r, c))`

• O(n^2 log n) time, O(n^2) space
``````def swimInWater(self, grid: List[List[int]]) -> int:
N = len(grid)
visit = set()
minH = [[grid[0][0], 0, 0]]  # (time/max-height, r, c)
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

while minH:
t, r, c = heapq.heappop(minH)
if r == N - 1 and c == N - 1:
return t
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
if (
neiR < 0
or neiC < 0
or neiR == N
or neiC == N
or (neiR, neiC) in visit
):
continue
heapq.heappush(minH, [max(t, grid[neiR][neiC]), neiR, neiC])
``````
• 🅱️Alien Dictionary⛈️: 💡

• topological sort, DFS cycle detection.

• O(chars) time, O(chars) space
``````def alienOrder(self, words: List[str]) -> str:
adj = {char: set() for word in words for char in word}

for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minLen = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
return ""
for j in range(minLen):
if w1[j] != w2[j]:
break

res = []
path = set()
visited = set()
def dfs(char):
if char in path: return True  # cycle
if char in visited: return False

for neighChar in adj[char]:
if dfs(neighChar): return True  # cycle
path.remove(char)
res.append(char)

for char in adj:
if dfs(char):
return ""

res.reverse()
return "".join(res)
``````
• `n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]`, `src = 0`, `dst = 2`, `k = 1` => `200`

• BellmanFord, BFS (k+1 times), create `tmp_dist` and `distances = tmp_dist` at the end

• O(k\*e) time, O(k\*e) space
``````def findCheapestPrice(
self, n: int, flights: List[List[int]], src: int, dst: int, k: int
) -> int:
prices = [float("inf")] * n
prices[src] = 0

for i in range(k + 1):
tmpPrices = prices.copy()

for s, d, p in flights:  # s=source, d=dest, p=price
if prices[s] == float("inf"):
continue
if prices[s] + p < tmpPrices[d]:
tmpPrices[d] = prices[s] + p
prices = tmpPrices
return -1 if prices[dst] == float("inf") else prices[dst]
``````

## Dynamic Programming#

https://youtu.be/mBNrRy2_hVs

• Fibonacci: `dp[i] = dp[i-1] + dp[i-2]`
• Zero / One Knapsack:
• Unbounded Knapsack:
• Longest Common Subsequence:
• Palindromes:

### 1D#

https://youtu.be/_i4Yxeh5ceQ

• 🅱️Climbing Stairs☀️: 💡 Fibonacci

• `n = 2` => `2`, `n = 3` => `3`

• `temp = n1 + n2`

• O(n) time, O(1) space
``````def climbStairs(self, n: int) -> int:
prev1 = 1
prev2 = 1
for _ in range(2, n+1):
prev1, prev2 = prev2, prev1+prev2
return prev2
``````
• `cost = [10, 15, 20]` => `15` (start from 0 or 1, 1 or 2 steps)

• `new = min(prev1+c[i-2], prev2+c[i-1]); prev1 = prev2; prev2 = new`

• O(n) time, O(n) space
``````def minCostClimbingStairs(self, cost: List[int]) -> int:
a = 0
b = 0
# min_cost[i] -> min(min_cost[i-1]+cost[i-1], min_cost[i-2]+cost[i-2])
for i in range(2, len(cost)+1):
a, b = b, min(a+cost[i-2], b+cost[i-1])
return b
``````
• 🅱️House Robber⛅: 💡

• `nums = [2,7,9,3,1]` => `12` (2, 9, 1)

• `rob1, rob2 = 0, 0`, `tmp = max(rob1 + n, rob2)`, `return rob2`

• O(n) time, O(1) space
``````def rob(self, nums: List[int]) -> int:
rob1, rob2 = 0, 0
for n in nums:
temp = max(n+rob1, rob2)
rob1 = rob2
rob2 = temp
return rob2
``````
• 🅱️House Robber II⛅: 💡

• `nums = [2,3,2]` => `3` (circular)

• `max(nums[0], rob1(nums[1:]), rob1(nums[:-1]))`

• O(n) time, O(1) space
``````def rob(self, nums: List[int]) -> int:
return max(nums[0], self.helper(nums[1:]), self.helper(nums[:-1]))

def helper(self, nums):
rob1, rob2 = 0, 0

for n in nums:
newRob = max(rob1 + n, rob2)
rob1 = rob2
rob2 = newRob
return rob2
``````
• `s = "babad"` => `"bab"` or `"aba"`

• for i in range(len(s)): expand around l, r = 1, 1 and l, r = i, i+1

• O(n^2) time, O(1) space
``````def longestPalindrome(self, s: str) -> str:
res = ""
resLen = 0

for i in range(len(s)):
# odd length
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
if (r - l + 1) > resLen:
res = s[l : r + 1]
resLen = r - l + 1
l -= 1
r += 1

# even length
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
if (r - l + 1) > resLen:
res = s[l : r + 1]
resLen = r - l + 1
l -= 1
r += 1

return res
``````
• `s = "abc"` => `3` (a, b, c)

• similar to the previous one, expand and add to count

• O(n^2) time, O(1) space
``````def countSubstrings(self, s: str) -> int:
res = 0

for i in range(len(s)):
res += self.countPali(s, i, i)
res += self.countPali(s, i, i + 1)
return res

def countPali(self, s, l, r):
res = 0
while l >= 0 and r < len(s) and s[l] == s[r]:
res += 1
l -= 1
r += 1
return res
``````
• 🅱️Decode Ways⛅: 💡

• `s = "12"` => `2` (“AB” or “L”)

• start from end, `dp[i] = dp[i+1]` add `dp[i+2]` if `dp[i:i+2]` is valid

• O(n) time, O(n) space
``````def numDecodings(self, s: str) -> int:
dp = {len(s): 1}

def dfs(i):
if i in dp: return dp[i]
if s[i] == "0": return 0

res = dfs(i + 1)
if i + 1 < len(s) and (
s[i] in "12" and s[i + 1] in "0123456"
):
res += dfs(i + 2)
dp[i] = res
return res

return dfs(0)
``````
• 🅱️Coin Change⛅: 💡 Unbounded Knapsack

• `coins = [1,2,5], amount = 11` => `3`

• Cache and iterate `range(amount+1)`, recursive is O(coins^amount)

• O(coins*amount) time, O(amount) space
``````def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0

for a in range(1, amount + 1):
for c in coins:
if a - c >= 0:
dp[a] = min(dp[a], 1 + dp[a - c])
return dp[amount] if dp[amount] != amount + 1 else -1
``````
• `nums = [2,3,-2,4]` => `6` (2, 3)

• `cur_max, cur_min, max_prod = 1, 1, float('-inf')`, reset if n == 0

• O(n) time, O(1) space
``````def maxProduct(self, nums: List[int]) -> int:
# O(n)/O(1) : Time/Memory
res = nums[0]
curMin, curMax = 1, 1

for n in nums:

tmp = curMax * n
curMax = max(n * curMax, n * curMin, n)
curMin = min(tmp, n * curMin, n)
res = max(res, curMax)
return res
``````
• 🅱️Word Break⛅: 💡

• `s = "leetcode", words = ["leet", "code"]` => `true`

• set of words, `if word in wordSet and dp(end): return True`

• O(n^2) time, O(n) space
``````def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
wordSet = set(wordDict)

@lru_cache(None)
def dp(start):
if start == n:  # Found a valid way to break words
return True

for end in range(start + 1, n + 1):  # O(N^2)
word = s[start:end]  # O(N)
if word in wordSet and dp(end): return True
return False

return dp(0)
``````
• `nums = [10,9,2,5,3,7,101,18]` => `4` (2, 3, 7, 101) strict

• start from end, `if nums[i] < nums[j]: dp[i] = max(dp[i], dp[j] + 1)`

• O(n^2) time, O(n) space
``````def lengthOfLIS(self, nums: List[int]) -> int:
LIS = [1] * len(nums)

for i in range(len(nums) - 1, -1, -1):
for j in range(i + 1, len(nums)):
if nums[i] < nums[j]:
LIS[i] = max(LIS[i], 1 + LIS[j])
return max(LIS)
``````
• `nums = [1,5,11,5]` => `true` (1, 5, 5) and (11)

• target is sum//2, `possible = possible.union({p+n for p in possible})`

• O(n\*target) time, O(target) space
``````def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2:
return False

dp = set()
target = sum(nums) // 2

for i in range(len(nums) - 1, -1, -1):
nextDP = set()
for t in dp:
if (t + nums[i]) == target:
return True
dp = nextDP
return False
``````

### 2D#

• 🅱️🏢Unique Paths💡

• `m = 3, n = 2` => `3`

• `cache[0, 0] = 1; cache[i, j] = cache.get((i-1, j), 0) + cache.get((i, j-1), 0)`

• O(m*n) time, O(n) space
``````def uniquePaths(self, m: int, n: int) -> int:
cache = {
(i, j): 0
for i in range(m)
for j in range(n)
}
cache[0, 0] = 1
for i in range(m):
for j in range(n):
if (i, j) == (0, 0):
continue
cache[i, j] = cache.get((i-1, j), 0) + cache.get((i, j-1), 0)

return cache[m-1, n-1]

def uniquePaths(self, m: int, n: int) -> int:
"""O(n) space"""
row = [1] * n

for i in range(m - 1):
newRow = [1] * n
for j in range(n - 2, -1, -1):
newRow[j] = newRow[j + 1] + row[j]
row = newRow
return row[0]
``````
• `text1 = "abcde", text2 = "ace"` => `3` (“ace”)

• dp/recursive, add one and increase both if equal, else get the max of i+1 and j+1

• O(m*n) time, O(m*n)
``````def longestCommonSubsequence(self, text1: str, text2: str) -> int:
memo = {}
i, j = 0, 0
def recursive(i, j):
if (i, j) in memo:
return memo[i, j]
if i == len(text1) or j == len(text2):
return 0
if text1[i] == text2[j]:
memo[i, j] = 1 + recursive(i+1, j+1)
else:
memo[i, j] = max(recursive(i+1, j), recursive(i, j+1))
return memo[i, j]
return recursive(0, 0)
``````
• `prices = [1,2,3,0,2]` => `3` (buy at 1, sell at 3, buy at 0, sell at 2)

• O(n) time, O(n) space
``````def maxProfit(self, prices: List[int]) -> int:

cache = {}
if i >= len(prices):
return 0
if (i, can_buy) in cache:

result = dfs(i+1, can_buy)
buy = dfs(i+1, False)-prices[i]
result = max(result, buy)
else:
sell = dfs(i+2, True)+prices[i]
result = max(result, sell)
cache[i, can_buy] = result
return result

return dfs(0, True)
``````
• `amount = 5, coins = [1, 2, 5]` => `4`

• Unbounded Knapsack, dfs(i, amount), start with dfs(0, 0)

• O(n*amount) time, O(n*amount) space
``````def change(self, amount: int, coins: List[int]) -> int:
cache = {}

def dfs(i, a):
if a == amount:
return 1
if a > amount:
return 0
if i == len(coins):
return 0
if (i, a) in cache:
return cache[i, a]

cache[i,a] = dfs(i, a+coins[i]) + dfs(i+1, a)
return cache[i, a]

return dfs(0, 0)
``````
• 🗿Target Sum⛅: 💡

• assign + or - `nums = [1, 1, 1, 1, 1], target = 3` => `5`

• 0/1 Knapsack, O(2^n) -> O(n*sum(nums)))

• O(n) time, O(n) space
``````def findTargetSumWays(self, nums: List[int], target: int) -> int:
dp = {}  # (index, total) -> # of ways

def backtrack(i, total):
if i == len(nums):
return 1 if total == target else 0
if (i, total) in dp:
return dp[(i, total)]

dp[(i, total)] = backtrack(i + 1, total + nums[i]) + backtrack(
i + 1, total - nums[i]
)
return dp[(i, total)]

return backtrack(0, 0)
``````
• `s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbc`

• check lengths, `if i < len(s1) and s1[i] == s3[i+j] and dfs(i+1, j): True`

• O(n*m) time, O(n*m) space
``````def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False

dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
dp[len(s1)][len(s2)] = True

for i in range(len(s1), -1, -1):
for j in range(len(s2), -1, -1):
if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
dp[i][j] = True
if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
dp[i][j] = True
return dp[0][0]
``````
• `matrix = [[9,9,4],[6,6,8],[2,1,1]]` => `4` (1, 2, 6, 9)

• `result = max(result, 1+dfs(ii, jj))`, dfs every cell

• O(m*n) time, O(m*n) space
``````def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
rows, cols = len(matrix), len(matrix[0])
dp = {}

def dfs(r, c, prevVal):
if r < 0 or r == rows or c < 0 or c == cols or matrix[r][c] <= prevVal:
return 0
if (r, c) in dp:
return dp[(r, c)]

res = 1
res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
dp[(r, c)] = res
return res

for r in range(rows):
for c in range(cols):
dfs(r, c, -1)
return max(dp.values())
``````
• `s = "rabbbit", t = "rabbit"` => `3` (rabbbit, rabbbit, rabbbit)

• `if same: dfs(i+1, j+1) + dfs(i+1, j)` else `dfs(i+1, j)`

• O(n*m) time, O(n*m) space
``````def numDistinct(self, s: str, t: str) -> int:
cache = {}

for i in range(len(s) + 1):
cache[(i, len(t))] = 1
for j in range(len(t)):
cache[(len(s), j)] = 0

for i in range(len(s) - 1, -1, -1):
for j in range(len(t) - 1, -1, -1):
if s[i] == t[j]:
cache[(i, j)] = cache[(i + 1, j + 1)] + cache[(i + 1, j)]
else:
cache[(i, j)] = cache[(i + 1, j)]
return cache[(0, 0)]
``````
• 🗿Edit Distance⛈️: 💡

• `word1 = "horse", word2 = "ros"` => `3` (insert, delete, replace)

• dp, recursive

• O(m*n) time, O(m*n) space
``````def minDistance(self, word1: str, word2: str, memo=None) -> int:
if not memo:
memo = {}
if (word1, word2) in memo:
return memo[word1, word2]

if word1 == word2: return 0
if not word1: return len(word2)
if not word2: return len(word1)

if word1[0] == word2[0]:
memo[word1, word2] = self.minDistance(word1[1:], word2[1:], memo)
return memo[word1, word2]
insert = 1 + self.minDistance(word1, word2[1:], memo)
delete = 1 + self.minDistance(word1[1:], word2, memo)
replace = 1 + self.minDistance(word1[1:], word2[1:], memo)
memo[word1, word2] = min(insert, delete, replace)
return memo[word1, word2]
``````
• 🗿Burst Balloons⛈️: 💡

• `nums = [3,1,5,8]` => `167` (3*1*5 + 3*5*8 + 1*3*8 + 1*8*1)

• `nums = [1] + nums + [1]`, `dfs(1, lens(nums)-2)`

• O(n^3) time, O(n^2) space
``````def maxCoins(self, nums: List[int]) -> int:
cache = {}
nums = [1] + nums + [1]

for offset in range(2, len(nums)):
for left in range(len(nums) - offset):
right = left + offset
for pivot in range(left + 1, right):
coins = nums[left] * nums[pivot] * nums[right]
coins += cache.get((left, pivot), 0) + cache.get((pivot, right), 0)
cache[(left, right)] = max(coins, cache.get((left, right), 0))
return cache.get((0, len(nums) - 1), 0)
``````
• `s = "aa", p = "a"` => `false`

• `match = s[i] == p[j] or p[j] == '.'`, handle `*`, recursive

• O(m*n) time, O(m*n) space
``````def isMatch(self, s: str, p: str) -> bool:
cache = {}

def dfs(i, j):
if (i, j) in cache:
return cache[(i, j)]
if i >= len(s) and j >= len(p):
return True
if j >= len(p):
return False

match = i < len(s) and (s[i] == p[j] or p[j] == ".")
if (j + 1) < len(p) and p[j + 1] == "*":
cache[(i, j)] = dfs(i, j + 2) or (  # dont use *
match and dfs(i + 1, j)
)  # use *
return cache[(i, j)]
if match:
cache[(i, j)] = dfs(i + 1, j + 1)
return cache[(i, j)]
cache[(i, j)] = False
return False

return dfs(0, 0)
``````

## Greedy#

• 🅱️🏢Maximum Subarray⛅: 💡

• `nums = [-2,1,-3,4,-1,2,1,-5,4]` => `6` (`[4,-1,2,1]`)

• `current_sum = max(current_sum+n, n)`, Kadane.

• O(n) time, O(1) space
``````def maxSubArray(self, nums: List[int]) -> int:
result = nums[0]
cur_sum = 0
for n in nums:
cur_sum = max(cur_sum+n, n)
result = max(result, cur_sum)
return result
``````
• 🅱️Jump Game⛅: 💡

• `nums = [2,3,1,1,4]` => `true` (can reach last index)

• iterate, calculate max_so_far, if less than curren index, return False

• O(n) time, O(1) space
``````def canJump(self, nums: List[int]) -> bool:
max_so_far = 0
for i, n in enumerate(nums):
if max_so_far < i:
return False
max_so_far = max(max_so_far, i+n)
return True
``````
• `nums = [2,3,1,1,4]` => `2` (jump 1 step from index 0 to 1, then 3 steps to the last index)

• l = r = 0, farthest, l = r+1, r = farthest, count += 1

• O(n) time, O(1) space
``````def jump(self, nums: List[int]) -> int:
l, r = 0, 0
res = 0
while r < (len(nums) - 1):
maxJump = 0
for i in range(l, r + 1):
maxJump = max(maxJump, i + nums[i])
l = r + 1
r = maxJump
res += 1
return res
``````
• 🗿Gas Station⛅: 💡

• `gas = [1,2,3,4,5], cost = [3,4,5,1,2]` => `3` (start at index 3)

• check `sum(gas) >= sum(cost)`, if total is negative, reset and start from next index.

• O(n) time, O(1) space
``````def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
start, end = len(gas) - 1, 0
total = gas[start] - cost[start]

while start >= end:
while total < 0 and start >= end:
start -= 1
total += gas[start] - cost[start]
if start == end:
return start
total += gas[end] - cost[end]
end += 1
return -1
``````
• `hand = [1,2,3,6,2,3,4,7,8], W = 3` => `true`

• counter, iterate keys

• O(n+klogk) time, O(n) space
``````def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
if len(hand) % groupSize:
return False

count = {}
for n in hand:
count[n] = 1 + count.get(n, 0)

minH = list(count.keys())
heapq.heapify(minH)
while minH:
first = minH[0]
for i in range(first, first + groupSize):
if i not in count:
return False
count[i] -= 1
if count[i] == 0:
if i != minH[0]:
return False
heapq.heappop(minH)
return True
``````
• `triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]` => `true`

• `if any(triplet[i] > target[i] for i in range(3)):` continue, update found[i]

• O(n) time, O(1) space
``````def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
good = set()

for t in triplets:
if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
continue
for i, v in enumerate(t):
if v == target[i]:
return len(good) == 3
``````
• `s = "ababcbacadefegdehijhklij"` => `[9,7,8]`

• last_idx = {}, end = max(idx, last_idx[c]), if idx == end, add to result.

• O(n) time, O(1) space
``````def partitionLabels(self, S: str) -> List[int]:
count = {}
res = []
i, length = 0, len(S)
for j in range(length):
c = S[j]
count[c] = j

curLen = 0
goal = 0
while i < length:
c = S[i]
goal = max(goal, count[c])
curLen += 1

if goal == i:
res.append(curLen)
curLen = 0
i += 1
return res
``````
• `s = "(*)"` => `true`

• left_min, left_max, `if l_max < 0: return False`, `if l_min < 0: l_min = 0`.

• O(n^2) time, O(n) space
``````def checkValidString(self, s: str) -> bool:
dp = {(len(s), 0): True}  # key=(i, leftCount) -> isValid

def dfs(i, left):
if i == len(s) or left < 0:
return left == 0
if (i, left) in dp:
return dp[(i, left)]

if s[i] == "(":
dp[(i, left)] = dfs(i + 1, left + 1)
elif s[i] == ")":
dp[(i, left)] = dfs(i + 1, left - 1)
else:
dp[(i, left)] = (
dfs(i + 1, left + 1) or dfs(i + 1, left - 1) or dfs(i + 1, left)
)
return dp[(i, left)]
``````

## Intervals#

• 🅱️🏢Insert Interval⛅: 💡

• `intervals = [[1,3],[6,9]], newInterval = [2,5]` => `[[1,5],[6,9]]` (sorted)

• `if newInterval[1] < interval[0]`, `if newInterval[0] > interval[1]`, else merge

• O(n) time, O(n) space
``````def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if not intervals:
return [newInterval]

res = []
for i, interval in enumerate(intervals):
if interval[1] < newInterval[0]:
res.append(interval)
elif newInterval[1] < interval[0]:
res.append(newInterval)
return res + intervals[i:]
else:
newInterval = [
min(newInterval[0], interval[0]),
max(newInterval[1], interval[1])
]
res.append(newInterval)
return res
``````
• 🅱️🏢Merge Intervals⛅: 💡

• `intervals = [[1,3],[2,6],[8,10],[15,18]]` => `[[1,6],[8,10],[15,18]]`

• Sort by start, change prev.end = max(prev.end, curr.end)

• O(nlogn) time, O(n) space
``````def merge(self, intervals: List[List[int]]) -> List[List[int]]:
result = []
for start, end in sorted(intervals):
if not result or start > result[-1][1]:
result.append([start, end])
else:
result[-1][1] = max(result[-1][1], end)
return result
``````
• `intervals = [[1,2],[2,3],[3,4],[1,3]]` => `1` (number of intervals to remove)

• sort, update if start >= prev.end, else increase count

• O(nlogn) time, O(1) space
``````def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
end = float("-inf")
overlap = 0
for s, e in sorted(intervals, key=lambda x: x[1]):
if s >= end:
end = e
else:
overlap += 1
return overlap
``````
• 🅱️Meeting Rooms☀️: 💡

• `intervals = [(0,30),(5,10),(15,20)]` => `false`

• sort, if start < prev.end, return false

• O(nlogn) time, O(n) space
``````def canAttendMeetings(self, intervals):
intervals.sort(key=lambda i: i[0])

for i in range(1, len(intervals)):
i1 = intervals[i - 1]
i2 = intervals[i]

if i1[1] > i2[0]:
return False
return True
``````
• 🅱️🏢Meeting Rooms II⛅: 💡 min number of conference rooms.

• `intervals = [(0,30),(5,10),(15,20)]` => `2`

• store all sorted timestamps, if start += 1, if end -= 1, max number of rooms

• O(nlogn) time, O(n) space
``````def minMeetingRooms(self, intervals: List[List[int]]) -> int:
time = []
for start, end in intervals:
time.append((start, 1))
time.append((end, -1))

time.sort(key=lambda x: (x[0], x[1]))

count = 0
max_count = 0
for t in time:
count += t[1]
max_count = max(max_count, count)
return max_count
``````
• `intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]` => `[3,-1,3,4]`

• sort intervals & queries, heap (length, end), pop if end < query, dict[query] = length

• O(nlogn + qlogq) time, O(n+q) space
``````def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
intervals.sort()
minHeap = []
res = {}
i = 0
for q in sorted(queries):
while i < len(intervals) and intervals[i][0] <= q:
l, r = intervals[i]
heapq.heappush(minHeap, (r - l + 1, r))
i += 1

while minHeap and minHeap[0][1] < q:
heapq.heappop(minHeap)
res[q] = minHeap[0][0] if minHeap else -1
return [res[q] for q in queries]
``````

## Math & Geometry#

• 🅱️Rotate Image⛅: 💡

• `matrix = [[1,2,3],[4,5,6],[7,8,9]]` => `[[7,4,1],[8,5,2],[9,6,3]]`

• reverse rows, transpose

• O(cells) time, O(1) space
``````def rotate(self, matrix: List[List[int]]) -> None:
l, r = 0, len(matrix) - 1
matrix.reverse()
for i in range(len(matrix)):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
``````
• 🅱️Spiral Matrix⛅: 💡

• `matrix = [[1,2,3],[4,5,6],[7,8,9]]` => `[1,2,3,6,9,8,7,4,5]`

• 4 pointers, left, right, top, bottom, while l <= r and t <= b

• O(n^2) time, O(1) space
``````def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
left, right = 0, len(matrix[0])
top, bottom = 0, len(matrix)

while left < right and top < bottom:
# get every i in the top row
for i in range(left, right):
res.append(matrix[top][i])
top += 1
# get every i in the right col
for i in range(top, bottom):
res.append(matrix[i][right - 1])
right -= 1
if not (left < right and top < bottom):
break
# get every i in the bottom row
for i in range(right - 1, left - 1, -1):
res.append(matrix[bottom - 1][i])
bottom -= 1
# get every i in the left col
for i in range(bottom - 1, top - 1, -1):
res.append(matrix[i][left])
left += 1

return res
``````
• `matrix = [[1,1,1],[1,0,1],[1,1,1]]` => `[[1,0,1],[0,0,0],[1,0,1]]`

• use first row and column to store if row or column should be zeroed

• O(mn) time, O(m+n) space
``````def setZeroes(self, matrix: List[List[int]]) -> None:
# O(1)
ROWS, COLS = len(matrix), len(matrix[0])
rowZero = False

# determine which rows/cols need to be zero
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
matrix[0][c] = 0
if r > 0:
matrix[r][0] = 0
else:
rowZero = True

for r in range(1, ROWS):
for c in range(1, COLS):
if matrix[0][c] == 0 or matrix[r][0] == 0:
matrix[r][c] = 0

if matrix[0][0] == 0:
for r in range(ROWS):
matrix[r][0] = 0

if rowZero:
for c in range(COLS):
matrix[0][c] = 0
``````
• 🗿 🏢Happy Number☀️: 💡

• `n = 19` => `true` (`12 + 92 = 82 |...| 12 + 02 + 02 = 1`)

• Hashset seen or Floyd’s cycle detection

• O(klogn), O(k) space -> k is num of iterations
``````def isHappy(self, n):
seen = set()
while n not in seen:
n = sum([int(x) **2 for x in str(n)])
return n == 1
``````
• 🗿Plus One☀️: 💡

• `digits = [1,2,3]` => `[1,2,4]`

• iterate reverse, carry variable, check carry at end

• O(n) time, O(n) space
``````def plusOne(self, digits: List[int]) -> List[int]:
result = []
carry = 1
for i in range(len(digits)-1, -1, -1):
n = digits[i]+carry
if n == 10:
carry = 1
n = 0
else:
carry = 0
result.append(n)

if carry:
result.append(1)
return result[::-1]
``````
• 🗿Pow(x, n)⛅: 💡

• `x = 2.00000, n = 10` => `1024.00000`

• recursive, handle 0 and negatives

• O(n) time, O(n) space
``````def myPow(self, x: float, n: int) -> float:
if n == 0: return 1
if n < 0: return 1 / self.myPow(x, -n)
return x*self.myPow(x, n-1)

def myPow(self, x, n):
if n == 0: return 1
if n < 0: return 1 / self.myPow(x, -n)
# Optimized
if n % 2 == 1: return x * self.myPow(x, n-1)
return self.myPow(x*x, n/2)
``````
• `num1 = "2", num2 = "3"` => `"6"`

• Manual multiplication, reverse, for in for

• O(nm) time, O(n+m) space
``````def multiply(self, num1: str, num2: str) -> str:
if "0" in [num1, num2]:
return "0"

res = [0] * (len(num1) + len(num2))
num1, num2 = num1[::-1], num2[::-1]
for i1 in range(len(num1)):
for i2 in range(len(num2)):
digit = int(num1[i1]) * int(num2[i2])
res[i1 + i2] += digit
res[i1 + i2 + 1] += res[i1 + i2] // 10
res[i1 + i2] = res[i1 + i2] % 10

res, beg = res[::-1], 0
while beg < len(res) and res[beg] == 0:
beg += 1
res = map(str, res[beg:])
return "".join(res)
``````
• 🗿 🏢Detect Squares⛅: 💡

• `points = [[3,10],[11,5],[11,10]]` => `[true,false,true]`

• `res += self.points_count[x, py] * self.points_count[px, y]`

• O(n) time, O(n) space
``````def __init__(self):
self.ptsCount = defaultdict(int)
self.pts = []

def add(self, point: List[int]) -> None:
self.ptsCount[tuple(point)] += 1
self.pts.append(point)

def count(self, point: List[int]) -> int:
res = 0
px, py = point
for x, y in self.pts:
if (abs(py - y) != abs(px - x)) or x == px or y == py:
continue
res += self.ptsCount[(x, py)] * self.ptsCount[(px, y)]
return res
``````

## Bit Manipulation (rare)#

Summary

Click to expand
• 🗿Single Number☀️: 💡

• `nums = [2,2,1]` => `1`

• XOR / hashset

• O(n) time, O(1) space
``````def singleNumber(self, nums: List[int]) -> int:
result = 0
for n in nums:
result ^= n
return result
``````
• 🅱️Number of 1 Bits☀️: 💡

• `n = 11` => `3` (1011)

• either `res += n & 1` and `n >> 1`

• O(logn) time, O(1) space
``````def hammingWeight(self, n: int) -> int:
result = 0
while n:
result += n & 1
n = n >> 1
return result
``````
• 🅱️Counting Bits☀️: 💡

• `n = 2` => `[0,1,1]`

• `if offset * 2 == i: offset *= i`, `dp[i] = dp[i-offset] + 1`

• O(n) time, O(n) space
``````def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
offset = 1

for i in range(1, n + 1):
if offset * 2 == i:
offset = i
dp[i] = 1 + dp[i - offset]
return dp
``````
• 🅱️Reverse Bits☀️: 💡

• `00000000000000000000000000000110` => `01100000000000000000000000000000`

• `for i in range(32): bit = (n >> i) & 1`, `res |= bit << (31-i)`

• O(1) time, O(1) space (32 bit)
``````def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
bit = (n >> i) & 1
res += (bit << (31 - i))
return res
``````
• 🅱️Missing Number☀️: 💡

• `nums = [3,0,1]` => `2`

• XOR index+1 and value, similar to duplicate number

• O(n) time, O(1) space
``````def missingNumber(self, nums: List[int]) -> int:
result = 0

for counter,value in enumerate(nums):
result ^= counter+1
result ^= value
return result
``````
• `a = 1, b = 2` => `3`

• `return a if b == 0 else getSum(a^b, (a&b)<<1)`

• ...
``````def getSum(self, a: int, b: int) -> int:
if not a or not b:
return a or b
return add(a ^ b, (a & b) << 1)

if a * b < 0:  # assume a < 0, b > 0
if a > 0:
return self.getSum(b, a)
if add(~a, 1) == b:  # -a == b
return 0
if add(~a, 1) < b:  # -a < b

return add(a, b)  # a*b >= 0 or (-a) > b > 0
``````
• `x = 123` => `321`

• TODO

• ...
``````def reverse(self, x: int) -> int:
MIN = -2147483648  # -2^31,
MAX = 2147483647  #  2^31 - 1

res = 0
while x:
digit = int(math.fmod(x, 10))  # (python dumb) -1 %  10 = 9
x = int(x / 10)  # (python dumb) -1 // 10 = -1

if res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10):
return 0
if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):
return 0
res = (res * 10) + digit

return res
``````

## Extra#

• `words = ["This", "is", "an", "example", "of", "text", "justification."] w = 16` => `["This is an", "example of text", "justification. "]`

• `if line_width + len(cur) > maxWidth:`, `line[j%(len(line)-1 or 1)] += ' '`

• O(n) time, O(n) space
``````def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
result = []

line_width = 0
line = []
for w in words:
if line_width + len(w) <= maxWidth:
line.append(w)
line_width += 1+len(w)
else:
result.append(line)
line_width = len(w)+1
line = [w]
if line:
result.append(line)

for i, line in enumerate(result):
spaces = maxWidth - sum(len(w) for w in line)
if i == len(result)-1:
result[i] = " ".join(line).ljust(maxWidth)
else:
for j in range(spaces):
line[j%(len(line)-1 or 1)] += ' '
result[i] = "".join(line)
return result
``````
• `[1,3]`, `pickIndex()` => `0` with 25% probability, `1` with 75% probability

• binary search (random (1, total)) on the prefix sum.

• O(logN) time, O(n) space
``````def __init__(self, w: List[int]):
self.prefix_sums = []
prefix_sum = 0
for weight in w:
prefix_sum += weight
self.prefix_sums.append(prefix_sum)

def pickIndex(self) -> int:
target = self.prefix_sums[-1] * random.random()
l, r = 0, len(self.prefix_sums)-1
while l <= r:
mid = (r+l) // 2
if target == self.prefix_sums[mid]:
return mid
if target > self.prefix_sums[mid]:
l = mid + 1
else:
r = mid - 1
return l
``````
• `shouldPrintMessage(1, "foo"), shouldPrintMessage(3, "foo")` => `true, false`

• Hashmap `{message: timestamp}`, `if self.cache[message] + 10 > timestamp`

• O(1) time, O(n) space
``````def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
if message not in self.cache:
self.cache[message] = timestamp
return True
elif self.cache[message] + 10 > timestamp:
return False
else:
self.cache[message] = timestamp
return True
``````
• `n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]` => `0`

• heap of ready rooms (room_id), heap of rooms in use (end_time, room_id)

• O(nlogn) time, O(n) space
``````def mostBooked(self, n, meetings):
ready = [r for r in range(n)] # room_id
rooms = []  # (end_time, room_id)
res = [0] * n  # times booked for each room
for s, e in sorted(meetings):
# check finished meetings
while rooms and rooms[0][0] <= s:
_, r = heappop(rooms)
heappush(rooms, [e, r])
else:
t, r = heappop(rooms)
# delayed
heappush(rooms, [t + e - s, r])
res[r] += 1
return res.index(max(res))
``````
• `target = 3` => `2` (“AA” 0 -> 1 -> 3)

• deque, BFS, but only add reverse if `pos + vel < target` or `pos + vel > target`

• O(logt) time, O(t) space
``````def racecar(self, target: int) -> int:
# 0 moves, 0 position, +1 velocity
queue = collections.deque([(0, 0, 1)])
while queue:
moves, pos, vel = queue.popleft()

if pos == target:
return moves

queue.append((moves + 1, pos + vel, 2 * vel))
if (pos + vel > target and vel > 0) or (pos + vel < target and vel < 0):
queue.append((moves + 1, pos, -vel / abs(vel)))
``````
• `grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1` => `-1`

• simple bfs with deque [(steps, x, y, k)]

• O(logt) time, O(t) space
``````def shortestPath(self, grid: List[List[int]], k: int) -> int:
rows, cols = len(grid), len(grid[0])
target = (rows - 1, cols - 1)

if k >= rows + cols - 2:
return rows + cols - 2

state = (0, 0, k)
queue = deque([(0, state)])
seen = set([state])

while queue:
steps, (row, col, k) = queue.popleft()

if (row, col) == target:
return steps

for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]:
if (0 <= new_row < rows) and (0 <= new_col < cols):
new_eliminations = k - grid[new_row][new_col]
new_state = (new_row, new_col, new_eliminations)
if new_eliminations >= 0 and new_state not in seen:
queue.append((steps + 1, new_state))

return -1
``````

Easy:

• `n = 5`, `isBadVersion(3) = false`, `isBadVersion(4) = true`

• binary search, `return r+1` (r is last good version)

• O(logn) time, O(1) space
``````def firstBadVersion(self, n: int) -> int:
l = 1
r = n
while l <= r:
mid = (l+r) // 2
if isBadVersion(mid): r = mid-1
else: l = mid+1
return r+1
``````
• `strs = ["flower","flow","flight"]` => `"fl"`

• iterate first word and compare

• O(sum_chars) time, O(1) space
``````def longestCommonPrefix(self, strs: List[str]) -> str:
for i, c in enumerate(strs[0]):
for string in strs[1:]:
if i == len(string) or string[i] != c:
return strs[0][:i]
return strs[0]
``````
• `moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]` => `"A"`

• Try to generalize

• O(1) time, O(1) space
``````def tictactoe(self, moves: List[List[int]]) -> str:
n = 3
board = [["" for _ in range(n)] for _ in range(n)]
first = True
for i, j in moves:
board[i][j] = "A" if first else "B"
first = not first

for row in board:
if all(c == "A" for c in row):
return "A"
if all(c == "B" for c in row):
return "B"

for col in range(n):
if all(row[col] == "A" for row in board):
return "A"
if all(row[col] == "B" for row in board):
return "B"

if all(board[i][i] == "A" for i in range(n)):
return "A"
if all(board[i][i] == "B" for i in range(n)):
return "B"
if all(board[n-1-i][i] == "A" for i in range(n-1, -1, -1)):
return "A"
if all(board[n-1-i][i] == "B" for i in range(n-1, -1, -1)):
return "B"

return "Draw" if all(row[c] for row in board for c in range(n)) else "Pending"
``````
• `x = 121` => `true`

• `new = new*10 + cur%10`

• O(logn) time, O(1) space
``````def isPalindrome(self, x: int) -> bool:
if x < 0:
return False

new = 0
cur = x
while cur:
new = new*10+cur%10
cur = cur // 10
return new == x
``````
• `s = "III"` => `3`

• sum, but handle special

• O(n) time, O(1) space
``````def romanToInt(self, s: str) -> int:
translations = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
number = 0
s = s.replace("IV", "IIII").replace("IX", "VIIII")
s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
for char in s:
number += translations[char]
return number
``````

Medium:

• `update(i, val)`, `sumRange(i, j)`

• Segment tree

• O(logn) time, O(n) space

• ...
• `nums = [1,1,1], k = 2` => `2` ([1, 1] and [1, 1])

• prefix sum, `result += prefix.get(current_sum-k, 0)`, initialize `d[0] = 1`

• O(n) time, O(n) space
``````def subarraySum(self, nums: List[int], k: int) -> int:
prefix = {0: 1}
current_sum = 0
result = 0
for n in nums:
current_sum += n
result += prefix.get(current_sum-k, 0)
prefix[current_sum] = prefix.get(current_sum, 0) + 1
return result
``````
• `changed = [1,3,4,2,6,8]` => `[1,3,4]`

• iterate sorted count, `if count[2*x] >= count[x]`, handle 0, `cnt[2*x] -= cnt[x]`

• O(n + mlogm) time, O(m) space (m = unique elements)

• ...
• `s = "3[a]2[bc]"` => `"aaabcbc"`

• append to stack `if != ']'`, pop and multiply

• O(n_output) time, O(n_output) space

• ...
• `book(start, end)`, `book(10, 20)`, `book(15, 25)`, `book(20, 30)`

• List (deque) + binary search

• O(n) time, O(n) space

• ...
• `s = "abcde", words = ["a","bb","acd","ace"]` => `3`

• Hashmap `{char: [(word_idx, current_idx)]}`

• O(s.length+sumcharwords) time, O(#words) space

• ...
• `words = ["a","b","ba","bca","bda","bdca"]` => `4` (a, b, ba, bda)

• start with shortest, for each word, check if word[:i]+word[i+1:] in dp

• O(nlog(n) + nll) time, O(ns) space

• ...
• TODO

• ...
• `properties = [[5,5],[6,3],[3,6]]` => `0`

• sort by `-x[0],x[1]`, then iterate and keep max y

• O(nlogn) time, O(1) space

• ...
• `cardPoints = [1,2,3,4,5,6,1], k = 3` => `12`
• Sliding window, minimum subarray of size n-k.
• O(n) time, O(1) space
• `update(int timestamp, int price)`, `current()`, `maximum()`, `minimum()`
• 2 heaps, timestamps[time, price], self.highest_timestamp.
• dfs, post-order, return layer.
• `SnapshotArray(int length)`, `set(index, val)`, `snap()`, `get(index, snap_id)`
• Dict[int, array], binary search on the list of snapshots.
• `timePoints = ["23:59","00:00"]` => `1`
• map to minutes & sort, `(time[i]-time[i-1])%(24*60)`
• O(nlogn) time, O(n) space
• TODO
• 🏢https://leetcode.com/problems/battleships-in-a-board/?md

• 🏢https://leetcode.com/problems/find-and-replace-in-string/?md

• 🏢https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/?md

• 🏢https://leetcode.com/problems/sort-integers-by-the-power-value/?md

• 🏢https://leetcode.com/problems/maximum-number-of-points-with-cost/?md

• 🏢https://leetcode.com/problems/detonate-the-maximum-bombs/?md

• 🏢https://leetcode.com/problems/filling-bookcase-shelves/?md

• 🏢https://leetcode.com/problems/shortest-way-to-form-string/?md

• 🏢https://leetcode.com/problems/rle-iterator/?md

• 🏢https://leetcode.com/problems/check-if-word-can-be-placed-in-crossword/?md

• 🏢https://leetcode.com/problems/sentence-screen-fitting/?md

• 🏢https://leetcode.com/problems/parallel-courses/?md

• 🏢https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/?md

• 🏢https://leetcode.com/problems/find-duplicate-subtrees/?md

• 🏢https://leetcode.com/problems/bulls-and-cows/?md

• 🏢https://leetcode.com/problems/time-needed-to-inform-all-employees/?md

Hard:

• 🏢Poor Pigs: 💡
• `buckets = 1000, minutesToDie = 15, minutesToTest = 60` => `5`
• TODO
• 🏢Range Module 💡
• TODO
• 🏢https://leetcode.com/problems/robot-room-cleaner/?hd
• 🏢https://leetcode.com/problems/employee-free-time/?hd
• 🏢Student Attendance Record II: Fewer than 2 A, no 3 or more consecutive L. [💡]
• `n = 2` => `8` (“PP”, “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”)
• 🏢https://leetcode.com/problems/amount-of-new-area-painted-each-day/?hd
• 🏢https://leetcode.com/problems/number-of-atoms/?hd
• 🏢https://leetcode.com/problems/number-of-good-paths/?hd
• 🏢https://leetcode.com/problems/guess-the-word/?hd
• 🏢https://leetcode.com/problems/shortest-distance-from-all-buildings/?hd
• 🏢https://leetcode.com/problems/maximum-and-sum-of-array/?hd
• 🏢https://leetcode.com/problems/sum-of-prefix-scores-of-strings/?hd
• 🏢https://leetcode.com/problems/basic-calculator/

• KMP pattern matching, O(m+n).
• Maximum Length of Repeated Subarray: Rabin–Karp algorithm / Rolling Hash.

• Longest Duplicate Substring / s: Rabin Karp + Binary Search.

• `set(w1) == set(w2) and Counter(Counter(w1).values()) == Counter(Counter(w2).values()`
• String Compression: 2 pointers, slow and fast.

• `1->2->3->4->5` => `3`
• slow = fast = head, while fast and fast.next: …, return slow
• O(n) time, O(1) space
• `head = [3,2,0,-4], -4 -> 2` => `2`
• dist(intersect, cycle) == dist(head, cycle)
• O(n) time, O(1) space
• Sudoku Solver: `if board[3 * (i // 3) + k // 3][ 3 * (j // 3) + k % 3] == n:`