📝 Data structures and algorithms

Some notes about DSA

https://leetcode.com/assessment/

Big O

• Neetcode
• Big O Cheat Sheet
• Recursive with multiple branches: O(branches^depth), if not repeated work, O(n).
• Fibonacci: O(2^n), with memoization: O(n)
• Permutations, TSP: O(n!)
• Binary search: O(log n) (divide search space)

Arrays

• Kadane’s algorithm: grow and check when to shrink

for n in nums:
    # need to shrink?
    if cur_sum+n < n: ...
    # update result
    if cur_sum > max_sum: ...

• Sliding window fixed size: l, r pointers and current window set

for r in range(len(nums)):
    if r-l+1 == k:
        ...

• Sliding window variable size: l, r pointers, iterate over r, grow while possible and shrink
• Two pointers: Palindrome, l, r extreme, choose which to move
• Prefix Sums: Get sum of any subarray in O(1), prefix / suffix products, etc

Basic & Hashing

• 🅱️Contains Duplicate☀️: 💡
  • nums = [1,2,3,1] => true
  • Hashmap seen or sort
  • O(n) time, O(n) space
• 🅱️Valid Anagram☀️: 💡
  • s = "anagram", t = "nagaram" => true
  • Counter for each string
  • O(s+t) time, O(1) space
• 🅱️🇬Two Sum☀️: 💡
  • nums = [2,7,11,15], target = 9 => [0,1]
  • Hashmap seen with index
  • O(n) time, O(n) space
• 🅱️Group Anagrams⛅: 💡
  • strs = ["tea","tan","ate","nat"] => [["nat","tan"],["ate","tea"]]
  • Counter for each string, use tuple as key
  • O(strings*average_lenth) time, O(strings) space
• 🅱️Top K Frequent Elements⛅: 💡
  • nums = [1,1,1,2,2,3], k = 2 => [1,2]
  • Counter, list of frequencies (len(nums)), iterate from end
  • O(n) time, O(n) space
• 🅱️Product of Array Except Self⛅: 💡
  • nums = [1,2,3,4] => [24,12,8,6]
  • Prefix product, Suffix product.
  • O(n) time, O(1) space
