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
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:
triplets.add((first, second, third))
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
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)
TODO: Keep adding more patterns
Linked List and Trees
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:
# execute Task C
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.
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.
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None:
return head
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
# set head to p1
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
Intersection of two linked lists
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
seen = set()
p1 = headA
p2 = headB
while p1:
seen.add(id(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.
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.
TODO: Add more
Backtracking
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)
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
subsets = set()
def back(idx, path, k):
if len(path) == k: # exit
subsets.add(tuple(path))
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:
def distributeCookies(self, cookies: List[int], k: int) -> int:
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
ans.append(cookies[idx])
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:
ans[i] += cookies[idx]
back(idx+1)
ans[i] -= cookies[idx]
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):
visited.add(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;
- Exit when idx == len(array)
- Do push -> recurse -> pop until accumulator array not full (will typilcally have a max size)
- Do ans+i -> recurse -> ans+i TC: O(K^N)
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
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
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
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]
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:
ans.add(f"({in_b}){out_b}")
return list(ans)
Pattern “( inside ) outside”. “(f(i))f(n-i-1)” Inside and outside are both recursive calls. Solve with memorization.
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))
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])
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.
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 =)
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)
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]...)
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
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.
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.
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!!
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
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
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
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!)
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
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.
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
visited.add((stone, j))
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
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
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])
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!
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!
Graph Traversals
TODO
Greedy
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!
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 = []
lookahead = 0
reading = True
p = 0
charbuff = ""
while p < len(s):
c = s[p]
if c.isnumeric() and reading:
lookahead = lookahead*10 + int(c)
p+=1
continue
if c == "|" and reading:
reading = False
p+=1
continue
if lookahead != 0:
charbuff += c
lookahead -= 1
p+=1
continue
if lookahead == 0:
output.append(charbuff)
# p+=1
reading = True
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 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)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]