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

for n in nums:
    # need to shrink?
    if cur_sum+n < n: ...
    # update result
    if cur_sum > max_sum: ...
for r in range(len(nums)):
    if r-l+1 == k:
        ...

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

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

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

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

Click to expand
  • 🇳Single Number☀️: 💡
    • nums = [2,2,1] => 1
    • result ^= n
    • O(n) time, O(1) space
  • 🅱️Number of 1 Bits☀️: 💡
    • n = 11 => 3 (1011)
    • either res += n & 1 and n >> 1 or just n = n & (n-1) and res += 1
    • O(logn) time, O(1) space
  • 🅱️Counting Bits☀️: 💡
    • n = 2 => [0,1,1]
    • if offset * 2 == i: offset *= i, dp[i] = dp[i-offset] + 1
    • O(n) time, O(n) space
  • 🅱️Reverse Bits☀️: 💡
    • 00000000000000000000000000000110 => 01100000000000000000000000000000
    • for i in range(32): bit = (n >> i) & 1, res |= bit << (31-i)
    • O(1) time, O(1) space (32 bit)
  • 🅱️Missing Number☀️: 💡
    • nums = [3,0,1] => 2
    • for i, n in enumerate(nums): res ^= n; res ^= i+1
    • O(n) time, O(1) space
  • 🅱️Sum of Two Integers⛅: 💡
    • a = 1, b = 2 => 3
    • return a if b == 0 else getSum(a^b, (a&b)<<1)
  • 🇳Reverse Integer⛅: 💡
    • x = 123 => 321
    • TODO

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/