💭

Problem Solving with Python

🏝 Number of Islands
  • Given a 2d grid map of ’1’s (land) and ’0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
  • Want to count the number of islands
Attempt #1
class Solution:
    def numIslands(self, grid):
        rc = len(grid)
        if(rc == 0):
            return 0
        cc = len(grid[0])
        if (cc == 0):
            return 0
        count = 0

        for r in range(rc):
            for c in range(cc):
                if grid[r][c] == "1":
                    grid = self.connected(grid, r, c)
                    count += 1
        return count

    def connected(self, grid, r, c):
        if(grid[r][c] == "0"):
            return grid

        translations = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        rc = len(grid)
        cc = len(grid[0])
        grid[r][c] = "0"

        for t in translations:
            if(0 <= r + t[0] < rc and 0 <= c + t[1] < cc):
                grid = self.connected(grid, r + t[0], c + t[1])

        return grid
Lessons

BFS can be used. Union Find can also solve this problem.

  • Attempt #1
  • import string
    
    class Trie(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.val = None
            self.isEnd = False
            self.children = dict(
                zip(string.ascii_lowercase, [None for i in range(26)]))
    
        def insert(self, word):
            """
            Inserts a word into the trie.
            :type word: str
            :rtype: None
            """
            node = self
            children = node["children"]
            firstLetter = True
            for l in word:
                if children[str(l)] is not None:
                    node = children[str(l)]
                    children = node["children"]
                else:
                    children[str(l)] = Trie()
                    node = children[str(l)]
                    node.val = l
                    children = node["children"]
            node.isEnd = True
    
        def search(self, word):
            """
            Returns if the word is in the trie.
            :type word: str
            :rtype: bool
            """
            root = self
            stack = [{"node": root, "index": 0}]
            success = False
            while len(stack):
                n = stack.pop()
                print(n)
                if(n["index"] == len(word)):
                    success = True if (
                        word[-1] == n["node"]["val"]
                        and n["node"].isEnd) else False
                    if success:
                        return True
                else:
                    for c in n["node"]["children"].values():
                        if (c is not None and c.val == word[n["index"]]):
                            stack.append({"node": c, "index": n["index"] + 1})
            return False
    
        def startsWith(self, prefix):
            """
            Returns if there is any word in the trie that starts with the given prefix.
            :type prefix: str
            :rtype: bool
            """
            root = self
            stack = [{"node": root, "index": 0}]
            success = False
            while len(stack):
                n = stack.pop()
                if(n["index"] == len(prefix)):
                    success = True if (
                        prefix[-1] == n["node"]["val"]) else False
                    if success:
                        return True
                else:
                    for c in n["node"]["children"].values():
                        stack.append({"node": c, "index": n["index"] + 1} if (
                            c is not None and c.val == prefix[n["index"]]
                        ) else {"node": c, "index": 0})
            return False
Attempt #2
import collections


class Trie(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.isWord = False
        self.children = collections.defaultdict(Trie)

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: None
        """
        if self.search(word):
            return
        else:
            node = self
            for l in word:
                node = node.children[l]
            node.isWord = True

    def search(self, word, node=None):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self
        for l in word:
            if l in node.children:
                node = node.children[l]
            else:
                return False
        return node.isWord

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        node = self
        for l in prefix:
            if l in node.children:
                node = node.children[l]
            else:
                return False
        return True
Lessons & Mental Model
💡
Default Dict allows a simple way to insert values. A TrieNode does NOT need a value property You can cache methods
🔁 Rotate Image
  • You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).
Attempt #1
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix.reverse()
        self.transpose(matrix)

    def transpose(self, matrix):
        N = len(matrix)
        for i in range(N):
            for j in range(i + 1, N):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        return matrix
Lessons & Mental Model
💡
- To do a swap in python, you can do a, b = b, a - To get a transpose of matrix you can do zip(*A) - To assign values into a list you can use A[:] = something (saves memory)

Solution

📕 Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

  • Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1:
  • Attempt #1 (TLE and then Accepted after memoization)
    import re
    
    class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> bool:
            if len(s) == 0:
                return False
            hash = {}
            return self.search(s, wordDict, hash)
    
        def search(self, s, words, memo):
            if s in memo:
                return memo[s]
            if len(s) == 0:
                return True
            matches = []
            for w in words:
                if re.match(w, s) is not None:
                    matches.append("".join(re.split(w, s, 1)))
            for m in matches:
                res = self.search(m, words, memo)
                if res == True:
                    return res
            memo[s] = False
            return memo[s]
    Lessons & Mental Model
    💡
    - Decorators can be used to wrap functions (like cache) - self in pyton is equivalent to this in javascript - Strategy - use a trie, and do bfs with the trie
    class Trie(object):
      def __init__(self):
        self.cache = {}
    
      @cache
      def insert(self, word):
        pass
    
      def cache(f):
        def method(obj, s):
          if s not in obj.cache:
            obj.cache[s] = f(obj, s)
          return obj.cache[s]
        return method
  • Solution
  • Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Attempt #1
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maximum = -float('inf')
        N = len(nums)
        A = [[None for i in range(N)] for j in range(N)]
        for i, num in enumerate(nums):
            A[i][i] = num
            maximum = max([num, maximum])
        for i in range(N):
            for j in range(i + 1, N):
                A[i][j] = A[i][j - 1] * nums[j]
                if(A[i][j] > maximum):
                    maximum = A[i][j]
        return maximum
Lessons & Mental Model
💡
1. infinity in python is represented by float('inf') 2. you can use one array… how would you do that?

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Attempt #1
import collections

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        if n == 0:
            return 0
        A = [[0 for i in range(n)] for j in range(n)]

        for e in edges:
            [u,v] = e
            A[u][v] = 1
            A[v][u] = 1


        visited = {}
        count = 0
        stack = []

        for u in range(n):
            if u in visited:
                continue
            else:
                count+=1
                stack.append(u)
                while(len(stack)):
                    cur = stack.pop()
                    if cur in visited:
                        continue
                    else:
                        visited[cur] = True
                        neighbors = A[cur]
                        for i, nb in enumerate(neighbors):
                            if nb == 1:
                                stack.append(i)
                visited[u] = True
        return count
Lessons & Mental Model
💡
- You can do DFS with a stack - Connected components can be found with a union find algorithm
☘️ Construct a Quad Tree
🏍 Unique Paths
  • A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
  • The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
  • How many possible unique paths are there?
Attempt #1
import math


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if(m < 2 or n < 2):
            return (1 if m + n >= 2 else 0)
        A = [[1 for i in range(n)] for j in range(m)]

        for i in range(1, m):
            for j in range(1, n):
                A[i][j] = A[i - 1][j] + A[i][j - 1]
        return A[m - 1][n - 1]
Lessons & Mental Model:
💡
- This is a dynamic programming problem - What is the recursive formulation? - This can be done in O(n) space. How?
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        root.left, root.right = self.invertTree(
            root.right), self.invertTree(root.left)

        return root
🧳 Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (s_i < e_i), determine if a person could attend all meetings.

Attempt #1
from heapq import heappush, heappop

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        l = []
        [heappush(l, el) for el in intervals]
        if len(l) < 2:
            return True
        while len(l) > 1:
            interval1 = heappop(l)
            interval2 = heappop(l)
            if self.conflictExists(interval1, interval2):
                return False
            heappush(l, interval2)
        return True

    def conflictExists(self, one, two):
        return one[0] < two[0] < one[1] or two[0] < one[1] < two[1] or one[0] <= two[0] <= two[1] <= one[1]

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key = lambda x: x[0])

        for i in range(1, len(intervals)):
            if intervals[i-1][1] > intervals[i][0]:
                return False

        return True
Attempt #2
class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key = lambda x: x[0])

        for i in range(1, len(intervals)):
            if intervals[i-1][1] > intervals[i][0]:
                return False

        return True
Lessons & Mental Model
🏃🏿‍♂️ Longest Substring without Repeating characters
Attempt #1
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
      """
      Input:
      Output:
      Edge Cases:
      Constraints:
      Approaches:
      * Brute Force: Every length of substring and check O(n^2)
      * Sliding Window using two pointers and a dictionary
      """
        seen = {l: False for l in s}
        beg, end, res = 0, 0, 0
        while beg < len(s):
            while end < len(s) and not seen[s[end]]:
                seen[s[end]] = True
                end += 1
            res = max(res, end - beg)
            if end == len(s):
                break
            seen[s[beg]] = False
            beg += 1
        return res
Lessons
  1. Two Pointers: Increment end pointer while no repeating characters
🍩 Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Attempt #1
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        dp = [1, 1]

        for i in range(2, n + 1):
            dp.append(dp[i - 1] + dp[i - 2])

        return dp[-1]
Lessons & Mental Model
  1. Negative Indices nums[-1]
  2. It is fibonacci

Recursive Solution: dp[i] = dp[i-1] + dp[i-2]

🌱 Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = {}
        for num in nums:
            if num in seen:
                return True
            else:
                seen[num] = True
        return False

Solution

Lessons & Mental Model

You can extract unique elements from a list by creating a set object

🥓 Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example
  • Input: 1->2->4, 1->3->4
  • Output: 1->1->2->3->4->4
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = ListNode(None)
        node = root
        while(l1 and l2):
            node.next = (l1 if l1.val <= l2.val else l2)
            l1 = l1.next if node.next is l1 else l1
            l2 = l2.next if node.next is l2 else l2
            node = node.next
        node.next = l1 if l1 else l2
        return root.next
Lessons & Mental Model
  1. This is like the merge step in mergesort

Solution

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

First Attempt

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = self.adjacencyList(numCourses, prerequisites)
        status = [0 for _ in range(numCourses)]  # status = 0 means not visited
        for n in range(numCourses):
            if not self.detectCycle(adj, n, status): # DFS
                return False
        return True

    def detectCycle(self, adj, node, status):
        if(status[node] == -1):  # status = -1 means visiting
            return False
        if(status[node] == 1):  # status = 1 means done
            return True
        status[node] = -1
        neighbors = adj[node]
        for neighbor in neighbors:
            if not self.detectCycle(adj, neighbor, status):
                return False
        status[node] = 1
        return True

    def adjacencyList(self, size, edges):
        adj = [[] for _ in range(size)]
        while edges:
            i, j = edges.pop()
            adj[i].append(j)
        return adj

Solution

Lessons & Mental Model
  1. The key insight is that if we see a node that we have finished exploring a node, we have a cycle
  2. In DFS, each node can be white (undiscovered), grey (visited), black (complete)
🌳 Binary Tree Max Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Attempt #1 (TLE)
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        if(not root):
            return 0
        if(not root.left and not root.right):
            return root.val
        q = [root]
        nodes = []
        parent = {}
        allPairs = set()
        while q:
            cur = q.pop(0)
            nodes.append(cur)
            nbs = [cur.left, cur.right]
            for nb in nbs:
                if nb is not None:
                    parent[nb] = cur
                    q.append(nb)

        for i in range(len(nodes)):
            for j in range(i, len(nodes)):
                if tuple([nodes[j], nodes[i]]) not in allPairs:
                    allPairs.add((tuple([nodes[i], nodes[j]])))
        pathsums = {p: None for p in allPairs}
        allPairs = list(allPairs)
        while(allPairs):
            cur = allPairs.pop(0)
            if pathsums[cur] is None:
                self.pathSum(cur, pathsums, parent)

        return max(filter(None, pathsums.values()))

    def pathSum(self, pair, ps, parent):
        q = [[pair[0], pair[0].val]]
        while(q):
            cur, d = q.pop(0)
            if cur == pair[1]:
                ps[pair] = d
                return ps
            nbs = [cur.left, cur.right,
                   (None if cur not in parent else parent[cur])]
            for nb in nbs:
                if nb is not None:
                    q.append([nb, d + nb.val])
```
Attempt #2
def maxPathSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.res = -float('inf')
        self.oneSideSum(root)
        return self.res

    def oneSideSum(self, node):
        if not node:
            return 0

        leftST = max(0, self.oneSideSum(node.left))
        rightST = max(0, self.oneSideSum(node.right))

        self.res = max(self.res, leftST + rightST + node.val)

        return max(leftST, rightST) + node.val

Solution

Lessons & Mental Model
  • Really think about the problem statement. I initially thought this was an All Pairs Shortest Path problem and tried to solve it with a variation of the Floyd Warshall Algorithm. This meant that I needed to go through the tree and create parent references, and then look at all paths. This was a working solution, but it was too slow.
  • The actual solution is to find the maximum sum at each

Reverse a singly linked list.

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        s = []
        node = head
        while(node and node.next):
            tmp = node.next
            node.next = None
            s.append(node)
            node = tmp
        tail = node
        while s:
            node.next = s.pop()
            node = node.next
        return tail

Solution

Lessons & Mental Model
  1. You can use a stack to reverse a list (i.e. process in reverse order)
🐑 Clone Graph

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Solution:
    def cloneGraph(self, node: 'Node', clones={}) -> 'Node':
        if not node:
            return None
        if node in clones:
            return clones[node]
        clone = Node(node.val, [])
        clones[node] = clone
        for nb in node.neighbors:
            clone.neighbors.append(self.cloneGraph(nb, clones))
        return clone

Solution:

Lessons Learned:

  1. You want to use a hashmap to hash nodes to their clones and return the cached clone if the node has been seen and cloned before
🐽 Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

from collections import defaultdict


class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        I: Head of LL
        O: Reordered List (e.g. 1->2->3->4 => 1->4->2->3)
        C: Modify head in-place (No additional memory)
        E: Empty List => returns None
        """
        if head is None or head.next is None:
            return head
        l1, l2 = self.splitList(head)
        l2 = self.reverseList(l2)
        self.mergeList(l1, l2)

    def splitList(self, ll):
        l1, l2 = ll, None
        fast = ll
        slow = ll
        while(fast and fast.next):
            slow = slow.next
            fast = fast.next
            fast = fast.next
        l2 = slow.next
        slow.next = None
        return l1, l2

    def reverseList(self, ll):
        stack = []
        node = ll
        while node is not None:
            stack.append(node)
            tmp = node
            node = node.next
            tmp.next = None
        if stack:
            res = stack.pop()
            node = res
        else:
            return node
        while stack:
            node.next = stack.pop()
            node = node.next
        return res

    def mergeList(self, l1, l2):
        cur1 = l1
        cur2 = l2
        while(cur2):
            tmp1, tmp2 = cur1.next, cur2.next
            cur1.next, cur2.next = cur2, tmp1
            cur1, cur2 = tmp1, tmp2

Solution: https://leetcode.com/problems/reorder-list/discuss/447242/python-solution

Lessons Learned:

  1. Break the problem down into helper functions
🔍 Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

from collections import deque, defaultdict


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        """
        I:
        O:
        C:
        E:
        Approach:
        BFS
        """
        if not word:
            return True
        for row in range(len(board)):
            for col in range(len(board[0])):
                if(word[0] == board[row][col]):
                    if(self.dfs(word, 0, board, row, col)):
                        return True

        return False

    def dfs(self, word, idx, grid, gridRow, gridCol):
        char = grid[gridRow][gridCol]
        if char != word[idx]:
            return False
        elif idx == len(word) - 1:
            return True

        grid[gridRow][gridCol] = ""

        transformations = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        for rT, cT in transformations:
            if(0 <= rT + gridRow < len(grid) and 0 <= cT + gridCol < len(grid[0])):
                if(self.dfs(word, idx + 1, grid, rT + gridRow, cT + gridCol)):
                    return True
        grid[gridRow][gridCol] = char
        return False

Solution:

https://leetcode.com/problems/word-search/discuss/27660/Python-dfs-solution-with-comments

Lessons Learned:

  1. searching for existence usually means dfs
  2. deque
🕶 Decode Ways
  • A message containing letters from A-Z is being encoded to numbers using the following mapping:
  • ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.
Attempt #1 (Wrong)
class Solution:
    def numDecodings(self, s: str) -> int:
        if not s:
            return 0
        if len(s) == 1:
            return 0 if s=="0" else 1
        if s[0] == "0":
            return 0
        l = len(s)
        dp = [0] * l

        for i in range(l):
            dp[i] = 0 if s[i] == "0" else (1 if 2 < int(s) <= 9 else 2)
        for i in in range(l):
            if dp[i] == 2:
                dp[i] -= 1 if int(s[j:j+2]) > 26
        print([dp[i-1]* (dp[i] if dp[i] != 0 else 1) for i in range(1,l)])
Attempt #2
class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == "0":
            return 0
        l = len(s)
        dp = [1] + [0] * l

        for i in range(1, l + 1):
            dp[i] += (dp[i - 1] if s[i - 1] != "0" else 0)
            dp[i] += (dp[i - 2] if (i > 1 and 10 <= int(s[i - 2:i]) <= 26) else 0)
        return dp[-1]

Solution

🐛 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example
  • Input: [100, 4, 200, 1, 3, 2]
  • Output: 4
  • Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

First Attempt (TLE)


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        if len(nums) == 2:
            return 2 if abs(nums[0] - nums[1]) == 1 else 1
        mn = float('inf')
        mx = -float('inf')
        output = []
        counts = {}

        for num in nums:
            if num != float('inf') and num != float('inf'):
                mn = min(mn, num)
                mx = max(mx, num)
        for num in nums:
            if num != float('inf') and num != float('inf'):
                if(num not in counts):
                    counts[num] = 1
                else:
                    counts[num] += 1
        for j in range(mn, 0):
            if(j in counts):
                output.append(j)
        for i in range(mx + 1):
            if(i in counts):
                output.append(i)
        beg, end = 0, 0
        length = 1

        for i in range(1, len(output)):
            end += 1
            if (abs(abs(output[i]) - abs(output[i - 1])) != 1):
                length = max(length, end - beg)
                beg, end = i, i
        # print(output)
        # print(counts, end='\n')
        return max(length, end - beg + 1)

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        I: LL Node
        O: Boolean
        C: O(1) space if possible
        E: not head or not head.next
        """

        if not head or not head.next:
            return False
        slow = head
        fast = head.next
        hashmap = {slow: True}
        while fast and fast.next:
            if fast in hashmap:
                return True
            hashmap[slow] = True
            slow = slow.next
            fast = fast.next.next
        return False

Solution

Lessons
  • slow = head, fast = head.next
🍬 Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        if not len(matrix):
            return res

        while matrix:
            res.extend(matrix.pop(0))
            if matrix and matrix[0]:
                res.extend([row.pop() for row in matrix])
            if matrix:
                res.extend(matrix.pop()[::-1])
            if matrix and matrix[0]:
                res.extend([row.pop(0) for row in matrix][::-1])
        return res
🌷 Pacific Atlantic Water Flow
Attempt #1
class Solution:
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        res = []
        if not matrix:
            return res
        rc = len(matrix)  # row count
        cc = len(matrix[0])  # column count
        self.dir = [[0, 1], [1, 0], [-1, 0], [0, -1]] # Directions
        pacific = [[False for _ in range(cc)] for _ in range(rc)]
        atlantic = [[False for _ in range(cc)] for _ in range(rc)]

        # Which nodes can the sides reach?
        for i in range(rc):  # for the sides
            self.dfs(matrix, rc, cc, i, 0, pacific)
            self.dfs(matrix, rc, cc, i, cc - 1, atlantic)

        # Which nodes can the top/bottom reach?
        for i in range(cc):  # for the top and bottom
            self.dfs(matrix, rc, cc, 0, i, pacific)
            self.dfs(matrix, rc, cc, rc - 1, i, atlantic)

        for i in range(rc):
            for j in range(cc):
                if pacific[i][j] and atlantic[i][j]:
                    res.append([i, j])
        return res

    def dfs(self, grid, m, n, i, j, visited):
        if(visited[i][j]):
            return

        visited[i][j] = True

        for d in self.dir:
            x, y = d[0] + i, d[1] + j
            if (0 <= x < m and 0 <= y < n and grid[i][j] <= grid[x][y]):
                self.dfs(grid, m, n, x, y, visited)
Lessons & Mental Model
  1. I initially wanted to do a depth first search from every node to see if it termination condition could be reached. The termination condition was complicated and that kept on screwing my algorithm up. Instead the correct way to implement was to do a Depth first search from the outer layer of the matrix.
  2. self.directions = …
  3. x, y = dir[0] + i, dir[1] + y
  4. You can actually use a matrix to store results/path, instead of a hash table

Solution

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Attempt #1
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        return (self.preorderTraversal(root))

    def preorderTraversal(self, root):
        if not root:
            return ",None"
        return "," + str(root.val) + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        return self.buildTree(data[1:].split(','))

    def buildTree(self, l):
        if not l:
            return
        first = l.pop(0)
        root = None if first == "None" else TreeNode(int(first))
        if not root:
            return root
        root.left = self.buildTree(l)
        root.right = self.buildTree(l)
        return root
Attempt #2
from collections import deque


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        serialized = []
        q = deque([root])
        while(q):
            cur = q.popleft()
            serialized.append("None" if cur is None else str(cur.val))
            if serialized[-1] != "None":
                q.append(cur.left)
                q.append(cur.right)
        return ",".join(serialized)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        data = deque(data.split(','))
        val = data.popleft()
        root = None if val == "None" else TreeNode(int(val))
        q = deque([root])
        while q:
            cur = q.popleft()
            if cur:
                left, right = data.popleft(), data.popleft()
                cur.left = None if left == "None" else TreeNode(int(left))
                cur.right = None if right == "None" else TreeNode(int(right))
                q.append(cur.left)
                q.append(cur.right)
        return root

Solution

Lessons
  1. Preordered Traversal is the same as BFS
  2. deque takes an iterable

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example
  • nums = [1, 2, 3]
  • target = 4
  • The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Attempt #1
from collections import defaultdict


class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        """
        I: Array, Target Integer
        O: Number of ways to add numbers in the list to add up to target num
        C:
        E: Positive numbers? Negative Numbers? Zeros? Empty list?
        Approach:
        * Observation: The ways to add numbers in an array to add up to a target is the union of the ways to add up numbers in every subset of nums
        * Ex: cS4([1,2,3,4], 5) = cS4([2,3,4], 5) + cS4([1,3,4], 5) + cS4([1,2,4], 5) + cS4([1,2,3], 5) = ... = cS4([1], 5) + cS4([2], 5) + cS4([3], 5) + cS4([1]) + .... +
        1. Selected: Recursion, with Memoization since each subset will eventually end up calling the same problems
        2. Bottom up DP - dp[i][j] = dp[i]
        3. Similar to an unbounded knapsack problem
        """
        self.cache = [-1] * (target + 1)
        count = 0

        for num in nums:
            count += self.dfs(nums, target - num)

        return count

    def dfs(self, nums, target):
        if target < 0:
            return 0
        res = 0
        if self.cache[target] != -1:
            return self.cache[target]
        if target == 0:
            return 1
        for num in nums:
            res += self.dfs(nums, target - num)
        self.cache[target] = res
        return res
  • ⭐️Bonus: Which question is this question similar to? How are they different?

Solution

Lessons
  1. It is not varying the subarray, but rather the “target” and counting the ways that nums can make each “subtarget”
  2. => The subproblem is dp[i] += dp[i - nums[j]] if nums[j] > i where i is the “sub-target”
  3. Q: In the solution, why is the outer loop the amount, and not the nums? (A: Permutations, not combinations)

Bonus: Which question is this question similar to? How are they different?

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

First Attempt

Code:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [1] + [0] * amount
        for coin in coins:
            for i in range(amount + 1):
                if i - coin >= 0:
                    dp[i] += dp[i - coin]
        return dp[amount]

Solution:

https://leetcode.com/problems/coin-change-2/discuss/99222/Video-explaining-how-dynamic-programming-works-with-the-Coin-Change-problem

Lessons Learned:

  1. Q: Why is the outer loop the coins and not the amount?
⛺️ Meeting Rooms 2
  • Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.
Examples
  • Input: [[0, 30],[5, 10],[15, 20]]
  • Output: 2
  • Input: [[7,10],[2,4]]
  • Output: 1
Attempt #1
from heapq import heappop, heappush

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort()
        finishTimes = []
        heappush(finishTimes, intervals[0][1])

        for interval in intervals[1:]:
            if finishTimes[0] <= interval[0]:
                heappop(finishTimes)
            heappush(finishTimes, interval[1])

        return len(finishTimes)
Lessons
  1. heapify from heapq only heapifies one element, and does it in place
  2. to sort a list of objects you can pass a lambda function like below to the sort method
key = lambda x: x.start
  • Note: To get a reverse list you want to use [::-1]

Solution

📲 Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Examples
  • Input: nums = [1,1,1,2,2,3], k=2
  • Output: [1,2]
  • Input: nums = [1], k = 1
  • Output: [1]
  • Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
Attempt #1
from collections import defaultdict


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        if not nums or not k:
            return None
        frequencyTable = defaultdict(int)
        for num in nums:
            frequencyTable[num] += 1
        return sorted(frequencyTable.keys(), key=lambda x: frequencyTable[x], reverse=True)[:k]

Solution

Lessons
  1. Cant use .sort method on dict keys
🎆 Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example
Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.
Attempt #1
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s and not t:
            return True
        if not s or not t:
            return False
        if (self.sameTree(s, t)):
            return True

        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

    def sameTree(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        return s.val == t.val and self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)

Solution

Lessons

1. Think in terms of subroutines

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Attempt #1
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)
        return max(self.simple_rob(nums[1:]), self.simple_rob(nums[:-1]))

    def simple_rob(self, nums):
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)

        l = len(nums)
        dp = [0] * l

        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        for i in range(2, l):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        return max(dp)

Solution

Lessons

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Examples:
  • Input: [ [1,1,1], [1,0,1], [1,1,1]] Output: [ [1,0,1], [0,0,0], [1,0,1]]
  • Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5]] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0]]
  • Follow up: A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?
Attempt #1
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        if not matrix:
            return
        rows = set()
        cols = set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)

        def zeroRows(m, r_idx):
            for i in range(len(m[r_idx])):
                m[r_idx][i] = 0
            return m

        def zeroCols(m, c_idx):
            for i in range(len(m)):
                m[i][c_idx] = 0
            return m

        while(len(rows)):
            matrix = zeroRows(matrix, rows.pop())
        while(len(cols)):
            matrix = zeroCols(matrix, cols.pop())