• 🇳Valid Sudoku⛅: 💡
  • partially filled 9x9 grid
  • sets, squares[(r // 3, c // 3)].add(board[r][c])
  • O(1) time, O(1) space
• 🅱️Encode and Decode Strings⛅: 💡
  • Create single string and split it back
  • Length + Separator
  • O(n) encode, O(n) decode
• 🅱️Longest Consecutive Sequence⛅: 💡
  • nums = [100,4,200,1,3,2] => 4
  • Set and start if n-1 not in set
  • O(n) time, O(n) space

Two Pointers

• 🅱️Valid Palindrome☀️: 💡
  • s = "A man, a plan, a canal: Panama" => true
  • Two pointers, if not s[i].isalnum(): i += 1
  • O(n) time, O(1) space
• 🇳Two Sum II⛅: 💡
  • numbers = [2,7,11,15], target = 9 => [1,2]
  • 2 pointers.
  • O(n) time, O(1) space
• 🅱️3Sum⛅: 💡
  • nums = [-1,0,1,2,-1,-4] => [[-1,-1,2],[-1,0,1]]
  • sort, 2 pointers
  • O(n^2) time, O(n) space (sorting)
• 🅱️Container With Most Water⛅: 💡
  • height = [1,8,6,2,5,4,8,3,7] => 49
  • start from both ends, move the smaller one
  • O(n) time, O(1) space
• 🇳Trapping Rain Water⛈️: 💡
  • height = [0,1,0,2,1,0,1,3,2,1,2,1] => 6
  • DP, can optimize to O(1) space by using 2 pointers (move l if leftmax < rightmax)
  • O(n) time, O(n) space

Sliding Window

• 🅱️🇬Best Time to Buy and Sell Stock☀️: 💡
  • prices = [7,1,5,3,6,4] => 5
  • Kadane’s algorithm
  • O(n) time, O(1) space
• 🅱️🇬Longest Substring Without Repeating Characters⛅: 💡
  • s = "abcabcbb" => 3 (“abc”)
  • Hashmap (seen, index), ans = max(ans, i - start + 1), update start if < index+1
  • O(n) time, O(1) space
• 🅱️Longest Repeating Character Replacement⛅: 💡
  • s = "ABAB", k = 2 => 4 (replace both A with B)
  • Window with most repeating, shrink if windowLen - max(count.values()) > k
  • O(n) time, O(1) space
• 🇳Permutation in String⛅: 💡
  • s1 = "ab" s2 = "eidbaooo" => true
  • Counter, sliding window of size len(s1)
  • O(n) time, O(1) space
• 🅱️Minimum Window Substring⛈️: 💡
  • s = "ADOBECODEBANC", t = "ABC" => "BANC"
  • Counter, if all window counter >= counter, shrink
  • O(n) time, O(1) space
• 🇳Sliding Window Maximum⛈️: 💡
  • nums = [1,3,-1,-3,5,3,6,7], k = 3 => [3,3,5,5,6,7]
  • l, r pointers, Monotonic dec deque, store idx, pop everything smaller than current
  • O(n) time, O(k) space

Stack

• 🅱️Valid Parentheses☀️: 💡
  • s = "()[]{}" => true
  • store last opened in stack
  • O(n) time, O(n) space
• 🇳Min Stack⛅: 💡
  • push(val), pop(), top(), getMin()
  • stack, append((min_so_far, val))
  • O(1) time, O(n) space
• 🇳 🇬Reverse Polish Notation⛅: 💡
  • tokens = ["2","1","+","3","*"] => 9
  • b, a = stack.pop(), stack.pop() … return stack[0]
  • O(2n) time, O(n) space
• 🇳Generate Parentheses⛅: 💡
  • n = 3 => ["((()))","(()())","(())()","()(())","()()()"]
  • stack, backtracking(opened, closed)
  • Exponential
• 🇳Daily Temperatures⛅: 💡
  • T = [73,74,75,71,69,72,76,73] => [1,1,4,2,1,1,0,0]
  • stack of pending indices, while current > stack[-1], pop and update ans
  • O(n) time, O(n) space
• 🇳Car fleet⛅: 💡
  • target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] => 3
  • Sort by position, start from end, if time to reach is faster than prev, ignore
  • O(nlogn) time, O(n) space
• 🇳Largest Rectangle in Histogram⛈️: 💡
  • heights = [2,1,5,6,2,3] => 10
  • stack, pop bigger than current, calculate area
  • O(n) time, O(n) space

Binary Search

Remember it can be used on a range.

• 🇳Binary Search☀️: 💡
  • nums = [-1,0,3,5,9,12], target = 9 => 4
  • while l <= r, mid = (l+r)//2
  • O(logn) time, O(1) space
• 🇳Search a 2D Matrix⛅: 💡
  • matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 => true
  • row = mid // len(matrix[0]), col = mid % len(matrix[0])
  • O(logmn) time, O(1) space
• 🇳Koko Eating Bananas⛅: 💡
  • piles = [3,6,7,11], H = 8 => 4
  • l, r = 1, max(piles), sum(math.ceil(p/mid) for p in piles) <= h
  • O(nlogm) time, O(1) space
• 🅱️Search in Rotated Sorted Array⛅: 💡
  • nums = [4,5,6,7,0,1,2], target = 0 => 4
  • see which side is sorted and then if target > nums[mid] or target < nums[l]
  • O(logn) time, O(1) space
• 🅱️Find Minimum in Rotated Sorted Array⛅: 💡
  • nums = [3,4,5,1,2] => 1
  • stop if nums[l] < nums[r], move l if nums[mid] >= nums[l]
  • O(logn) time, O(1) space
• 🇳Time Based Key-Value Store⛅: 💡
  • set(k, v, time), get(k, time)
  • if values[m][1] <= timestamp: res = values[m][0], l = m + 1
  • O(logn) time, O(n) space
• 🇳 🇬Median of Two Sorted Arrays⛈️: 💡
  • nums1 = [1,2], nums2 = [3,4] => 2.5
  • Binary search on the shorter array until Aleft <= Bright and Bleft <= Aright.
  • O(log(m+n)) time, O(1) space

Linked List

• 🅱️Reverse Linked List☀️: 💡
  • head = [1,2] => [2,1]
  • while cur: …, tmp, update prev and cur, return prev
  • O(n) time, O(1) space
• 🅱️Merge Two Sorted Lists☀️: 💡
  • l1 = [1,2,4], l2 = [1,3,4] => [1,1,2,3,4,4]
  • dummy first node, curr node, while l1 and l2, add remaining
  • O(n) time, O(1) space
• 🅱️Reorder List⛅ 💡
  • head = [1,2,3,4] => [1,4,2,3] (L0 -> Ln -> L1 -> Ln-1 -> L2…)
  • find mid, reverse second half, merge two lists
  • O(n) time, O(1) space
• 🅱️Remove Nth Node From End of List⛅: 💡
  • head = [1,2,3,4,5], n = 2 => [1,2,3,5]
  • Two pointers, move one n steps ahead.
  • O(n) time, O(1) space
• 🇳Copy List with Random Pointer⛅: 💡
  • head = [[3,null],[3,0],[3,null]] => [[3,null],[3,0],[3,null]]
  • two passes, copy and then update next and random, old_to_new = {None: None}
  • O(n) time, O(n) space
• 🇳 🇬Add Two Numbers⛅: 💡
  • l1 = [2,4,3], l2 = [5,6,4] => [7,0,8]
  • carry = sum_ // 10, remain = p1 or p2, etc.
  • O(max(m,n)) time, O(max(m,n)) space
• 🅱️Linked List Cycle☀️: 💡
  • head = [3,2,0,-4], -4 -> 2 => true
  • slow = fast = head, while fast and fast.next:
  • O(n) time, O(1) space
• 🇳Find The Duplicate Number⛅: 💡
  • nums = [1,3,4,2,2] => 2
  • Floyd’s cycle detection, slow = nums[slow]; fast = nums[nums[fast]], slow2
  • O(n) time, O(1) space
• 🇳LRU Cache⛅: 💡
  • LRUCache(int capacity), get(int key), put(int key, int value)
  • double linked list, cache of key to node, dummy head and tail
  • O(1) time, O(capacity) space
• 🅱️Merge K Sorted Lists⛈️: 💡
  • lists = [[1,4,5],[1,3,4],[2,6]] => [1,1,2,3,4,4,5,6]
  • Merge two lists at a time.
  • O(nlogk) time, O(1) space
• 🇳Reverse Nodes in k-Group⛈️: 💡
  • head = [1,2,3,4,5], k = 2 => [2,1,4,3,5]
  • groupPrev, groupNext, reverse while curr != groupNext
  • O(n) time, O(1) space

Trees

Careful with recursion limit (bound to the application stack)

• 🅱️Invert Binary Tree☀️: 💡
  • root = [4,2,7,1,3,6,9] => [4,7,2,9,6,3,1]
  • r.right, r.left = self.invert(r.left), self.invert(r.right) or stack
  • O(n) time, O(height) space
• 🅱️Maximum Depth of Binary Tree☀️: 💡
  • root = [3,9,20,null,null,15,7] => 3
  • return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
  • O(n) time, O(height) space
• 🇳Diameter of Binary Tree☀️: 💡
  • root = [1,2,3,4,5] => 3
  • dfs, path: res = max(res, left+right), max length: return max(left, right) + 1
  • O(n) time, O(height) space
• 🇳Balanced Binary Tree☀️: 💡
  • root = [3,9,20,null,null,15,7] => true
  • recursive, abs(height(left)-height(right)) <= 1
  • O(n) time, O(height) space
• 🅱️Same Tree☀️: 💡
  • p = [1,2,3], q = [1,2,3] => true
  • isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
  • O(n) time, O(height) space
• 🅱️Subtree of Another Tree☀️: 💡
  • s = [3,4,5,1,2], t = [4,1,2] => true
  • isSameTree(s, t) or isSubtree(s.left, t) or isSubtree(s.right, t)
  • O(nm) time, O(n+m) space
• 🅱️Binary Tree Level Order Traversal⛅: 💡
  • root = [3,9,20,null,null,15,7] => [[3],[9,20],[15,7]]
  • while level: ans.append([node.val for node in level]); level = [...] or queue
  • O(n) time, O(n) space
• 🇳Binary Tree Right Side View⛅: 💡
  • root = [1,2,3,null,5,null,4] => [1,3,4]
  • Level order, right most
  • O(n) time, O(n) space
• 🇳Count Good Nodes in Binary Tree⛅: 💡
  • root = [3,1,4,3,null,1,5] => 4
  • dfs, stack = [(node, max_so_far)]
  • O(n) time, O(height) space
• 🅱️Construct Binary Tree from Preorder and Inorder Traversal⛅: 💡
  • preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] => [3,9,20,null,null,15,7]

  root = TreeNode(preorder[0])
  i = inorder.index(root.val)
  root.left = self.buildTree(preorder[1:i+1], inorder[:i])
  root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
  

  • O(n) time, O(n) space
