# Algorithm Patterns

This document contains all the coding algorithm patterns I have seen. There is no structure to this document. These are all the rough notes that I go through in my free-time (bus-rides to GaTech). Maybe one day I'll make a flash-card deck for this.

# Arrays

3sum

Find 3 nums that add up to 0 (similar to 2 sum).

```class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:

nums.sort()
i = 0
j = i + 1
k = len(nums)-1

triplets = set()
for i in range(len(nums) - 2):
first = nums[i]
j = i + 1
k = len(nums) - 1
while j < k:
second = nums[j]
third = nums[k]

if first + second + third == 0:
j+=1
k-=1
elif first + second + third > 0:
k-=1
else:
j += 1
return triplets
```

Pattern Remember that 2-sum can be done in linear time and 3 sum needs quadratic time! Use a 2 pointer approach. The first step in any array method is to sort the arrays. It only takes O(nlogn) time at most. And we can always afford to sort!

Select pointer i, j, k for first, second and third element. Outermost loop should only iterate through i. Innermost loop should iterate j and k in opposite directions. Since our array is sorted from low to big, if sum is > 0 then it means that k is over-sized hence decrement k. Else increment j if sum < 0 since j is too -ve. If same, insert into a set!

Note how the while loop works. We increment j and decrement k. We stop when j > k.

Complexity: O(n^2) TC and O(n) Space complexity

