CS After Dark

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.



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

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

        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))
                elif first + second + third > 0:
                    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<k). j+=1 if current_sum is less than target, k-=1 if current_sum > 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]]:

        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:
        if N == 2:
            op = self.twoSum(nums, target)
            if op != []:
                for idx in op:
                    ret.append(res + idx)
            for i in range(len(nums) - N + 1):
                if nums[i]*N > target or nums[-1]*N < target:
                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:

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

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

           curr = f"L{l}({node.val})R{r}"
           if curr in best and best[curr] == 1:
           best[curr] += 1
           return curr
       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]:
       if head is None:
           return head

       h = p1 = p2 = head
       space = k

       # separate the pointers
       len_list = 0
       while space >0:
           # print(len_list)
           if p2.next is None:
               p2 = h
               space = k%len_list
               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:
           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]
           elif nums[w] == 1:
               nums[w], nums[b] = nums[b], nums[w]

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]
               nums1[w] = nums2[p2]

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

TODO: Add more


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:

           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)

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

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.

Fair Distribution of Cookies


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

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

            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]
                    ans[i] -= cookies[idx]

        return best

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

def back(idx):

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:

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

            if len(edges) < 4:

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

        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]

Generate Parenthesis

class Solution:
   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
                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])

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

Graph Traversals

#algorithms #arrays #bfs #dfs #graphs #leetcode #trees