• 🅱️Binary Tree Maximum Path Sum⛈️: 💡
  • root = [1,2,3] => 6
  • dfs, allow split or not, nonlocal max
  • O(n) time, O(height) space
• 🅱️Serialize and Deserialize Binary Tree⛈️: 💡
  • serialize(self, root) and deserialize(self, data)
  • Preorder travelsal, "1,2,N,N,3,4,N,N,5,N,N"
  • O(n) time, O(n) space

BST: nodes left < node < nodes right

• 🅱️Lowest Common Ancestor of a Binary Search Tree⛅: 💡
  • root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 => 6
  • cur, left if p<cur and q<cur, right if p>cur and q>cur else return
  • O(n) time, O(1) space
• 🅱️Validate Binary Search Tree⛅: 💡
  • root = [2,1,3] => true
  • validate(n.left, min_val, n.val) and validate(n.right, n.val, max_val)
  • O(n) time, O(height) space
• 🅱️Kth Smallest Element in a BST⛅ 💡
  • root = [3,1,4,null,2], k = 1 => 1
  • inorder traversal, return res[k-1] (or iterative inorder with stack)
  • O(n) time, O(height) space

Tries

• 🅱️Implement Trie (Prefix Tree)⛅: 💡
  • insert(word), search(word), startsWith(prefix)
  • node with dict[char, node] and a bool isWord.
  • O(n) time, O(n) space
• 🅱️Design Add And Search Words Data Structure⛅: 💡
  • addWord(word), search(word)
  • trie, recursive dfs(idx, node) for “.”
  • O(n) time, O(n) space
• 🅱️Word Search II⛈️ 💡
  • board, words = ["oath","pea","eat","rain"] => ["eat","oath"]
  • build words trie from each cell, dfs
  • O(mn*4^mn) time, O(n) space (brute force O(wmn*4^mn))

Heap & Priority Queue

• Binary Tree
• Heap invariant: each node is <= than its children.
• Implemented as array: root at 0, children 2i+1 & 2i+2, parent at (i-1)//2

• 🇳Kth Largest Element in a Stream☀️: 💡
  • KthLargest(int k, int[] nums), add(num) -> int
  • simple minheap, pop if len > k, return heap[0]
  • O(logk) time, O(k) space
• 🇳Last Stone Weight☀️: 💡
  • stones = [2,7,4,1,8,1] => 1
  • Heapify, pop 2 largest, push diff, repeat while len > 1
  • O(nlogn) time, O(n) space
• 🇳K Closests Points to Origin⛅: 💡
  • points = [[1,3],[-2,2]], K = 1 => [[-2,2]]
  • simple maxheap (-dist, x, y), pop if len > k
  • O(nlogk) time, O(k) space
• 🇳Kth Largest Element in an Array⛅: 💡
  • nums = [3,2,1,5,6,4], k = 2 => 5
  • quickselect,
  • O(2n) average, O(n^2) worst case time, O(1) space
• 🇳Task Scheduler⛅: 💡
  • tasks = ["A","A","A","B","B","B"], n = 2 => 8
  • max_heap of times, queue, while max_heap or q, increase time
  • O(n) time, O(1) space
• 🇳Design Twitter⛅: 💡
  • postTweet, getNewsFeed, follow, unfollow
  • heap([count, tweetid, foloweeid, index-1])
  • O(nlogn) time, O(n) space
• 🅱️Find Median from Data Stream⛈️ 💡
  • addNum(num) and findMedian()
  • 2 heaps, max heap for left, min heap for right, balance
  • O(logn) time, O(n) space

Backtracking

• Subsets:
  • append to path, dfs, pop, dfs
  • if don’t want duplicates while loop to increase idx before second dfs