3sum Closest Exactly same as above but target is non-zero and goal is to reach as close to target as possible. Do the same as above i.e. 3 pointers, `i` goes from 0 to n-2, j goes from 1 to right and k goes from n-1 to left (till j target.

Complexity: O(n^2) TC O(n) SC

4sum This is a very general implementation of N-sum. We know that 2-sum is linear time, 3-sum is quadratic time. Check the general solution:

```class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

nums.sort()
ret = []
# we pass empty list [] to collect results
self.helper(nums, target, 4, [], ret) # N can be anything
return ret

def helper(self, nums, target, N, res, ret):

if len(nums) < N or N <2:
return
if N == 2:
op = self.twoSum(nums, target)
if op != []:
for idx in op:
ret.append(res + idx)
else:
for i in range(len(nums) - N + 1):
if nums[i]*N > target or nums[-1]*N < target:
break
if i == 0 or i>0 and nums[i-1] != nums[i]:  # here the second clause handles duplicates in array
self.helper(nums[i+1:], target - nums[i], N-1, res + [nums[i]], ret)

def twoSum(self, nums, target):
# we want to return all 2 sums
pass # assume this mf is implemented
```

In general, the pattern is: Create a function F(N, array). Inside the function: `F(N, array) = F(N-i, array[i:]) for i in range(len(array)-N+1)`. The `nums[i-1] != nums[i]` is meant to handle duplicates in the array.

A few tips:

• If asking to sum to a number N then sorting is best (unless its 2-sum)
• If asking for indices then sorting is NOT a good idea
• Remember that fetch of key or checking key is in Hashmap is O(1)

Find First and Last Position of Element in Sorted Array This is literally binary search. VV imp algo. We have an array with repeated values of a target. Goal is to find start and end index of that value.

```class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:

def binSearch(x):
lo, hi = 0, len(nums)
while lo < hi:
m = (lo + hi) // 2 # integer div
if nums[m] < x:
lo = m+1
else:
hi = m
return lo

lo = binSearch(target) # so clever
hi = binSearch(target + 1) - 1
if lo <= hi:
return [lo, hi]
return [-1, -1]
```

Pattern Standard bin search for target and bin search for a value just greater than the target. TC: O(Log N) SC: O(Log N)

Flatten Binary Tree to Linked List This is a very important problem to show how recursion works and how to convert it to a stack based solution.

Consider this solution:

```class Solution:
previous_right = None
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root:
self.flatten(root.right) # call A
self.flatten(root.left) # call B

# Task C: things to do once recursive calls are completed
root.right, self.previous_right = self.previous_right, root
root.left = None
```

Now a way to make this run faster is to make it iterative and use a stack. A simple structure to call the stack is as follows:

```       stack = [(root, False)]
previous_right = None
while stack:
node, visited = stack.pop()
if node:
if visited:
node.right, previous_right = previous_right, node
node.left = None
else:
stack.append((node, True)) # enqueue Task C
stack.append((node.left, False)) # append Call B
stack.append((node.right, False)) # append Call A
```

Notice how when we convert the code into an iterative stack based solution, we simply append/push to the stack in reverse order of execution. Because we expect the recursive call to right side of the tree to finish first, it is enqueued last đź™‚That way it will be popped out first. This structure will help implement any recursive function into an iterative function.

652. Find Duplicate Subtrees

```from collections import defaultdict
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:

best = defaultdict(int)
ans = []
def dfs(node):
nonlocal best, ans
if node is None:
return

l = dfs(node.left)
r = dfs(node.right)

curr = f"L{l}({node.val})R{r}"
if curr in best and best[curr] == 1:
ans.append(node)
best[curr] += 1
return curr
dfs(root)
return ans
```

Pattern Subpath-tracking. This is a veeryyyy important tree question. You must essentially keep a track of every sub-path visited. Here we keep a track of visited using a string representation of the tree. Once we see a sub-path, we simply store it back in a dict. If the sub-path is seen in dict already, then we simply add the seen-node to the list of answers! VVV important pattern.

Rotate List

```class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

h = p1 = p2 = head
space = k

# separate the pointers
len_list = 0
while space >0:
len_list+=1
# print(len_list)
if p2.next is None:
p2 = h
space = k%len_list
continue
else:
p2 = p2.next
space -= 1

# move both to the end
while p2.next:
p1 = p1.next
p2 = p2.next

# set the last element to head
p2.next = h
h = p1.next
# set element before the head to prev
p1.next = None

return h
```

Pattern Two pointers. Step 1: separate out the pointers. Step 2: Increment both the pointers post-separation. Step 3: Do what you must do post-separation! Here the trick is to keep p1 and p2 at a distance of k with k starting from 0. This way, you always have access to k-1th element and kth element as well. For the above particular question, we simply do at step 3: point p2.next to head. Make new head point to p1.next. Poing p1.next to null.

Edge Case If k >>>> size of the LL. Then when you hit the end of the LL you will have the size of the LL. Simply set K = K%size(LL) + 1

```class Solution:
seen = set()
while p1:
p1 = p1.next
while p2:
if id(p2) in seen:
return p2
p2 = p2.next
return None
```

Pattern Subpath finding! Store path in seen! Very similar to the subtree question we did a while ago! Simply store the object id in a seen dict. If itâ€™s seen before you return the node else continue traversing.

Sort Colors VV important question! Uses something called Dutch Parititoning for fastest solution!

```class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
r, w, b = 0, 0, len(nums)-1
while w <= b:
if nums[w] == 0:
nums[w], nums[r] = nums[r], nums[w]
r+=1
w+=1
elif nums[w] == 1:
w+=1
else:
nums[w], nums[b] = nums[b], nums[w]
b-=1
```

Pattern Two pointers at start and 1 at the end. Use Dutch partitioning! middle pointer `w` is always gonna be a pivot. middle `w` gotta be less than end `b`. If middle has element lesser than middle then swap leftside `r` with middle `w`. Increment both. If middle actually has correct element then increment middle `w` pointer. Else swap right `b` and middle `w` and only decrement `b`. Dont use more brain and just accept this algo.

Merge Sorted Arrays

Similar to previous post:

```class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1 = m-1
p2 = n-1
w = m+n-1

while p2 >= 0:
if p1 >=0 and nums1[p1] > nums2[p2]:
nums1[w] = nums1[p1]
p1-=1
else:
nums1[w] = nums2[p2]
p2-=1
w-=1
```

Pattern Maintain 2 start pointers and one end pointer moving from right to left.

# Backtracking

Combination 3 sum

```class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
if k>n:
return []
nums = range(1, 10) # 123456789
ans = []
def back(idx, path):
if len(path) == k: # terminal condition here!
if sum(path) == n:
ans.append(path)
return

for i in range(idx, len(nums)): # for loop to generate combinations!
back(i+1, path + [nums[i]])

back(0, [])
return ans
```

Pattern Simple pattern of backtracking. Remember that when the problem asks for combinations, do recursive calls in a for loop! Typically pass your backtracking function, f(idx, path)

• If repetitions dont matter: Start from 0 to N
• If repetitions not allowed and order matters: Start for loop form idx to N and pass in `f(i+1, path + [num[i]])`
• If picking ith element again is allowed then start loop from idx ot N and pass `f(i, path+[num[i]])` and perhaps consider maintaining a visited set.

TC: O(K^N)

Non-decreasing subsequences

```class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:

subsets = set()

def back(idx, path, k):
if len(path) == k: # exit
return
for i in range(idx, len(nums)):
# if nums[i] == nums[i-1]:
#     continue
if len(path) == 0 or path[-1] <= nums[i]: # ensure non-decreasing
back(i+1, path + [nums[i]], k)

for i in range(2, len(nums)+1):
back(0, [], i)

return [list(s) for s in subsets]
```

Pattern This is similar to subset generation question of backtracking. Have one reliable way of generating subsets and the rest will be take care of!

• Subset or powerset pattern. â€śCombinations of size Kâ€ť + â€śfor loop foing from 0<=K<=maxâ€ť
• Simply create function with f(idx, path, k). In a for loop going from 0 to N, call f(0, [], k)
• Since it has combinations do for loop from idx to N.
• TC: O(9^N)

Target Sum You are allowed to combine two elements in array with + or a -. See if you can get to target.

```class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
mem = {}
def dfs(curr, nums):
key = (curr, tuple(nums))
if key in mem: return mem[key]
if not nums: return 1 if curr == target else 0
mem[key] = dfs(curr - nums[0], nums[1:]) + dfs(curr + nums[0], nums[1:])
return mem[key]
return dfs(0, nums)
```

## Pattern This is a simple DFS traversal. No sweat. Notice that we memoize.

VVVV IMP PATTERN

```from copy import deepcopy
class Solution:

ans = []
best = float('inf')
def back(idx):
nonlocal best
if idx == len(cookies): # exit when idx == array len
best = min(best, max(ans))
return

if len(ans) < k: # next push->backtrack->pop till placeholder arr isnt full
back(idx+1)
ans.pop()

for i in range(len(ans)): # finally keep adding or decreasing from placeholder array
# notice how we only loop thorugh len(ans)
if ans[i] + cookies[idx] < best:
back(idx+1)

back(0)
return best
```

Pattern DISTRIBUTION! Under the hood this is just a clever way of doing subset combination generation! Remember this pattern:

• Maintain a collector array outside the back() function
• Call the backtracking in the following way:
```def back(idx):
back(idx+1)
visited.remove(idx)
back(idx+1)
```

The above form ends up generating subsets! Its pretty cool! For problems where you are expected to have one fixed size group with distribution of values within that group then follow this pattern.

In back tracking do this;

1. Exit when idx == len(array)
2. Do push -> recurse -> pop until accumulator array not full (will typilcally have a max size)
3. Do ans+i -> recurse -> ans+i TC: O(K^N)

Matchsticks to Square

```class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:

if sum(matchsticks) %4 != 0 or max(matchsticks) > (sum(matchsticks)//4):
return False # task cannot be completed

target = sum(matchsticks)//4
edges = [] # [1, 1]
found = False
# @cache
def back(idx):
nonlocal found
if found:
return

if idx == len(matchsticks):
if len(edges) == 4:
e1, e2, e3, e4 = edges
found = e1 == e2 == e3 == e4
return

if len(edges) < 4:
edges.append(matchsticks[idx])
back(idx+1)
edges.pop()

for i in range(len(edges)):
if edges[i] + matchsticks[idx] <= target:
edges[i] += matchsticks[idx]
back(idx+1)
edges[i] -= matchsticks[idx]

back(0)
return found
```

Pattern DISTRIBUTION! Exactly the same as previous question on cookie distribution. Size is fixed to 4. We have to distribute matchstick sizes into 4 groups instead of cookies!

TC: O(K^N)

IN BACKTRAKCING PROBLEMS AND DFS ALWAYS USE `nonlocal temp` if temp is outsite the recursive func

784 Letter Case permutation

Needs to go in a straight line. There are no combinations happening so no loop required. For loop come never comes into picture for problem statements where ith element can never be combined or seen with i+rth element (i.e. problems where sequence matters) Simply pass idx + 1 to recursive function

```class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
ans = []
def back(idx, path):
if len(path) == len(s):
ans.append(''.join(path))
return
if s[idx].isdigit():
back(idx+1, path + [s[idx]])
else:
back(idx+1, path + [s[idx].upper()])
back(idx+1, path + [s[idx].lower()])
back(0, [])
return ans
```

Max Split of Positive Even Integers

Pattern: Comb + Idx + Path

```class Solution:
def __init__(self):
self.options = [2*i for i in range(1, )]

def maximumEvenSplit(self, finalSum: int) -> List[int]:
if finalSum % 2 != 0:
return []
L = finalSum // 2
nums = [2*i for i in range(1, L+1)]
max_len = 0
ans = []
def back(idx, path):
nonlocal max_len, ans # always!
if sum(path) == finalSum and len(path) > max_len:
max_len = len(path)
ans = path
return
for i in range(idx, len(nums)):
back(i+1, path + [nums[i]])
back(0, [])
return ans
```

^ This is correct but slow. Errors I made: nonlocal `max_len` and `ans` weren't there! Hence code broke! This also results in a timeout: Greedy solution:

```class Solution:
def maximumEvenSplit(self, finalSum: int) -> List[int]:
ans, i = [], 2
if finalSum % 2 == 0:
while i <= finalSum:
ans.append(i)
finalSum -= i
i += 2
print(finalSum, i, ans)
ans[-1] += finalSum

return ans
```

2375 construct smallest num from DI string

```class Solution:
def smallestNumber(self, pattern: str) -> str:
ans = []
stack = []
for i in range(len(pattern)+1):
stack.append(i+1)
if i == len(pattern) or pattern[i] == "I":
while stack:
ans.append(stack.pop())

return ''.join(map(str, ans))
```

Pattern: Greedy: answer append I + stack append D and answer append stack pop Mistake made: join on list of ints!

2597 Number of beautiful subsets

```from collections import Counter
class Solution:
def beautifulSubsets(self, nums: List[int], k: int) -> int:

N = len(nums)
counter = Counter()
output = 0
def dfs(idx):
nonlocal counter, output
if idx == N:
if counter:
output += 1
return

if nums[idx] - k not in counter and nums[idx] + k not in counter:
counter[nums[idx]] += 1
dfs(idx+1)
counter[nums[idx]] -= 1
if not counter[nums[idx]]:
del counter[nums[idx]]
dfs(idx+1)
dfs(0)
return output
```

Pattern: Subset Generation algo + check if curr - k and curr + k are visited. Follows the classic subset generation logic:

```Counter[nums[i]] += 1
dfs(idx+1)
Counter[nums[i]] -= 1
dfs(idx+1)
```

Like this:

```       res = []
path = []
def find(idx):
if idx > len(nums)-1:
res.append(path.copy())
return
path.append(nums[idx])
find(idx+1)
path.pop()
find(idx+1)
find(0)
return res
```

2708: Max Strength of Group

```from collections import Counter
class Solution:
def maxStrength(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
res = []
path = []
output = 0
def find(idx):
nonlocal res, path, output
if idx == len(nums):
if path:
temp = 1
for p in path:
temp *= p
if temp > output:
output = temp
res.append(path)
return
path.append(nums[idx])
find(idx+1)
path.pop()
find(idx+1)
find(0)
return output
```

Pattern: Subset generation (std algo) + global max Edgecases: handle if path is empty or handle if only one element is in the list

797. All Paths From Source to Target

```class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
q =[[0]]
target = len(graph) -1
res = []
while q:
temp = q.pop(0)
if temp[-1] == target:
res.append(temp)
for nei in graph[temp[-1]]:
q.append( temp +[nei])
return res
```

Pattern: BFS

79. Word Search

```class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:

M = len(board)
N = len(board[0])

visited = [[0 for _ in range(N)] for _ in range(M)]
found = False # indicator

def back(idx, bi, bj):
nonlocal found, visited

# ensure not crossing board boundaries
if bi < 0 or bi > M-1 or bj <0 or bj > N-1:
return

if found:
return

if visited[bi][bj]:
return

if idx == len(word) - 1 and board[bi][bj] == word[idx]:
found = True
return
if board[bi][bj] == word[idx]:
if visited[bi][bj] == 0:
visited[bi][bj] = 1
back(idx+1, bi-1, bj)
back(idx+1, bi+1, bj)
back(idx+1, bi, bj+1)
back(idx+1, bi, bj-1)
visited[bi][bj] = 0
for i in range(M):
for j in range(N):
if board[i][j] == word[0]:
back(0, i, j)
if found:
return found
return False
```

# Dynamic Programming

Longest Palindromic Subsequence

```class Solution:
def longestPalindrome(self, s: str) -> str:
longest_seq = ''
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1 # fill the diagonal
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if s[i] == s[j]:
if len(s[i:j+1]) == 1 or len(s[i:j+1]) == 2 or dp[i+1][j-1] == 1:
dp[i][j] = 1
if len(longest_seq) < len(s[i:j+1]):
longest_seq = s[i:j+1]
return longest_seq
```

Pattern dp[i:j] holds the computation value of substring from index i to j. Since we must find all such substrings, we will do 2-d bottom up DP. DP mai we only do one diagonal traversal. Bottom Up diagonal travel up the DP table. DP[i][j] true if s[i] == s[j] & DP[i+1,j-1]

Generate Parenthesis

```class Solution:
@cache
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return [""]

if n == 1:
return ["()"]

ans = set()
for i in range(0, n):
inside = self.generateParenthesis(i)
outside = self.generateParenthesis(n-i-1)
for in_b in inside:
for out_b in outside:
return list(ans)
```

Pattern â€ś( inside ) outsideâ€ť. â€ś(f(i))f(n-i-1)â€ť Inside and outside are both recursive calls. Solve with memorization.

Jump Game 2

```class Solution:
def jump(self, nums: List[int]) -> int:
dp = [9999 for _ in range(len(nums))]
for i in range(len(nums)-1, -1, -1):
if i == len(nums)-1:
dp[i] = 0 # takes 0 steps to reach the last index
else:
for j in range(i+1, min(i+1+nums[i], len(nums))):
dp[i] = min(dp[i], 1 + dp[j])
return dp[0]
```

Pattern: (GOAL REACHING) Start from goal-state (similar to maze finding) and mark end-state cost to 0. Then for ith cell the cost is min(1+dp[i+1], dp[i]) Edge cases: for inner J loop, j (max jump limit) can be greater than remaining array length hence do min(j, len(nums))

Maximum Subarray

```class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [-999999 for _ in range(len(nums))]
global_max = -999999
for i in range(0, len(nums)):
dp[i] = max(dp[i-1]+nums[i], nums[i])
if global_max < dp[i]:
global_max = dp[i]
return global_max
```

## Pattern 1D array. Dp[i] = max(dp[i-1] + num[i], num[i])

Unique Paths

```class Solution:
def uniquePaths(self, m: int, n: int) -> int:

dp = [[0 for _ in range(n)] for _ in range(m)]

for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if i == m-1 or j == n-1:
dp[i][j] = 1
continue
else:
dp[i][j] = dp[i+1][j] + dp[i][j+1]

return dp[0][0]
```

Pattern (GOAL CHASING) start from goal state. Along the bottom and right edges the value of dp will be 1. Else dp[i][j] = dp[i+1][j] (down) + dp[i][j+1]

Best time to buy and sell stock 2

```class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 1:
return 0

profits = []
for i in range(1, len(prices)):
profits.append(max(0, prices[i] - prices[i-1]))
return sum(profits)
```

Pattern Find all subarrays that are increasing (i.e. all increasing sub sequences). This is like a foundation for LIS. Also note how considering [1, 2, 3], buy 1 sell 3 is equivalent to buy 1 sell 2 + buy 2 sell 3.

63. Unique Paths II

```class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
continue
if i == m-1 and j == n-1:
dp[i][j] = 1
continue
if i == m-1:
dp[i][j] = dp[i][j+1]
continue
if j == n-1:
dp[i][j] = dp[i+1][j]
continue
dp[i][j] = dp[i+1][j] + dp[i][j+1]
return dp[0][0]
```

Pattern: (GOAL CHASING) start from goal. If obstacle found mark dp cell to 0. If no Obstacle. Rest remains the same. Edge Cases/Errors: Be careful that for the assignment you dont do a == 12 instead of a = 12 (== vs =)

72. Edit Distance

```class Solution:
def minDistance(self, word1: str, word2: str) -> int:
if len(word1)== 0 or len(word2) == 0:
return max(len(word1), len(word2))

M = len(word1)
N = len(word2)

dp = [[0 for i in range(N+1)] for j in range(M+1)]

for i in range(M+1):
dp[i][0] = i
for j in range(N+1):
dp[0][j] = j

for i in range(1, M+1):
for j in range(1, N+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
continue
dp[i][j] = min(
dp[i-1][j-1]+1,
dp[i-1][j]+1,
dp[i][j-1]+1
)
return dp[-1][-1]
```

Pattern: 2-strings so 2-d dp matrix. Insert is increment in s1, delete is increment in s2 and increment is change in both. If char is same then 0 cost. Else cost is min(up, left, up-left)

91. Decode Ways

```class Solution:
def numDecodings(self, s: str) -> int:
if s[0] == 0:
return 0

dp = [0 for i in range(len(s))]
dp[0] = 1 if s[0] != "0" else 0
for i in range(1, len(s)):
ss = s[i] # curr char
ssp = s[i-1] # prev char
d1 = 0
d2 = 0
if ss != "0":
d1 = dp[i-1]
if ssp != "0" and int(ssp+ss) <= 26:
d2 = 1 if i-2 < 0 else dp[i-2]
dp[i] = d1 + d2
return dp[-1]
```

Pattern: 1 string partitioning/grouping. This always has 1d dp array. Think by doing dp[i] = f(dp[i-1]...)

97. Interleaving String

```class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s3) < len(s1)+len(s2):
return False

@cache
def dfs(p, q, t):
if p == len(s1) and q == len(s2) and t == len(s3):
return True

r1, r2 = False, False
if p < len(s1) and s1[p] == s3[t]:
r1 = dfs(p+1, q, t+1)

if q< len(s2) and s2[q] == s3[t]:
r2 = dfs(p, q+1, t+1)

return r1 or r2
return dfs(0,0,0)
```

Pattern: Memoization! Problems like this require backtracking. They cannot be expressed as a 1-d or 2-d DP table. You have to try out every combination and thats how you know you need memoization. Do â€śreturn dfs(p+1, q, t+1) or dfs(p, q+1, t+1)â€ť Errors: In Exit case I didnt check the index values well Before checking for char equality I didnt check if p less than the listâ€™s length-1

120. Triangle

```class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp = [0]
for i in range(len(triangle)):
temp_dp = dp.copy()
for j in range(len(triangle[i])):
if j == 0:
dp[j] = triangle[i][j] + temp_dp[j]
elif j == len(temp_dp):
dp.append(
triangle[i][j] + temp_dp[j-1]
)
else:
dp[j] = min(
triangle[i][j] + temp_dp[j],
triangle[i][j] + temp_dp[j-1]
)
return min(dp)
```

Pattern: i is triangle row and j is column. dp[j] = min(prev[i][j], prev[i][j-1]) Errors: Tried to do recursive backtrack and screwed up indexing. Took too much space and time

122. Best Time to Buy and Sell Stock II

```class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 1:
return 0
profits = []
for i in range(1, len(prices)):
profits.append(max(0, prices[i] - prices[i-1]))
return sum(profits)
```

Pattern: Find all subarrays that are increasing (i.e. all increasing sub sequences). This is like a foundation for LIS. Also note how considering [1, 2, 3], buy 1 sell 3 is equivalent to buy 1 sell 2 + buy 2 sell 3.

152. Maximum Product Subarray

```class Solution:
def maxProduct(self, nums: List[int]) -> int:
# SC: O(2N)
# TC: O(N)
# this can obviously be improved and maintained with
# a single variable
dp = [0 for i in range(len(nums))]
dpm = [0 for i in range(len(nums))]
dp[0] = nums[0]
dpm[0] = nums[0]
global_max = dp[0]
for i in range(1, len(nums)):
vals = (nums[i], nums[i]*dp[i-1], nums[i]*dpm[i-1])
dp[i] = max(vals)
if global_max < dp[i]:
global_max = dp[i]
dpm[i] = min(vals)
return global_max
```

Pattern: Subarray (Kadanes Algo). If contains -ve values & product then maintain min and max for DP.

198. House Robber

```class Solution:
def rob(self, nums: List[int]) -> int:
mem = {}
def recur(idx):
nonlocal nums
if idx < 0:
return 0

if idx in mem:
return mem[idx]

mem[idx] = max(
nums[idx]+recur(idx-2),
nums[idx]+recur(idx-3)
)
return mem[idx]
for i in range(len(nums)-1, -1, -1):
recur(i)
return max(mem.values())
```

Pattern: interleaving array question. f(i) = max(num[i]+f(i-2), num[i] + f(i-3)). Do this for all i. Note that if I dont do this for all i then there will be items in the array that I will NEVER reach! Errors: I did not through all indexes! There are multiple entrypoints to this function! I also did i-1 instead of i-2 for interleaving! Very bad and stupid!!

221. Maximal Square

```class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
M = len(matrix)
N = len(matrix[0])
dp = [[0 for _ in range(N)] for _ in range(M)]

best_cell = 0
for i in range(M):
for j in range(N):
if matrix[i][j] == "1":
if i == 0:
dp[i][j] = 1
elif j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(
dp[i-1][j],
dp[i-1][j-1],
dp[i][j-1]
) + 1
if dp[i][j] > best_cell:
best_cell = int(dp[i][j])

return best_cell*best_cell
```

Pattern: 2-D dp. Tricky question. Dp[i][j] = min(dp[i-1][j],dp[i-1][j-1], dp[i][j-1])+1. Then finally answer is max(dp)^2

213. House Robber II

```class Solution:
def rob(self, nums: List[int]) -> int:
def hr(nums):
dp = [0]*len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], nums[i]+dp[i-2])

return dp[-1]

if len(nums)==0: return 0
if len(nums) ==1: return nums[0]
if len(nums)==2:return max(nums)

return max(hr(nums[:-1]), hr(nums[1:]))
```

Pattern: important question on DP on looping arrays (i.e. array ends and loops back on itself). Trick is to realize that we can pick index 0 and exclude last index OR pick index last and exclude index 0. This is because in looped arrays index 0 and index last are continuous. SImple trick

241. Different Ways to Add Parentheses

```class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
ans = []
@cache
def recur(expr):
nonlocal ans
if expr == "":
return [0]
if len(expr) <= 4:
return [eval(expr)]
temp = ""
combs = []
for i in range(len(expr)-1):
if expr[i] in ["+", "-", "*"]:
left = recur(temp) # [2]
symbol = expr[i]
right = recur(expr[i+1:]) # [0]

for l in left:
for r in right:
print(f"{l}{symbol}{r}")
combs.append(eval(f"{l}{symbol}{r}"))
temp+= expr[i]
return combs
ans = recur(expression)
return ans
```

Pattern: Similar to number of ways to do parentheses. I.e f(s[:i])*f(s[i+1:]) for i going from i = 0 to len(s)-1 (last symbol can never be a sign!). Now important recursion pattern to note here is that, since the expectation is to have a list returned, we should also make our recursive function return lists! Simply do this: eval(fâ€ť{s[:i]}{s[i]}{s[i+1:]}â€ť), s[i] is the symbol

264. Ugly Number II

```class Solution:
def nthUglyNumber(self, n: int) -> int:
k = [0] * n
t1 = t2 = t3 = 0
k[0] = 1
for i in range(1, n):
k[i] = min(k[t1]*2, k[t2]*3, k[t3]*5)
if k[i] == k[t1]*2: t1+=1
if k[i] == k[t2]*3: t2+=1
if k[i] == k[t3]*5: t3+=1
return k[-1]
```

Pattern: creating increasing order products using given factors of numbers. Idk why this works yet. Will figure it out soon. Important pattern for when you get factoring related problems

338. Counting Bits

```from functools import reduce
class Solution:
def countBits(self, n: int) -> List[int]:
counter = [0]
for i in range(1, n+1):
counter.append(counter[i >> 1] + i % 2)
return counter
```

Pattern: Important bit manipulation question this is. TODO: handrun for deeper intuition Soâ€¦ num >> 1 is right bitshift by 1. This essentially has the effect of num//2. Now the i%2 is gonna be a 0 or a 1. All odd numbers will have 1 at the end in binary representation. So if the binary representation of 9 is 1001 then the code is essentially doing: Dp[100] + 1 Dp[10] + 0 Dp[1] + 0 1 (i.e. essentially going bit by bit and doing a count! So cool!)

343. Integer Break

```class Solution:
def integerBreak(self, n: int) -> int:
f = [0 for _ in range(n+1)]
f[1] = 1
for i in range(2, n+1):
for j in range(1, i//2+1):
f[i] = max(
f[i],
max(j, f[j]) *
max(i-j, f[i-j])
)
return max(f)
```

Pattern: 1-D DP problem. TODO: handrun for deeper intuition

377. Combination Sum IV

```class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target+1)
for i in range(target+1):
for n in nums:
if i == n:
dp[i] += 1
if n < i:
dp[i] += dp[i-n]
return dp[-1]
```

Pattern: This is a much more interesting pattern.

403. Frog Jump

```class Solution:
def canCross(self, stones: List[int]) -> bool:
stone_set = set(stones)
visited = set()
def dfs(stone, j):
nonlocal stones, stone_set, visited
if j <= 0:
return False
if stone + j not in stone_set:
return False
if (stone, j) in visited:
return False
if stone + j == stones[-1]:
return True
return dfs(stone+j, j) or dfs(stone+j, j+1) or dfs(stone+j, j-1)
return dfs(stones[0], 1)
```

Pattern: DFS traversal with set to check if stone exists. Do dfs(val+k, k-1) or dfs(val+k, k) or dfs(val+k, k-1). Note that first arg needs to remain constant because

413. Arithmetic Slices

```class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
N = len(nums)
dp = [0] * N
for i in range(2, N):
if nums[i]-nums[i-1] == nums[i-1]-nums[i-2]:
dp[i] = 1+dp[i-1]
return sum(dp)
```

Pattern: simple 1D dp. I tried to unnecessarily complicate it by trying to consider all possible subsets in a M*M DP grid.This just greedily checks if

746. Min Cost Climbing Stairs

```class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
cost.append(0)
dp = [0] * len(cost)
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, len(cost)):
dp[i] = min(cost[i] + dp[i-1], cost[i] + dp[i-2])

return dp[-1]
```

Pattern: 1-D DP. dp[i] = min(cost[i] + dp[i-1], cost[i] + dp[i-2])

368. Largest Divisible Subset

```class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
n = len(nums)
if n==0: return []
nums.sort()

dp = [[i] for i in nums]
for i in range(n):
for j in range(i):
if nums[i]%nums[j]==0 and len(dp[j])+1 > len(dp[i]):

dp[i] = dp[j]+[nums[i]]
return max(dp, key=len)
```

Pattern: 1-D dp but with 2d iteration! REVIEW!

983. Minimum Cost For Tickets

```class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
dp = [0] * len(days)
dp[0] = min(costs)

for i in range(1, len(days)):
candidates = [
dp[i-1] + costs[0]
]
j = i-1
while days[i] - days[j] < 7 and j >= 0:
j-=1
candidates.append(
dp[j] + costs[1]
)
while days[i] - days[j] < 30 and j >= 0:
j-=1
candidates.append(
dp[j] + costs[2]
)
dp[i] = min(candidates)
return dp[-1]
```

I wasnt able to solve this in last interview. Pattern: The trick is to simply ask yourself: what do I have to do if I have the optimal value for all day sizes and I am given one more day! Errors: I fucked up the indexing! I was trying to find the day that is 7 or 30 days away from current day. I did a j+=1 at the end to have my pointer point at the day that is inclusive of the N day window wrt current day. I should not have done this! Another issue is that I was doing days[i]-days[j] <= 7. This is wrong! Cuz 8-1 is also 7 but we cannot reach 8 from 1! Day traversal is inclusive of the days!

TODO

# Greedy

134. Gas Station

```class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost): return -1
tank = idx = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
idx = i+1
tank = 0
return idx
```

Pattern: We know if total gas is less than total cost then its not possible to do a round-trip. Hence return -1. Should sum(gas) < sum(cost) be a trivial thing? In fact this begs the question: Is sum(gas) and sum(cost) in some way the same thing? Cost is just -ve gas. Gas, well is just positive gas. If you knew that both these arrays were essentially just the same Gas object, then youâ€™d know it to be trivial. It is trivial. Think of it as how much gas we can gain and how much we can lose. If we can lose more than we can gain then we are fucked. For the next part of the question: We do a very cool traversal. We greedily go from 0 to N-1. We keep adding gas-cost for each station. If its -ve, start counting from that particular station. But why does this work? It is one thing to see it work but how do you arrive at the intuition on why it works?

Okay I get it now. The question is simple: If Iâ€™m coming from gas state

Here you can see that in case one, moving from 0 to 1 is possible and in this case we get 0 fuel left which is the same case as starting from 1 to 2. In case 2, from 0 to 1 we are unable to reach and hence life will be sad and we continue from 1. In last case if we have more additional fuel to add then we super happy. In general we can see that it is not possible to EVER have a case where if we were able to move from 0 to 2 we find a better path from 1 to 2. Because we are never adding -ve fuel!

334. Increasing Triplet Subsequence

```class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
f = s = float('inf')
for n in nums:
if n <= f:
f = n
elif n <= s:
s = n
else:
return True

return False
```

Pattern: Greedy hai. This is essentially peak-finding shiz. TODO: Draw diagrams for this!

150 String Encode Decode

There are multiple solutions that Iâ€™ve written for these. There is a good sol and a bad sol too

```class Solution:
def encode(self, strs: List[str]) -> str:
encoded = ""
for ss in strs:
encoded += str(len(ss)) + "|" + ss
return encoded

def decode(self, s: str) -> List[str]:
output = []
p = 0
charbuff = ""
while p < len(s):
c = s[p]
p+=1
continue
if c == "|" and reading:
p+=1
continue
charbuff += c
p+=1
continue
output.append(charbuff)
# p+=1
charbuff = ""
if charbuff != "" or s == "0|": output.append(charbuff)
return output
```

Issues that I faced in this approach:

Edge cases: When input was [] then I was returning [â€śâ€ť]. This is because charbuff always started off as â€śâ€ť string. When input was [â€śâ€ť] then after adding a fix for the above thing, simply doing: if charbuff != "": output.append(charbuff)) was not enough. When [â€śâ€ť] is given, it still thinks that there is nothing to decode and does not append charbuff to output list. This causes our code to break. To fix this I added a s == "0|" condition When lookahead is 0, then I was mistakenly doing p +=1. But I realized that doing so will often skip the numerical char and jump straight to the â€ś|â€ť char. The p pointer DOES NOT have to move every iteration. Itâ€™s a while loop. So we must not be tempted to think that p can be incremented every iteration. You just need to use the whileloop as a state machine. Forgot to set charbuff to â€śâ€ť in the last section Forgot to decrement lookahead when parsing the string

