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've taken so far. 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
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))
[Maximum Subarray](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])
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.