• Combinations:

  for j in range(i, n+1):
      path.append(j)
      dfs(j+1)
      path.pop()
  

• Permutations:

  def backtrack(first = 0):
      if first == n:
          output.append(nums[:])
      for i in range(first, n):
          nums[first], nums[i] = nums[i], nums[first]
          backtrack(first + 1)
          nums[first], nums[i] = nums[i], nums[first]
  

• 🇳Subsets⛅: 💡
  • nums = [1,2,3] => [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]
  • dfs with backtracking, result and path
  • O(n * 2^n) time, O(n) space (recursion stack)
• 🅱️Combination Sum⛅ 💡
  • candidates = [2,3,6,7], target = 7 => [[7],[2,2,3]]
  • dfs, backtracking, append path to global res
  • O(2^target) time, O(target) space
• 🇳Permutations⛅: 💡
  • nums = [1,2,3] => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
  • divide and conquer, remove first, recursive, add back
  • O(n^2*n!) time, O(n) space
• 🇳Subsets II⛅: 💡
  • nums = [1,2,2] => [[2],[1],[1,2,2],[2,2],[1,2],[]]
  • sort, while i+1 < len(nums) and nums[i] == nums[i+1]:
  • O(n * 2^n) time, O(n) space
• 🇳Combination Sum II⛅: 💡
  • candidates = [10,1,2,7,6,1,5], target = 8 => [[1,1,6],[1,2,5],[1,7],[2,6]]
  • dfs(pos, target), path = [], top if target <= 0
  • O(2^n) time, O(n) space
• 🅱️Word Search⛅ 💡
  • board = [["A","B","C","E"],["S","F","C","S"],...], word = "ABCCED" => true
  • dfs, backtracking, mark visited
  • O(mn*4^l) time, O(l) space
• 🇳Palindrome Partitioning⛅: 💡
  • s = "aab" => [["a","a","b"],["aa","b"]]
  • res = [], path = [], dfs(pos), for j in range(i, len(s))
  • O(n*2^n) time, O(n) space
• 🇳Letter Combinations of a Phone Number⛅: 💡
  • digits = "23" => ["ad","ae","af","bd","be","bf","cd","ce","cf"]
  • digit_to_char map, dfs, backtracking
  • O(n * 4^n) time, O(n) space
• 🇳N Queens⛈️: 💡
  • n = 4 => [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
  • dfs(row): for c in range(n), col, pos_diag, neg_diag sets
  • O(n!) time, O(n²) space

Graphs

• Dijkstra’s Algorithm: shortest path algo, greedy, O(ElogV) time

  shortest = {}
  heap = [(0, src)]
  while heap:
      w, node = heapq.heappop(heap)
      if node in shortest:
          continue
      shortest[node] = w
      for d, w2 in adj[node]:
          if d not in shortest:
              heapq.heappush(heap, (w + w2, d))
  

• Prim’s Algorithm: MST, O(ElogV) time, O(V) space

  heap = []
  for n, w in adj[0]:
      heapq.heappush(heap, (w, 0, n))
  visited = set()
  while heap:
      w, s, d = heapq.heappop(heap)
      if d in visited:
          continue
      mst.append((s, d))
      visited.add(d)
      for n, w2 in adj[d]:
          if n not in visited:
              heapq.heappush(heap, (w2, d, n))
  

• Kruskal: Union Find

• Topological Sort: Alien dict, dfs to the end and reverse, O(V+E) time, O(V) space

  result = []
  #cycle = set()
  visited = set()
  def dfs(node):
      if node in visited:
          return
      visited.add(node)
      for n in adj[node]:
          dfs(n)
      result.append(node)
      #cycle.remove(node)
  for i in range(...):
      dfs(i)
  return result[::-1]
  

Basic

• 🅱️🇬Number of Islands⛅: 💡
  • grid = [["1", "0"], ["0", "1"]] => 2
  • skip visited (mark 0 or set), dfs (4 directions) on 1s.
  • O(cells) time, O(cells) space
• 🅱️Clone Graph⛅: 💡
  • Node with val, neighbors.
  • cache[old] = copy, for n in neighbors: copy.neighbors.append(dfs(n))).
  • O(v+e) time, O(v) space
• 🇳 🇬Max Area of Island⛅: 💡
  • grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],...,[0,0,0,0,0,0,0,1,1,1,0,0,0]] => 6
  • return 1 + dfs(4 directions), max_area = max(max_area, dfs)
  • O(mn) time, O(mn) space
• 🅱️🇬Pacific Atlantic Water Flow⛅: 💡
  • grid of heights.
  • start from edge and dfs(x, y, ocean, last_height) to higher, return set intersection
  • O(mn) time, O(mn) space
• 🇳Surrounded Regions⛅: 💡
  • board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
  • dfs regions connected to edge, mark temporary, flip rest.
  • O(mn) time, O(1) space
• 🇳Rotting Oranges⛅: 💡
  • grid = [[2,1,1],[1,1,0],[0,1,1]] => 4
  • BFS, while queue: minutes+=1 for i in range(len(queue)), check if any remain
  • O(nm) time, O(nm) space
• 🇳Walls and Gates⛅: 💡
  • rooms = [[2147483647,-1,0,2147483647],...,[2147483647,2147483647,2147483647,-1]]
  • BFS, while queue pop left, add to queue if rooms[r][c] > rooms[i][j]+1
  • O(nm) time, O(nm) space
• 🅱️Course Schedule⛅: 💡
  • DFS cycle detection (visited set, cycle set).
  • O(v+e) time, O(v) space
