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 go through in my free-time (bus-rides to GaTech). 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 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

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):
           if s[idx].isdigit():
               back(idx+1, path + [s[idx]])
               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
           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:
               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):
           if i == len(pattern) or pattern[i] == "I":
               while stack:

       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

           if nums[idx] - k not in counter and nums[idx] + k not in counter:
               counter[nums[idx]] += 1
               counter[nums[idx]] -= 1
               if not counter[nums[idx]]:
                   del counter[nums[idx]]
       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
Counter[nums[i]] -= 1

Like this:

       res = []
       path = []
       def find(idx):
           if idx > len(nums)-1:
       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
       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:
           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:

           if found:
           if visited[bi][bj]:

           if idx == len(word) - 1 and board[bi][bj] == word[idx]:
               found = True
           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:
   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

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.

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
               if i == m-1 and j == n-1:                   
                   dp[i][j] = 1
               if i == m-1:
                   dp[i][j] = dp[i][j+1]
               if j == n-1:
                   dp[i][j] = dp[i+1][j]
               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]
               dp[i][j] = min(
       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

       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):
                       triangle[i][j] + temp_dp[j-1]
                   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(
           return mem[idx]
       for i in range(len(nums)-1, -1, -1):
       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
                       dp[i][j] = min(
                       ) + 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 = []
       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:
               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(
                   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
           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

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

       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:
               dp[j] + costs[1]
           while days[i] - days[j] < 30 and j >= 0:
               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



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
                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 = []
       lookahead = 0
       reading = True
       p = 0
       charbuff = ""
       while p < len(s):
           c = s[p]
           if c.isnumeric() and reading:
               lookahead = lookahead*10 + int(c)
           if c == "|" and reading:
               reading = False
           if lookahead != 0:
               charbuff += c
               lookahead -= 1
           if lookahead == 0:
               # 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


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)
           size = int(s[i:j]) #4|neet
           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)

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