EDGE CASES! I NEED TO MAKE MY MIND THE PERFECT SIMULATOR FOR THE BRAIN

The above code was also poorly written because it tried to solve the question in a very complicated way. Here is my alternative solution:

```   def decode(self, s: str) -> List[str]:
output = []
i, j = 0, 0
while i < len(s):
while s[j] != "|": # or j < len(s)
j+=1
size = int(s[i:j]) #4|neet
output.append(s[j+1:j+1+size])
i = j + 1 + size
j = i
return output
```

Simpler two-pointer approach. i is being used to isolate the â€śsizeâ€ť of the strings. Itâ€™s easier to read. Due to reduced complications, it has fewer edge cases to follow. Now one important thing to note here is that, I made a mistake with the inner while loop which gave me an error. I had initially written this: while s[j] != "|" or j < len(s): Due to this the inner loop kept incrementing j because the OR condition on j

238 Product of Array Except Self

```import numpy as np
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
num_zeros = 0
product_with_zeros = 1
product_without_zeros = 1
l = len(nums)
for n in nums:
if n == 0:
num_zeros += 1
if num_zeros >= 2:
return [0] * len(nums)

product_with_zeros *= n
product_without_zeros *= n if n!=0 else 1

return [(product_with_zeros//n) if n!=0 else  product_without_zeros for n in nums]
```

In this code, the ask is to NOT use the // or division operator but we are still choosing to use it. The interesting observation to take note of here is that if an array has more than two 0s in it then the output will always have all zeros. This is a property that I shouldâ€™ve picked up much earlier. Hence I have the num_zero >= 2 condition in place. If there is a single 0 then, we introduce the product_without_zeros variable (which simply replaces that 0 with a 1)