• 🇳 🇬Course Schedule II⛅: 💡
  • numCourses = 2, prerequisites = [[1,0]] => [0,1]
  • DFS topological sort, return [] if cycle, visited and cycle set
  • O(v+e) time, O(v) space
• 🇳Redundant Connection⛅: 💡
  • edges = [[1,2], [1,3], [2,3]] => [2,3]
  • union find, return edge if cycle (parent == parent[y])
  • O(n+m) time, O(n) space
• 🅱️Number of Connected Components in an Undirected Graph⛅: 💡
  • n = 5, edges = [[0, 1], [1, 2], [3, 4]] => 2
  • union find
  • O(n+m) time, O(n) space
• 🅱️Graph Valid Tree⛅: 💡
  • n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]] => true
  • adj list, DFS cycle detection, dfs(0, prev=-1) and n == len(visit)
  • O(e+v) time, O(e+v) space
• 🇳Word Ladder⛈️: 💡
  • beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] => 5
  • BFS, queue, create adj list with patterns pattern = word[:i] + '*' + word[i+1:]
  • O(m^2n) time, O(m^2n) space

Advanced

• 🇳Reconstruct Itinerary⛈️: 💡
  • tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] => ["JFK","MUC","LHR","SFO","SJC"]
  • adj list, sort (lexico), dfs
  • O(n_flights^max_airport_f) time, O(n_airports+n_flights) space
• 🇳Min Cost to Connect All Points⛅: 💡
  • points = [[0,0],[2,2],[3,10],[5,2],[7,0]] => 20
  • Prim’s algorithm, weigth, s, d = heapq.heappop(heap)
  • O(n^2) time, O(n) space
• 🇳Network delay time⛅: 💡
  • times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2 => 2
  • Dijkstra’s algorithm, visited set instead of dist
  • O(elogv) time, O(e+v) space
• 🇳 🇬Swim in Rising Water⛈️: 💡
  • grid = [[0,2],[1,3]] => 3
  • Simple Dijkstra, heapq.heappush(heap, (max(t, grid[r][c]), r, c))
  • O(n^2 log n) time, O(n^2) space
• 🅱️Alien Dictionary⛈️: 💡
  • topological sort, DFS cycle detection.
• 🇳Cheapest Flights Within K Stops⛅: 💡
  • n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 => 200
  • BellmanFord, BFS (k+1 times), create tmp_dist and distances = tmp_dist at the end
  • O(k*e) time, O(k*e) space

Dynamic Programming

https://youtu.be/mBNrRy2_hVs

• Fibonacci: dp[i] = dp[i-1] + dp[i-2]
• Zero / One Knapsack:
• Unbounded Knapsack:
• Longest Common Subsequence:
• Palindromes:

1D

https://youtu.be/_i4Yxeh5ceQ

• 🅱️Climbing Stairs☀️: 💡 Fibonacci
  • n = 2 => 2, n = 3 => 3
  • temp = n1 + n2
  • O(n) time, O(1) space
• 🇳Min cost climbing stairs☀️: 💡
  • cost = [10, 15, 20] => 15 (start from 0 or 1, 1 or 2 steps)
  • new = min(prev1+c[i-2], prev2+c[i-1]); prev1 = prev2; prev2 = new
  • O(n) time, O(1) space
• 🅱️House Robber⛅: 💡
  • nums = [2,7,9,3,1] => 12 (2, 9, 1)
  • rob1, rob2 = 0, 0, tmp = max(rob1 + n, rob2), return rob2
  • O(n) time, O(1) space
• 🅱️House Robber II⛅: 💡
  • nums = [2,3,2] => 3 (circular)
  • max(nums[0], rob1(nums[1:]), rob1(nums[:-1]))
  • O(n) time, O(1) space
• 🅱️🇬Longest Palindromic Substring⛅: 💡
  • s = "babad" => "bab" or "aba"
  • for i in range(len(s)): expand around l, r = 1, 1 and l, r = i, i+1
  • O(n^2) time, O(1) space
• 🅱️Palindrome Substrings⛅: 💡
  • s = "abc" => 3 (a, b, c)
  • similar to the preview one, expand and add to count
  • O(n^2) time, O(1) space
• 🅱️Decode Ways⛅: 💡
  • s = "12" => 2 (“AB” or “L”)
  • start from end, dp[i] = dp[i+1] add dp[i+2] if dp[i:i+2] is valid
  • O(n) time, O(n) space
• 🅱️Coin Change⛅: 💡 Unbounded Knapsack
  • coins = [1,2,5], amount = 11 => 3
  • Cache and iterate range(amount+1), recursive is O(coins^amount)
  • O(coins*amount) time, O(amount) space
• 🅱️Maximum Product Subarray⛅: 💡
  • nums = [2,3,-2,4] => 6 (2, 3)
  • cur_max, cur_min, max_prod = 1, 1, float('-inf'), reset if n == 0
  • O(n) time, O(1) space
• 🅱️Word Break⛅: 💡
  • s = "leetcode", words = ["leet", "code"] => true
  • start from end, dp[i] = any(dp[i+len(w)] for w in words if s[i:i+len(w)] == w)
  • O(n^2) time, O(n) space
• 🅱️Longest Increasing Subsequence⛅: 💡
  • nums = [10,9,2,5,3,7,101,18] => 4 (2, 3, 7, 101) strict
  • start from end, if nums[i] < nums[j]: dp[i] = max(dp[i], dp[j] + 1)
  • O(n^2) time, O(n) space
• 🇳Partition Equal Subset Sum⛅: 💡
  • nums = [1,5,11,5] => true (1, 5, 5) and (11)
  • target is sum//2, possible = possible.union({p+n for p in possible})
  • O(n*target) time, O(target) space

2D

• 🅱️🇬Unique Paths⛅ 💡
  • m = 3, n = 2 => 3
  • cache[0, 0] = 1; cache[i, j] = cache.get((i-1, j), 0) + cache.get((i, j-1), 0)
  • O(m*n) time, O(m*n) space
• 🅱️Longest Common Subsequence⛅ 💡
  • text1 = "abcde", text2 = "ace" => 3 (“ace”)
  • dp/recursive, add one and increase both if equal, else get the max of i+1 and j+1
  • O(m*n) time, O(m*n) space (can be reduced)
• 🇳Best Time to Buy and Sell Stock with Cooldown⛅: 💡
  • prices = [1,2,3,0,2] => 3 (buy at 1, sell at 3, buy at 0, sell at 2)
  • cache[i, can_buy], handle cooldown, can_buy and not can_buy
  • O(n) time, O(n) space
• 🇳Coin Change 2⛅: 💡
  • amount = 5, coins = [1, 2, 5] => 4
  • Unbounded Knapsack, dfs(i, amount) = dfs(i+1, amount) + dfs(i, amount-coins[i])
  • O(n*amount) time, O(n*amount) space
• 🇳Target Sum⛅: 💡
  • assign + or - nums = [1, 1, 1, 1, 1], target = 3 => 5
  • 0/1 Knapsack, O(2^n) -> O(n*sum(nums)))
• 🇳Interleaving String⛅: 💡
  • s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbc
  • check lengths, if i < len(s1) and s1[i] == s3[i+j] and dfs(i+1, j): True
  • O(n*m) time, O(n*m) space
• 🇳 🇬Longest Increasing Path in a Matrix⛈️: 💡
  • matrix = [[9,9,4],[6,6,8],[2,1,1]] => 4 (1, 2, 6, 9)
  • result = max(result, 1+dfs(ii, jj)), dfs every cell
  • O(m*n) time, O(m*n) space
• 🇳Distinct Subsequences⛈️: 💡
  • s = "rabbbit", t = "rabbit" => 3 (rabbbit, rabbbit, rabbbit)
  • if same: dfs(i+1, j+1) + dfs(i+1, j) else dfs(i+1, j)
  • O(n*m) time, O(n*m) space
• 🇳Edit Distance⛈️: 💡
  • word1 = "horse", word2 = "ros" => 3
  • lru_cache, dp(len(s1), len(s2))
  • O(m*n) time, O(m*n) space
• 🇳Burst Balloons⛈️: 💡
  • nums = [3,1,5,8] => 167 (3*1*5 + 3*5*8 + 1*3*8 + 1*8*1)
  • nums = [1] + nums + [1], dfs(1, lens(nums)-2)
  • O(n^3) time, O(n^2) space
• 🇳Regular Expression Matching⛈️: 💡
  • s = "aa", p = "a" => false
  • match = s[i] == p[j] or p[j] == '.', handle *, recursive
  • O(m*n) time, O(m*n) space (with cache)

Greedy

• 🅱️🇬Maximum Subarray⛅: 💡
  • nums = [-2,1,-3,4,-1,2,1,-5,4] => 6 ([4,-1,2,1])
  • current_sum = max(current_sum+n, n), Kadane.
  • O(n) time, O(1) space
• 🅱️Jump Game⛅: 💡
  • nums = [2,3,1,1,4] => true (can reach last index)
  • start from end, if i + nums[i] >= target: target = i.
  • O(n) time, O(1) space
• 🇳Jump Game II⛅: 💡
  • nums = [2,3,1,1,4] => 2 (jump 1 step from index 0 to 1, then 3 steps to the last index)
  • l = r = 0, farthest, l = r+1, r = farthest, count += 1
  • O(n) time, O(1) space
• 🇳Gas Station⛅: 💡
  • gas = [1,2,3,4,5], cost = [3,4,5,1,2] => 3 (start at index 3)
  • check sum(gas) >= sum(cost), if total is negative, reset and start from next index.
  • O(n) time, O(1) space
• 🇳Hand of Straights⛅: 💡
  • hand = [1,2,3,6,2,3,4,7,8], W = 3 => true
  • counter, iterate keys
  • O(n+klogk) time, O(n) space
• 🇳Merge Triplets to Form Target Triplet⛅: 💡
  • triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] => true
  • if any(triplet[i] > target[i] for i in range(3)): continue, update found[i]
  • O(n) time, O(1) space
• 🇳Partition Labels⛅ 💡
  • s = "ababcbacadefegdehijhklij" => [9,7,8]
  • last_idx = {}, end = max(idx, last_idx[c]), if idx == end, add to result.
  • O(n) time, O(1) space
• 🇳Valid Parenthesis String⛅: 💡
  • s = "(*)" => true
  • left_min, left_max, if l_max < 0: return False, if l_min < 0: l_min = 0.
  • O(3^n)->O(n³)->O()

Intervals

• 🅱️🇬Insert Interval⛅: 💡
  • intervals = [[1,3],[6,9]], newInterval = [2,5] => [[1,5],[6,9]] (sorted)
  • if newInterval[1] < interval[0], if newInterval[0] > interval[1], else merge
  • O(n) time, O(n) space
• 🅱️🇬Merge Intervals⛅: 💡
  • intervals = [[1,3],[2,6],[8,10],[15,18]] => [[1,6],[8,10],[15,18]]
  • Sort by start, append to result and merge if start <= result[-1][1]
  • O(nlogn) time, O(n) space
• 🅱️Non-overlapping Intervals⛅: 💡
  • intervals = [[1,2],[2,3],[3,4],[1,3]] => 1 (number of intervals to remove)
  • sort, update if start >= prev.end, else increase count
  • O(nlogn) time, O(1) space
• 🅱️Meeting Rooms☀️: 💡
  • intervals = [(0,30),(5,10),(15,20)] => false
  • sort, if start < prev.end, return false
  • O(nlogn) time, O(n) space
• 🅱️🇬Meeting Rooms II⛅: 💡 min number of conference rooms.
  • intervals = [(0,30),(5,10),(15,20)] => 2
  • sorted starts and ends, s and e pointers, increment count if start[s] < end[e]
  • O(nlogn) time, O(n) space
• 🇳Minimum Interval to Include Each Query⛈️: 💡
  • intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] => [3,-1,3,4]
  • sort intervals & queries, heap (length, end), pop if end < query, dict[query] = length
  • O(nlogn + qlogq) time, O(n+q) space

Math & Geometry

• 🅱️Rotate Image⛅: 💡
  • matrix = [[1,2,3],[4,5,6],[7,8,9]] => [[7,4,1],[8,5,2],[9,6,3]]
  • while l < r, swap 4 corners, move inwards
  • O(n^2) time, O(1) space
• 🅱️Spiral Matrix⛅: 💡
  • matrix = [[1,2,3],[4,5,6],[7,8,9]] => [1,2,3,6,9,8,7,4,5]
  • 4 pointers, left, right, top, bottom, while l <= r and t <= b
  • O(n^2) time, O(1) space
• 🅱️Set Matrix Zeroes⛅: 💡
  • matrix = [[1,1,1],[1,0,1],[1,1,1]] => [[1,0,1],[0,0,0],[1,0,1]]
  • use first row and column to store if row or column should be zeroed
  • O(mn) time, O(1) space
• 🇳 🇬Happy Number☀️: 💡
  • n = 19 => true (12 + 92 = 82 |...| 12 + 02 + 02 = 1)
  • Hashset seen or Floyd’s cycle detection
• 🇳Plus One☀️: 💡
  • digits = [1,2,3] => [1,2,4]
  • carry = (digits[i]+carry) // 10, return [1]+result if carry
  • O(n) time, O(n) space
• 🇳Pow(x, n)⛅: 💡
  • x = 2.00000, n = 10 => 1024.00000
  • helper(x, abs(n)), recursive helper
  • O(n) time, O(n) space
• 🇳Multiply Strings⛅: 💡
  • num1 = "2", num2 = "3" => "6"
  • Manual multiplication, reverse, for in for
  • O(nm) time, O(n+m) space
• 🇳 🇬Detect Squares⛅: 💡
  • points = [[3,10],[11,5],[11,10]] => [true,false,true]
  • res += self.points_count[x, py] * self.points_count[px, y]
  • O(n) time, O(n) space

Bit Manipulation (rare)

Summary

Extra

Sorting:

• …

Easy:

• 🇬Logger Rate Limiter: 💡
  • shouldPrintMessage(1, "foo"), shouldPrintMessage(3, "foo") => true, false
  • Hashmap {message: timestamp}, if self.cache[message] + 10 > timestamp
  • O(1) time, O(n) space
• 🇬First Bad Version: 💡
  • n = 5, isBadVersion(3) = false, isBadVersion(4) = true
  • binary search.
  • O(logn) time, O(1) space
• 🇬Longest Common Prefix: 💡
  • strs = ["flower","flow","flight"] => "fl"
  • iterate first word and compare
  • O(n) time, O(1) space
• 🇬Tic tac toe: 💡
  • moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] => "A"
• 🇬Palindrome Number: 💡
  • x = 121 => true
  • calculate divider, use mod
  • O(logn) time, O(1) space
• 🇬Roman to Integer: 💡
  • s = "III" => 3
  • iterate, roman_dict, if roman[i] < roman[i+1]: res -= roman[i]
  • O(n) time, O(1) space

Medium:

• 🇬Range Sum Query - Mutable: 💡
  • update(i, val), sumRange(i, j)
  • Segment tree

  class Node(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None
  

  • O(logn) time, O(n) space
• 🇬Subarray Sum Equals K: 💡
  • nums = [1,1,1], k = 2 => 2 ([1, 1] and [1, 1])
  • prefix sum, if increase by k, found (subarray in between), initialize d[0] = 1
  • O(n) time, O(n) space
• 🇬Find original array from doubled array: 💡
  • changed = [1,3,4,2,6,8] => [1,3,4]
  • iterate sorted count, if count[2*x] >= count[x], handle 0, cnt[2*x] -= cnt[x]
  • O(n + mlogm) time, O(m) space (m = unique elements)
• 🇬Decode String: 💡
  • s = "3[a]2[bc]" => "aaabcbc"
  • append to stack if != ']', pop and multiply
  • O(n_output) time, O(n_output) space
• 🇬My Calendar I: 💡
  • book(start, end), book(10, 20), book(15, 25), book(20, 30)
  • List (deque) + binary search
  • O(n) time, O(n) space
• 🇬Random Pick with Weight: 💡
  • [1,3], pickIndex() => 0 with 25% probability, 1 with 75% probability
  • binary search (random (1, total)) on the prefix sum.
  • O(n) time, O(n) space
• 🇬Number of matching subsequences: 💡
  • s = "abcde", words = ["a","bb","acd","ace"] => 3
  • Hashmap {char: [(word_idx, current_idx)]}
  • O(s.length+sumcharwords) time, O(#words) space
• 🇬Longest String Chain: 💡
  • words = ["a","b","ba","bca","bda","bdca"] => 4 (a, b, ba, bda)
  • start with shortest, for each word, check if word[:i]+word[i+1:] in dp
  • O(nlog(n) + nll) time, O(ns) space
• 🇬Step-By-Step Directions From a Binary Tree Node to Another: [💡]
  • TODO
  • …
• 🇬The Number of Weak Characters in the Game: 💡
  • properties = [[5,5],[6,3],[3,6]] => 0
  • sort by -x[0],x[1], then iterate and keep max y
  • O(nlogn) time, O(1) space
• 🇬Maximum Points You Can Obtain from Cards: 💡
  • cardPoints = [1,2,3,4,5,6,1], k = 3 => 12
  • Sliding window, minimum subarray of size n-k.
  • O(n) time, O(1) space
• 🇬Stock Price Fluctuation: 💡
  • update(int timestamp, int price), current(), maximum(), minimum()
  • 2 heaps, timestamps[time, price], self.highest_timestamp.
• 🇬Find Leaves of Binary Tree: [💡]
  • dfs, post-order, return layer.
• 🇬Snapshot Array: 💡
  • SnapshotArray(int length), set(index, val), snap(), get(index, snap_id)
  • Dict[int, array], binary search on the list of snapshots.
• 🇬Minimum Time Difference: 💡
  • timePoints = ["23:59","00:00"] => 1
  • map to minutes & sort, (time[i]-time[i-1])%(24*60)
  • O(nlogn) time, O(n) space
• 🇬Find All Possible Recipes from Given Supplies: 💡
  • TODO
  • …
• 🇬https://leetcode.com/problems/battleships-in-a-board/?md
• 🇬https://leetcode.com/problems/find-and-replace-in-string/?md
• 🇬https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/?md
• 🇬https://leetcode.com/problems/swap-adjacent-in-lr-string/?md
• 🇬https://leetcode.com/problems/sort-integers-by-the-power-value/?md
• 🇬https://leetcode.com/problems/maximum-number-of-points-with-cost/?md
• 🇬https://leetcode.com/problems/detonate-the-maximum-bombs/?md
• 🇬https://leetcode.com/problems/filling-bookcase-shelves/?md
• 🇬https://leetcode.com/problems/shortest-way-to-form-string/?md
• 🇬https://leetcode.com/problems/rle-iterator/?md
• 🇬https://leetcode.com/problems/check-if-word-can-be-placed-in-crossword/?md
• 🇬https://leetcode.com/problems/sentence-screen-fitting/?md
• 🇬https://leetcode.com/problems/parallel-courses/?md
• 🇬https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/?md
• 🇬https://leetcode.com/problems/find-duplicate-subtrees/?md
• 🇬https://leetcode.com/problems/bulls-and-cows/?md
• 🇬https://leetcode.com/problems/time-needed-to-inform-all-employees/?md

Hard:

• 🇬Race Car: 💡
  • TODO
  • …
• 🇬Text Justification: 💡
  • words = ["This", "is", "an", "example", "of", "text", "justification."] w = 16 => ["This is an", "example of text", "justification. "]
  • if num_of_letters + len(w) + len(cur) > maxWidth:, round robin
• 🇬Shortest Path in a Grid with Obstacles Elimination: 💡
  • TODO
  • …
• 🇬Poor Pigs: 💡
  • buckets = 1000, minutesToDie = 15, minutesToTest = 60 => 5
  • TODO
  • …
• 🇬https://leetcode.com/problems/maximum-number-of-visible-points/?hd
• 🇬Range Module 💡
  • TODO
  • …
• 🇬https://leetcode.com/problems/robot-room-cleaner/?hd
• 🇬https://leetcode.com/problems/employee-free-time/?hd
• 🇬https://leetcode.com/problems/expression-add-operators/?hd
• 🇬Student Attendance Record II: Fewer than 2 A, no 3 or more consecutive L. [💡]
  • n = 2 => 8 (“PP”, “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”)
• 🇬https://leetcode.com/problems/meeting-rooms-iii/?hd
• 🇬https://leetcode.com/problems/amount-of-new-area-painted-each-day/?hd
• 🇬https://leetcode.com/problems/number-of-atoms/?hd
• 🇬https://leetcode.com/problems/number-of-good-paths/?hd
• 🇬https://leetcode.com/problems/guess-the-word/?hd
• 🇬https://leetcode.com/problems/shortest-distance-from-all-buildings/?hd
• 🇬https://leetcode.com/problems/maximum-and-sum-of-array/?hd
• 🇬https://leetcode.com/problems/sum-of-prefix-scores-of-strings/?hd
• 🇬https://leetcode.com/problems/basic-calculator/

• Shortest Path in Binary Matrix: A*.

• Find the Index of the First Occurrence in a String: [💡]

  • KMP pattern matching, O(m+n).

• Maximum Length of Repeated Subarray: Rabin–Karp algorithm / Rolling Hash.

• Longest Duplicate Substring / s: Rabin Karp + Binary Search.

• 🦠Close strings: 💡

  • set(w1) == set(w2) and Counter(Counter(w1).values()) == Counter(Counter(w2).values()

• String Compression: 2 pointers, slow and fast.

• Middle of the Linked List: 💡

  • 1->2->3->4->5 => 3
  • slow = fast = head, while fast and fast.next: …, return slow
  • O(n) time, O(1) space

• Linked List Cycle II: 💡

  • head = [3,2,0,-4], -4 -> 2 => 2
  • dist(intersect, cycle) == dist(head, cycle)
  • O(n) time, O(1) space

• Sudoku Solver: if board[3 * (i // 3) + k // 3][ 3 * (j // 3) + k % 3] == n:

Links

• Cracking the coding interview
• Neetcode
• Leetcode
• Project Euler
• HackerRank