Some notes about DSA

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

Reacto

  • Read the problem, ask clarifying questions, assumptions
  • Examples, edge cases
  • Approach, pseudocode
  • Code
  • Test, edge cases
  • Optimize, space and time complexity

Legend

  • 🅱️ Blind 75 / 🗿 Neetcode / 🏢 Google
  • ☀️ Easy / ⛅ Medium / ⛈️ Hard

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

    • Hashset seen / sort and check i and i+1

    • O(n) time, O(n) space
      def containsDuplicate(self, nums: List[int]) -> bool:
          """O(n) time, O(n) space"""
          seen = set()
      
          for n in nums:
              if n in seen:
                  return True
              seen.add(n)
          return False
      
      def containsDuplicate(self, nums: List[int]) -> bool:
          """O(nlogn) time, O(1) space"""
          nums.sort()
          for i in range(1, len(nums)):
              if nums[i] == nums[i - 1]:
                  return True
          return False
      
  • 🅱️Valid Anagram☀️: 💡

    • s = "anagram", t = "nagaram" => true

    • 2 Counters / 1 counter and decrease / sort

    • O(w) time, O(1) space
      def isAnagram(self, s: str, t: str) -> bool:
          if len(s) != len(t):
              return False
          count_s = Counter(s)
          count_t = Counter(t)
          return count_s == count_t
      
  • 🅱️🏢Two Sum☀️: 💡

    • nums = [2,7,11,15], target = 9 => [0,1]

    • Hashmap seen and store index, look for complement

    • O(n) time, O(n) space
      def twoSum(self, nums: List[int], target: int) -> List[int]:
          seen = {}
          for i, n in enumerate(nums):
              if target - n in seen:
                  return seen[target - n], i
              seen[n] = i
      
  • 🅱️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
      def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
          groups = defaultdict(list)
          for word in strs:
              groups[tuple(sorted(Counter(word).items()))].append(word)
          return list(groups.values())
      
  • 🅱️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
      def topKFrequent(self, nums: List[int], k: int) -> List[int]:
          groups_by_freq = [[] for _ in range(len(nums)+1)]
          for n, count in Counter(nums).items():
              groups_by_freq[count].append(n)
          result = []
          for i in range(len(nums), -1, -1):
              for n in groups_by_freq[i]:
                  result.append(n)
                  if len(result) >= k:
                      return result
          return result
      
  • 🅱️Product of Array Except Self⛅: 💡

    • nums = [1,2,3,4] => [24,12,8,6]

    • Prefix product, Suffix product.

    • O(n) time, O(1) space
      def productExceptSelf(self, nums):
          ans = [1]*len(nums)
          suf, pre = 1, 1
          for i in range(len(nums)):
              ans[i] *= pre
              ans[-1-i] *= suf
              pre *= nums[i]
              suf *= nums[-1-i]
          return ans
      
  • 🗿Valid Sudoku⛅: 💡

    • partially filled 9x9 grid

    • sets, squares[(r // 3, c // 3)].add(board[r][c])

    • O(1) time, O(1) space
      def isValidSudoku(self, board: List[List[str]]) -> bool:
      
          for row in board:
              numbers = [n for n in row if n != "."]
              if len(set(numbers)) != len(numbers):
                  return False
      
          for i in range(9):
              numbers = [row[i] for row in board if row[i] != "."]
              if len(set(numbers)) != len(numbers):
                  return False
      
          squares = defaultdict(set)
          for r in range(9):
              for c in range(9):
                  block = squares[(r // 3, c // 3)]
                  if board[r][c] != "." and board[r][c] in block:
                      return False
                  block.add(board[r][c])
          return True
      
  • 🅱️Encode and Decode Strings⛅: 💡

    • Create single string and split it back

    • Length + Separator

    • O(n) encode, O(n) decode
      def encode(self, strs):
          res = ""
          for s in strs:
              res += str(len(s)) + "#" + s
          return res
      
      def decode(self, s):
          res, i = [], 0
      
          while i < len(s):
              j = i
              while s[j] != "#":
                  j += 1
              length = int(s[i:j])
              res.append(s[j + 1 : j + 1 + length])
              i = j + 1 + length
          return res
      
  • 🅱️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
      def longestConsecutive(self, nums: List[int]) -> int:
          if not nums:
              return 0
          hashset = set(nums)
          result = 1
          for n in hashset:
              if (n-1) not in hashset:
                  length = 0
                  cur = n
                  while cur in hashset:
                      cur = cur+1
                      length += 1
                  result = max(result, length)
          return result
      

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
      def isPalindrome(self, s: str) -> bool:
          l = 0
          r = len(s)-1
          while l < r:
              while l < len(s) and not s[l].isalnum(): l += 1
              while r >= 0 and not s[r].isalnum(): r -= 1
              if l >= r:
                  return True
              if s[l].lower() != s[r].lower():
                  return False
              l += 1
              r -= 1
      
          return True
      
  • 🗿Two Sum II⛅: 💡

    • numbers = [2,7,11,15], target = 9 => [1,2]

    • 2 pointers.

    • O(n) time, O(1) space
      def twoSum(self, numbers: List[int], target: int) -> List[int]:
          l = 0
          r = len(numbers)-1
          while l < r:
              cursum = numbers[l] + numbers[r]
              if cursum == target:
                  return [l+1, r+1]
              if cursum < target:
                  l += 1
              else:
                  r -= 1
          return None
      
  • 🅱️3Sum⛅: 💡

    • nums = [-1,0,1,2,-1,-4] => [[-1,-1,2],[-1,0,1]]

    • sort, for each i, 2 pointers (l = i+1, r = len(nums)-1)

    • O(n^2) time, O(n) space (sorting)
      def threeSum(self, nums: List[int]) -> List[List[int]]:
          result = set()
          nums.sort()
          for i in range(len(nums)):
              l, r = i+1, len(nums)-1
              while l < r:
                  sum3 = nums[l] + nums[r] + nums[i]
                  if sum3 == 0:
                      result.add((nums[i], nums[l], nums[r]))
                      l += 1
                      r -= 1
                  elif sum3 < 0:
                      l += 1
                  else:
                      r -= 1
          return result
      
  • 🅱️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
      def maxArea(self, height: List[int]) -> int:
          result = 0
          l, r = 0, len(height)-1
          while l < r:
              result = max(result, min(height[l], height[r])*(r-l))
              if height[l] < height[r]:
                  l += 1
              else:
                  r -= 1
          return result
      
  • 🗿Trapping Rain Water⛈️: 💡

    • height = [0,1,0,2,1,0,1,3,2,1,2,1] => 6

    • using 2 pointers, update result before moving the pointer

    • O(n) time, O(n) space
      def trap(self, height: List[int]) -> int:
          leftmax, rightmax = 0, 0
          l, r = 0, len(height)-1
          result = 0
      
          while l <= r:
              if leftmax <= rightmax:
                  result += max(min(leftmax, rightmax)-height[l], 0)
                  leftmax = max(leftmax, height[l])
                  l += 1
              else:
                  result += max(min(leftmax, rightmax)-height[r], 0)
                  rightmax = max(rightmax, height[r])
                  r -= 1
          return result
      

Sliding Window

  • 🅱️🏢Best Time to Buy and Sell Stock☀️: 💡

    • prices = [7,1,5,3,6,4] => 5

    • Kadane’s algorithm / Two pointers (start from 0, 1)

    • O(n) time, O(1) space
      def maxProfit(self, prices: List[int]) -> int:
          result = 0
          cheapest = prices[0]
          for p in prices:
              result = max(result, p-cheapest)
              cheapest = min(cheapest, p)
          return result
      
  • 🅱️🏢Longest Substring Without Repeating Characters⛅: 💡

    • s = "abcabcbb" => 3 (“abc”)

    • Hashmap (seen, index), left = max(left, seen[c]+1)

    • O(n) time, O(1) space
      def lengthOfLongestSubstring(self, s: str) -> int:
          result = 0
          l = 0
          last_seen = {}
          for i, c in enumerate(s):
              if c in last_seen:
                  l = max(l, last_seen[c]+1)  # do not decrease!
              last_seen[c] = i
              result = max(result, i-l+1)
          return result
      
  • 🅱️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
      def characterReplacement(self, s: str, k: int) -> int:
          result = 0
          l = 0
          char_count = {}
          for r, c in enumerate(s):
              char_count[c] = char_count.get(c, 0) + 1
              if (r-l+1) > max(char_count.values())+k:
                  char_count[s[l]] -= 1
                  l += 1
              result = max(result, r-l+1)
          return result
      
  • 🗿Permutation in String⛅: 💡

    • s1 = "ab" s2 = "eidbaooo" => true

    • Counter, sliding window of size len(s1)

    • O(n) time, O(1) space
      def checkInclusion(self, s1: str, s2: str) -> bool:
          cntr, w = Counter(s1), len(s1)
          for i in range(len(s2)):
              if s2[i] in cntr:
                  cntr[s2[i]] -= 1
              if i >= w and s2[i-w] in cntr:  # shrink
                  cntr[s2[i-w]] += 1
              if all([cntr[i] == 0 for i in cntr]):
                  return True
          return False
      
  • 🅱️Minimum Window Substring⛈️: 💡

    • s = "ADOBECODEBANC", t = "ABC" => "BANC"

    • Counter, if all window counter >= counter, shrink, i = 0, for j in …

    • O(n) time, O(1) space
      def minWindow(self, s: str, t: str) -> str:
          need = collections.Counter(t)
          l = 0
          result = ""
          for r, c in enumerate(s):
              need[c] -= 1
              if all(v <= 0 for v in need.values()):
                  while l < r and need[s[l]] < 0:
                      need[s[l]] += 1
                      l += 1
                  if not result or r-l+1 < len(result):
                      result = s[l:r+1]
          return result
      
  • 🗿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
      def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
          result = []
      
          q = deque()
          l = 0
          for r in range(len(nums)):
              while q and nums[q[-1]] < nums[r]:
                  q.pop()
      
              q.append(r)
              if l > q[0]:
                  q.popleft()
      
              if r-k+1 >= 0:
                  result.append(nums[q[0]])
                  l += 1
      
          return result
      

Stack


  • 🅱️Valid Parentheses☀️: 💡

    • s = "()[]{}" => true

    • store last opened in stack, check stack empty at the end

    • O(n) time, O(n) space
      def isValid(self, s: str) -> bool:
          stack = []
          close_to_open = {"}": "{", ")": "(", "]": "["}
          for p in s:
              if p in close_to_open:
                  if not stack or close_to_open[p] != stack[-1]:
                      return False
                  stack.pop()
              else:
                  stack.append(p)
          return len(stack) == 0
      
  • 🗿Min Stack⛅: 💡

    • push(val), pop(), top(), getMin()

    • stack, append((min_so_far, val)), min_so_far = min(val, self.stack[-1][0])

    • O(1) time, O(n) space
      def __init__(self):
          self.stack = []
      
      def push(self, val: int) -> None:
          if not self.stack:
              self.stack.append((val, val))
          else:
              min_so_far = min(val, self.stack[-1][0])
              self.stack.append((min_so_far, val))
      
      def pop(self) -> None:
          return self.stack.pop()[1]
      
      
      def top(self) -> int:
          return self.stack[-1][1]
      
      
      def getMin(self) -> int:
          return self.stack[-1][0]
      
  • 🗿 🏢Reverse Polish Notation⛅: 💡

    • tokens = ["2","1","+","3","*"] => 9

    • b, a = stack.pop(), stack.pop()return stack[0]

    • O(n) time, O(n) space
      def evalRPN(self, tokens: List[str]) -> int:
          stack = []
          operators = {
              "+": lambda a,b: a+b,
              "-": lambda a,b: a-b,
              "*": lambda a,b: a*b,
              "/": lambda a,b: int(a/b),
          }
          for t in tokens:
              if t not in operators:
                  stack.append(int(t))
              else:
                  b, a = stack.pop(), stack.pop()
                  stack.append(operators[t](a, b))
          return stack[0]
      
  • 🗿Generate Parentheses⛅: 💡

    • n = 3 => ["((()))","(()())","(())()","()(())","()()()"]

    • stack, backtracking, dfs(opened, closed), if opened < n, if closed < opened

    • O(2^(2n)) time, O(n) space
      def generateParenthesis(self, n: int) -> List[str]:
          result = []
          path = []
      
          def dfs(opened, closed):
              if opened == closed == n:
                  result.append("".join(path))
                  return
              if opened < n:
                  path.append("(")
                  dfs(opened+1, closed)
                  path.pop()
      
              if closed < opened:
                  path.append(")")
                  dfs(opened, closed+1)
                  path.pop()
      
          dfs(0, 0)
          return result
      
  • 🗿Daily Temperatures⛅: 💡

    • T = [73,74,75,71,69,72,76,73] => [1,1,4,2,1,1,0,0]

    • init result = [0]*len, stack of pending, while tmp[i] > tmp[stack[-1]], pop and update

    • O(n) time, O(n) space
      def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
          result = [0]*len(temperatures)
          pending = []
          for i, t in enumerate(temperatures):
              while pending and temperatures[pending[-1]] < t:
                  prev = pending.pop()
                  result[prev] = i-prev
              pending.append(i)
          return result
      
  • 🗿Car fleet⛅: 💡

    • target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] => 3

    • Sort by position, start from end, calculate time to reach, ignore if faster

    • O(nlogn) time, O(n) space
      def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
          stack = []
          for p, s in sorted([(p,s) for p, s in zip(position, speed)], reverse=True):
              time = (target-p)/s
              if stack and time <= stack[-1]:
                  continue
              stack.append(time)
          return len(stack)
      
  • 🗿Largest Rectangle in Histogram⛈️: 💡

    • heights = [2,1,5,6,2,3] => 10

    • stack.append((start, h)), if decreasing, pop and update maxArea and current start

    • O(n) time, O(n) space
      def largestRectangleArea(self, heights: List[int]) -> int:
          maxArea = 0
          stack = []
      
          for i, h in enumerate(heights):
              start = i
              # found a decrease in height
              while stack and stack[-1][1] > h:
                  index, height = stack.pop()
                  maxArea = max(maxArea, height * (i - index))
                  start = index  # we can start from the leftmost index that is higher
              stack.append((start, h))
      
          for i, h in stack:
              maxArea = max(maxArea, h * (len(heights) - i))
          return maxArea
      

Remember it can be used on a range of values


  • 🗿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
      def search(self, nums: List[int], target: int) -> int:
          l, r = 0, len(nums)-1
          while l <= r:
              mid = (l+r)//2
              if nums[mid] == target:
                  return mid
              if nums[mid] < target:
                  l = mid + 1
              else:
                  r = mid - 1
          return -1
      
  • 🗿Search a 2D Matrix⛅: 💡

    • matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 => true

    • calculate row = mid // len(matrix[0]), col = mid % len(matrix[0])

    • O(logmn) time, O(1) space
      def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
          l, r = 0, len(matrix)*len(matrix[0])-1
          while l <= r:
              mid = (l+r)//2
              row = mid // len(matrix[0])
              col = mid % len(matrix[0])
              if matrix[row][col] == target:
                  return True
              if matrix[row][col] < target:
                  l = mid+1
              else:
                  r = mid-1
          return False
      
  • 🗿Koko Eating Bananas⛅: 💡

    • piles = [3,6,7,11], H = 8 => 4

    • binary search over speed, l, r = 1, max(piles)

    • O(nlogm) time, O(1) space
      def minEatingSpeed(self, piles: List[int], h: int) -> int:
          l, r = 1, max(piles)
          result = r
          while l <= r:
              mid = (l+r)//2
              hours = sum(math.ceil(p/mid) for p in piles)
              if hours <= h:
                  result = min(result, mid)
                  r = mid-1
              else:
                  l = mid+1
          return result
      
  • 🅱️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
      def search(self, nums: List[int], target: int) -> int:
          l, r = 0, len(nums)-1
      
          while l <= r:
              mid = (l+r) // 2
              if target == nums[mid]:
                  return mid
      
              if nums[l] <= nums[mid]:
                  if nums[l] <= target <= nums[mid]:
                      r = mid-1
                  else:
                      l = mid+1
      
              else:
                  if nums[mid] <= target <= nums[r]:
                      l = mid+1
                  else:
                      r = mid-1
          return -1
      
  • 🅱️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
      def findMin(self, nums: List[int]) -> int:
          start, end = 0, len(nums)-1
          curr_min = float("inf")
      
          while start < end:
              mid = (start+end) // 2
              curr_min = min(curr_min, nums[mid])
      
              if nums[mid] > nums[end]:
                  start = mid + 1
              else:
                  end = mid - 1
      
          return min(curr_min, nums[start])
      
  • 🗿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
      def __init__(self):
          self.store = {}
      
      def set(self, key: str, value: str, timestamp: int) -> None:
          if key not in self.store:
              self.store[key] = []
          self.store[key].append((value, timestamp))
      
      def get(self, key: str, timestamp: int) -> str:
          if key not in self.store:
              return ""
          res = ""
          values = self.store[key]
          l, r = 0, len(values)-1
          while l <= r:
              m = (l+r)//2
              if values[m][1] <= timestamp:
                  res = values[m][0]
                  l = m+1
              else:
                  r = m-1
          return res
      
  • 🗿 🏢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
      def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
          A, B = nums1, nums2
          total = len(nums1) + len(nums2)
          half = total // 2
      
          if len(B) < len(A):
              A, B = B, A
      
          l, r = 0, len(A) - 1
          while True:
              i = (l + r) // 2  # A
              j = half - i - 2  # B
      
              Aleft = A[i] if i >= 0 else float("-inf")
              Aright = A[i + 1] if (i + 1) < len(A) else float("inf")
              Bleft = B[j] if j >= 0 else float("-inf")
              Bright = B[j + 1] if (j + 1) < len(B) else float("inf")
      
              # partition is correct
              if Aleft <= Bright and Bleft <= Aright:
                  # odd
                  if total % 2:
                      return min(Aright, Bright)
                  # even
                  return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
              elif Aleft > Bright:
                  r = i - 1
              else:
                  l = i + 1
      

Linked List


  • 🅱️Reverse Linked List☀️: 💡

    • head = [1,2] => [2,1]

    • store previous, save cur.next in temp

    • O(n) time, O(1) space
      def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
          prev = None
          cur = head
      
          while cur:
              next_cur = cur.next
              cur.next = prev
              prev = cur
              cur = next_cur
          return prev
      
  • 🅱️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
      def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
          p1 = list1
          p2 = list2
          dummy = ListNode()
          cur = dummy
      
          while p1 and p2:
              if p1.val > p2.val:
                  p1, p2 = p2, p1
              cur.next = p1
              cur = cur.next
              p1 = p1.next
      
          if p1: cur.next = p1
          if p2: cur.next = p2
      
          return dummy.next
      
  • 🅱️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, for i in range(0, len(lists), 2)

    • O(nlogk) time, O(1) space
      def mergeKLists(self, lists: List[ListNode]) -> ListNode:
          if not lists or len(lists) == 0:
              return None
      
          while len(lists) > 1:
              mergedLists = []
              for i in range(0, len(lists), 2):
                  l1 = lists[i]
                  l2 = lists[i + 1] if (i + 1) < len(lists) else None
                  mergedLists.append(self.mergeList(l1, l2))
              lists = mergedLists
          return lists[0]
      
  • 🅱️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
      def reorderList(self, head: Optional[ListNode]) -> None:
          slow = head
          fast = head.next
          while fast and fast.next:
              slow = slow.next
              fast = fast.next.next
      
          p1 = head
          p2 = self.reverse(slow)
          # merge
          while p1 and p2:
              tmp1 = p1.next
              tmp2 = p2.next
              p1.next = p2
              p2.next = tmp1
              p1 = tmp1
              p2 = tmp2
          return head
      
      def reverse(self, node):
          ...
      
  • 🅱️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
      def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
          fast = slow = head
          for _ in range(n):
              fast = fast.next
          if not fast:
              return head.next
          while fast.next:
              fast = fast.next
              slow = slow.next
          slow.next = slow.next.next
          return head
      
  • 🗿Copy List with Random Pointer⛅: 💡

    • head = [[3,null],[3,0],[3,null]] => [[3,null],[3,0],[3,null]]

    • old_to_new = {None: None}, two passes, copy and then update next and random

    • O(n) time, O(n) space
      def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
          old_to_new = {None: None}
          cur = head
          while cur:
              copy = Node(cur.val)
              old_to_new[cur] = copy
              cur = cur.next
      
          cur = head
          while cur:
              copy = old_to_new[cur]
              copy.next = old_to_new[cur.next]
              copy.random = old_to_new[cur.random]
              cur = cur.next
          return old_to_new[head]
      
  • 🗿 🏢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
      def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
          head = ListNode()
          cur = head
          carry = 0
          while l1 or l2 or carry:
              cur.next = ListNode()
              cur = cur.next
              v1 = l1.val if l1 else 0
              v2 = l2.val if l2 else 0
              cur.val = v1 + v2 + carry
              if cur.val >= 10:
                  cur.val = cur.val % 10
                  carry = 1
              else:
                  carry = 0
              if l1: l1 = l1.next
              if l2: l2 = l2.next
          return head.next
      
  • 🅱️Linked List Cycle☀️: 💡

    • head = [3,2,0,-4], -4 -> 2 => true

    • Floyd’s Tortoise and hare / hashset of seen

    • O(n) time, O(1) space
      def hasCycle(self, head: Optional[ListNode]) -> bool:
          slow = fast = head
          while fast and fast.next:
              slow = slow.next
              fast = fast.next.next
              if slow == fast: return True
          return False
      
      def hasCycle(self, head: Optional[ListNode]) -> bool:
          seen = set()
          while head:
              if id(head) in seen: return True
              seen.add(id(head))
              head = head.next
          return False
      
  • 🗿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
      def findDuplicate(self, nums: List[int]) -> int:
          slow, fast = 0, 0
          while True :
              slow = nums[slow]
              fast = nums[nums[fast]]
              if slow == fast:
                  break
      
          slow2 = 0
          while True:
              slow = nums[slow]
              slow2 = nums[slow2]
              if slow == slow2:
                  return slow
      
  • 🗿LRU Cache⛅: 💡

    • LRUCache(int capacity), get(int key), put(int key, int value)

    • double linked list (easy remove/insertion), dict key -> node, dummy head and tail

    • O(1) time, O(capacity) space
      def __init__(self, capacity: int):
          self.cap = capacity
          self.cache = {}
      
          self.left = Node(0, 0)
          self.right = Node(0, 0)
          self.left.next = self.right
          self.right.prev = self.left
      
      def get(self, key: int) -> int:
          if key in self.cache:
              self.remove(self.cache[key])
              self.insert(self.cache[key])
              return self.cache[key].val
          return -1
      
      def put(self, key: int, value: int) -> None:
          if key in self.cache:
              self.remove(self.cache[key])
          self.cache[key] = Node(key, value)
          self.insert(self.cache[key])
      
          if len(self.cache) > self.cap:
              lru = self.left.next
              self.remove(lru)
              del self.cache[lru.key]
      
      def remove(self, node):
          prev, nxt = node.prev, node.next
          prev.next, nxt.prev = nxt, prev
      
      def insert(self, node):
          prev, nxt = self.right.prev, self.right
          prev.next = node
          self.right.prev = node
          node.next = nxt
          node.prev = prev
      
  • 🗿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
      def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
          node = head
          count = 0
          while node and count < k:
              node = node.next
              count += 1
          if count < k:
              return head
          new_head, prev = self.reverse(head, k)
          head.next = self.reverseKGroup(new_head, k)
          return prev
      
      def reverse(self, head, count):
          prev = None
          curr = head
          while count > 0:
              tmp = curr.next
              curr.next = prev
              prev = curr
              curr = tmp
              count -= 1
          return curr, prev
      

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
      def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
          stack = [root]
          while stack:
              node = stack.pop()
              if node is None: continue
              node.left, node.right = node.right, node.left
              stack.append(node.left)
              stack.append(node.right)
          return root
      
      def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
          if not root:
              return None
          root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
          return root
      
  • 🅱️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
      def maxDepth(self, root: Optional[TreeNode]) -> int:
          if not root:
              return 0
          return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
      
  • 🗿Diameter of Binary Tree☀️: 💡

    • root = [1,2,3,4,5] => 3

    • def dfs(node) that returns depth, update global diameter

    • O(n) time, O(height) space
      def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
          self.diameter = 0
          self.dfs(root)
          return self.diameter
      
      def dfs(self, node):
          if not node:
              return 0
          left = self.dfs(node.left)
          right = self.dfs(node.right)
          self.diameter = max(self.diameter, left+right)
          return 1 + max(left, right)
      
  • 🗿Balanced Binary Tree☀️: 💡

    • root = [3,9,20,null,null,15,7] => true

    • def dfs(node) that returns depth, update global balanced

    • O(n) time, O(height) space
      def isBalanced(self, root):
          self.bal = True
          self.dfs(root)
          return self.bal
      
      def dfs(self, node):
           if not node: return 0
           lft, rgh = self.dfs(node.left), self.dfs(node.right)
           if abs(lft - rgh) > 1: self.bal = False
           return max(lft, rgh) + 1
      
  • 🅱️Same Tree☀️: 💡

    • p = [1,2,3], q = [1,2,3] => true

    • check None, check val and recursive call

    • O(n) time, O(height) space
      def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
          if p is None and q is None:
              return True
          if p is None or q is None:
              return False
          return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
      
  • 🅱️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(n*m) time, O(n+m) space
      def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
          if not root:
              return False
          if self.is_same_tree(root, subRoot):
              return True
          return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
      
  • 🅱️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
      def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
          level = [root]
          result = []
          while level:
              new_level = []
              level = [l for l in level if l]
              if level:
                  result.append([n.val for n in level])
              for n in level:
                  new_level.append(n.left)
                  new_level.append(n.right)
              level = new_level
          return result
      
  • 🗿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
      def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
          if not root:
              return []
      
          result = []
          level = [root]
          while level:
              result.append(level[-1].val)
              new_level = []
              for n in level:
                  if n.left:
                      new_level.append(n.left)
                  if n.right:
                      new_level.append(n.right)
              level = new_level
          return result
      
  • 🗿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
      def goodNodes(self, root: TreeNode) -> int:
          if not root:
              return 0
      
          result = 0
          def dfs(node, max_so_far):
              nonlocal result
              if not node:
                  return
      
              max_so_far = max(max_so_far, node.val)
              if node.val >= max_so_far:
                  result += 1
      
              dfs(node.left, max_so_far)
              dfs(node.right, max_so_far)
      
          dfs(root, root.val)
          return result
      
  • 🅱️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]

    • recursive, pop(0) from preorder, find index in inorder, split inorder

    • O(n^2) time, O(n) space
      def buildTree(self, preorder, inorder):
          if not preorder or not inorder:
              return
          ind = inorder.index(preorder.pop(0))  # optimize with deque
          root = TreeNode(inorder[ind])
          root.left = self.buildTree(preorder, inorder[:ind])
          root.right = self.buildTree(preorder, inorder[ind+1:])
          return root
      
  • 🅱️Binary Tree Maximum Path Sum⛈️: 💡

    • root = [1,2,3] => 6

    • dfs, allow split or not, nonlocal max

    • O(n) time, O(height) space
      def maxPathSum(self, root: Optional[TreeNode]) -> int:
          max_path = float("-inf")
          def get_max_gain(node):
              nonlocal max_path
              if node is None:
                  return 0
      
              gain_on_left = max(get_max_gain(node.left), 0)
              gain_on_right = max(get_max_gain(node.right), 0)
              current_max_path = node.val + gain_on_left + gain_on_right
              max_path = max(max_path, current_max_path)
      
              return node.val + max(gain_on_left, gain_on_right)
      
          get_max_gain(root)
          return max_path
      
  • 🅱️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
      def serialize(self, root):
          values = []
          def preorder(node):
              if node:
                  values.append(str(node.val))
                  preorder(node.left)
                  preorder(node.right)
              else:
                  values.append('#')
          preorder(root)
          return ' '.join(values)
      
      def deserialize(self, data):
          values = list(reversed(data.split()))
          def preorder():
              value = values.pop()
              if value == '#':
                  return None
              node = TreeNode(int(value))
              node.left = preorder()
              node.right = preorder()
              return node
          return preorder()
      

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
      def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
          cur = root
          while cur:
              if p.val < cur.val and q.val < cur.val:
                  cur = cur.left
              elif p.val > cur.val and q.val > cur.val:
                  cur = cur.right
              else:
                  return cur
      
  • 🅱️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
      def isValidBST(self, root: Optional[TreeNode]) -> bool:
          return self.validate(root)
      
      def validate(self, node, min_val=None, max_val=None):
          if not node:
              return True
          if min_val is not None and node.val <= min_val:
              return False
          if max_val is not None and node.val >= max_val:
              return False
          return self.validate(node.left, min_val, node.val) and self.validate(node.right, node.val, max_val)
      
  • 🅱️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
       def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
          count = []
          self.helper(root, count)
          return count[k-1]
      
      def helper(self, node, count):
          if not node:
              return
      
          self.helper(node.left, count)
          count.append(node.val)
          self.helper(node.right, count)
      

Tries


  • 🅱️Implement Trie (Prefix Tree)⛅: 💡

    • insert(word), search(word), startsWith(prefix)

    • TrieNode has children dict and end bool

    • O(n) time, O(n) space
      class TrieNode:
          def __init__(self):
              self.children = {}
              self.end = False
      
      
      class Trie:
          def __init__(self):
              self.root = TrieNode()
      
          def insert(self, word: str) -> None:
              curr = self.root
              for c in word:
                  if c not in curr.children:
                      curr.children[c] = TrieNode()
                  curr = curr.children[c]
              curr.end = True
      
          def search(self, word: str) -> bool:
              curr = self.root
              for c in word:
                  if c not in curr.children:
                      return False
                  curr = curr.children[c]
              return curr.end
      
          def startsWith(self, prefix: str) -> bool:
              curr = self.root
              for c in prefix:
                  if c not in curr.children:
                      return False
                  curr = curr.children[c]
              return True
      
  • 🅱️Design Add And Search Words Data Structure⛅: 💡

    • addWord(word), search(word)

    • trie, recursive dfs(idx, node) for “.”

    • O(c) time, O(c) space
      
      class TrieNode:
          def __init__(self):
              self.children = {}  # a : TrieNode
              self.word = False
      
      
      class WordDictionary:
          def __init__(self):
              self.root = TrieNode()
      
          def addWord(self, word: str) -> None:
              cur = self.root
              for c in word:
                  if c not in cur.children:
                      cur.children[c] = TrieNode()
                  cur = cur.children[c]
              cur.word = True
      
          def search(self, word: str) -> bool:
              def dfs(j, root):
                  cur = root
      
                  for i in range(j, len(word)):
                      c = word[i]
                      if c == ".":
                          for child in cur.children.values():
                              if dfs(i + 1, child):
                                  return True
                          return False
                      else:
                          if c not in cur.children:
                              return False
                          cur = cur.children[c]
                  return cur.word
      
              return dfs(0, self.root)
      
  • 🅱️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
      class TrieNode:
          def __init__(self):
              self.children = {}
              self.isWord = False
              self.refs = 0
      
          def addWord(self, word):
              cur = self
              cur.refs += 1
              for c in word:
                  if c not in cur.children:
                      cur.children[c] = TrieNode()
                  cur = cur.children[c]
                  cur.refs += 1
              cur.isWord = True
      
          def removeWord(self, word):
              cur = self
              cur.refs -= 1
              for c in word:
                  if c in cur.children:
                      cur = cur.children[c]
                      cur.refs -= 1
      
      
      class Solution:
          def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
              root = TrieNode()
              for w in words:
                  root.addWord(w)
      
              ROWS, COLS = len(board), len(board[0])
              res, visit = set(), set()
      
              def dfs(r, c, node, word):
                  if (
                      r not in range(ROWS) 
                      or c not in range(COLS)
                      or board[r][c] not in node.children
                      or node.children[board[r][c]].refs < 1
                      or (r, c) in visit
                  ):
                      return
      
                  visit.add((r, c))
                  node = node.children[board[r][c]]
                  word += board[r][c]
                  if node.isWord:
                      node.isWord = False
                      res.add(word)
                      root.removeWord(word)
      
                  dfs(r + 1, c, node, word)
                  dfs(r - 1, c, node, word)
                  dfs(r, c + 1, node, word)
                  dfs(r, c - 1, node, word)
                  visit.remove((r, c))
      
              for r in range(ROWS):
                  for c in range(COLS):
                      dfs(r, c, root, "")
      
              return list(res)
      

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
      def __init__(self, k: int, nums: List[int]):
          heapq.heapify(nums) # O(n)
          self.heap = nums
          self.k = k
      
      def add(self, val: int) -> int:
          heapq.heappush(self.heap, val)
          while len(self.heap) > self.k:
              heapq.heappop(self.heap) # O(logk)
          return self.heap[0]
      
  • 🗿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
      def lastStoneWeight(self, stones: List[int]) -> int:
          result = [-s for s in stones]
          heapq.heapify(result) # n
          while len(result) > 1: # n times
              y = heapq.heappop(result)  # logn
              x = heapq.heappop(result)
              if x != y:
                  heapq.heappush(result, y-x) # logn
          # nlogn
          return -result[0] if result else 0
      
  • 🗿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
      def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
          heap = []
          for (x, y) in points:
              dist = -(x*x + y*y)
              if len(heap) == K:
                  heapq.heappushpop(heap, (dist, x, y))
              else:
                  heapq.heappush(heap, (dist, x, y))
          return [(x,y) for (dist,x, y) in heap]
      
  • 🗿Kth Largest Element in an Array⛅: 💡

    • nums = [3,2,1,5,6,4], k = 2 => 5

    • quickselect,

    • O(n) avg time, O(n) space
      def findKthLargest(self, nums, k):
          if not nums: return
          pivot = random.choice(nums)
          left =  [x for x in nums if x > pivot]
          mid  =  [x for x in nums if x == pivot]
          right = [x for x in nums if x < pivot]
      
          L, M = len(left), len(mid)
      
          if k <= L:
              return self.findKthLargest(left, k)
          elif k > L + M:
              return self.findKthLargest(right, k - L - M)
          else:
              return mid[0]
      
  • 🗿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(n) space
      def leastInterval(self, tasks: List[str], n: int) -> int:
          count = Counter(tasks)
          maxHeap = [-cnt for cnt in count.values()]
          heapq.heapify(maxHeap)  # O(n)
      
          time = 0
          q = deque()  # pairs of [-cnt, idleTime]
          while maxHeap or q:
              time += 1
      
              if not maxHeap:
                  time = q[0][1]
              else:
                  cnt = 1 + heapq.heappop(maxHeap)
                  if cnt:
                      q.append([cnt, time + n])
              if q and q[0][1] == time:
                  heapq.heappush(maxHeap, q.popleft()[0])
          return time
      
  • 🗿Design Twitter⛅: 💡

    • postTweet, getNewsFeed, follow, unfollow

    • heap, followerset per user, tweetmap per user

    • O(nlogn) time, O(n) space
      def __init__(self):
          self.count = 0
          self.tweetMap = defaultdict(list)  # userId -> list of [count, tweetIds]
          self.followMap = defaultdict(set)  # userId -> set of followeeId
      
      def postTweet(self, userId: int, tweetId: int) -> None:
          self.tweetMap[userId].append([self.count, tweetId])
          self.count -= 1
      
      def getNewsFeed(self, userId: int) -> List[int]:
          res = []
          minHeap = []
      
          self.followMap[userId].add(userId)
          for followeeId in self.followMap[userId]:
              if followeeId in self.tweetMap:
                  index = len(self.tweetMap[followeeId]) - 1
                  count, tweetId = self.tweetMap[followeeId][index]
                  heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])
      
          while minHeap and len(res) < 10:
              count, tweetId, followeeId, index = heapq.heappop(minHeap)
              res.append(tweetId)
              if index >= 0:
                  count, tweetId = self.tweetMap[followeeId][index]
                  heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])
          return res
      
      def follow(self, followerId: int, followeeId: int) -> None:
          self.followMap[followerId].add(followeeId)
      
      def unfollow(self, followerId: int, followeeId: int) -> None:
          if followeeId in self.followMap[followerId]:
              self.followMap[followerId].remove(followeeId)
      
  • 🅱️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
      class MedianFinder:
          def __init__(self):
              """
              initialize your data structure here.
              """
              # two heaps, large, small, minheap, maxheap
              # heaps should be equal size
              self.small, self.large = [], []  # maxHeap, minHeap (python default)
      
          def addNum(self, num: int) -> None:
              if self.large and num > self.large[0]:
                  heapq.heappush(self.large, num)
              else:
                  heapq.heappush(self.small, -1 * num)
      
              if len(self.small) > len(self.large) + 1:
                  val = -1 * heapq.heappop(self.small)
                  heapq.heappush(self.large, val)
              if len(self.large) > len(self.small) + 1:
                  val = heapq.heappop(self.large)
                  heapq.heappush(self.small, -1 * val)
      
          def findMedian(self) -> float:
              if len(self.small) > len(self.large):
                  return -1 * self.small[0]
              elif len(self.large) > len(self.small):
                  return self.large[0]
              return (-1 * self.small[0] + self.large[0]) / 2
      

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
      def subsets(self, nums: List[int]) -> List[List[int]]:
          result = []
      
          path = []
          def dfs(i):
              if i == len(nums):
                  result.append(path[:])
                  return
      
              path.append(nums[i])
              dfs(i+1)
              path.pop()
              dfs(i+1)
      
          dfs(0)
          return result
      
  • 🅱️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
      def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
          result = []
      
          path = []
          def dfs(i, t):
              if t == 0:
                  result.append(path[:])
                  return
              if i >= len(candidates) or t < 0:
                  return
      
              path.append(candidates[i])
              dfs(i, t-candidates[i])
              path.pop()
              dfs(i+1, t)
      
          dfs(0, target)
          return result
      
  • 🗿Permutations⛅: 💡

    • nums = [1,2,3] => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    • stack of

    • O(n*n!) time, O(n!) space
      def permute(self, nums: List[int]) -> List[List[int]]:
          stack = [(nums, [])]
          res = []
          while stack:
              nums, path = stack.pop()
              if not nums:
                  res.append(path)
                  continue
              for i in range(len(nums)):
                  stack.append((nums[:i] + nums[i+1:], path+[nums[i]]))
          return res
      
  • 🗿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
      def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
          res = []
          nums.sort()
      
          def backtrack(i, subset):
              if i == len(nums):
                  res.append(subset[::])
                  return
      
              # All subsets that include nums[i]
              subset.append(nums[i])
              backtrack(i + 1, subset)
              subset.pop()
              # All subsets that don't include nums[i]
              while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                  i += 1
              backtrack(i + 1, subset)
      
          backtrack(0, [])
          return res
      
  • 🗿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
      def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
          candidates.sort()
      
          res = []
      
          def backtrack(cur, pos, target):
              if target == 0:
                  res.append(cur.copy())
                  return
              if target <= 0:
                  return
      
              prev = -1
              for i in range(pos, len(candidates)):
                  if candidates[i] == prev:
                      continue
                  cur.append(candidates[i])
                  backtrack(cur, i + 1, target - candidates[i])
                  cur.pop()
                  prev = candidates[i]
      
          backtrack([], 0, target)
          return res
      
  • 🅱️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
      def exist(self, board: List[List[str]], word: str) -> bool:
          ROWS, COLS = len(board), len(board[0])
          path = set()
      
          def dfs(r, c, i):
              if i == len(word):
                  return True
              if (
                  min(r, c) < 0
                  or r >= ROWS
                  or c >= COLS
                  or word[i] != board[r][c]
                  or (r, c) in path
              ):
                  return False
              path.add((r, c))
              res = (
                  dfs(r + 1, c, i + 1)
                  or dfs(r - 1, c, i + 1)
                  or dfs(r, c + 1, i + 1)
                  or dfs(r, c - 1, i + 1)
              )
              path.remove((r, c))
              return res
      
          # To prevent TLE,reverse the word if frequency of the first letter is more than the last letter's
          count = defaultdict(int, sum(map(Counter, board), Counter()))
          if count[word[0]] > count[word[-1]]:
              word = word[::-1]
      
          for r in range(ROWS):
              for c in range(COLS):
                  if dfs(r, c, 0):
                      return True
          return False
      
      # O(n * m * 4^n)
      
  • 🗿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
       def partition(self, s: str) -> List[List[str]]:
          res, part = [], []
      
          def dfs(i):
              if i >= len(s):
                  res.append(part.copy())
                  return
              for j in range(i, len(s)):
                  if self.isPali(s, i, j):
                      part.append(s[i : j + 1])
                      dfs(j + 1)
                      part.pop()
      
          dfs(0)
          return res
      
      def isPali(self, s, l, r):
          while l < r:
              if s[l] != s[r]:
                  return False
              l, r = l + 1, r - 1
          return True
      
  • 🗿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
      def letterCombinations(self, digits: str) -> List[str]:
          res = []
          digitToChar = {
              "2": "abc",
              "3": "def",
              "4": "ghi",
              "5": "jkl",
              "6": "mno",
              "7": "qprs",
              "8": "tuv",
              "9": "wxyz",
          }
      
          def backtrack(i, curStr):
              if len(curStr) == len(digits):
                  res.append(curStr)
                  return
              for c in digitToChar[digits[i]]:
                  backtrack(i + 1, curStr + c)
      
          if digits:
              backtrack(0, "")
      
          return res
      
  • 🗿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
      def solveNQueens(self, n: int) -> List[List[str]]:
          col = set()
          posDiag = set()  # (r + c)
          negDiag = set()  # (r - c)
      
          res = []
          board = [["."] * n for i in range(n)]
      
          def backtrack(r):
              if r == n:
                  copy = ["".join(row) for row in board]
                  res.append(copy)
                  return
      
              for c in range(n):
                  if c in col or (r + c) in posDiag or (r - c) in negDiag:
                      continue
      
                  col.add(c)
                  posDiag.add(r + c)
                  negDiag.add(r - c)
                  board[r][c] = "Q"
      
                  backtrack(r + 1)
      
                  col.remove(c)
                  posDiag.remove(r + c)
                  negDiag.remove(r - c)
                  board[r][c] = "."
      
          backtrack(0)
          return res
      

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

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
      def numIslands(self, grid: List[List[str]]) -> int:
          result = 0
      
          visited = set()
          def dfs(i, j):
              if (i, j) in visited: return
              if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]): return
              if grid[i][j] != "1": return
              visited.add((i, j))
              for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                  dfs(ii, jj)
      
          for i in range(len(grid)):
              for j in range(len(grid[0])):
                  if grid[i][j] == "1" and (i, j) not in visited:
                      result += 1
                      dfs(i, j)
      
          return result
      
  • 🅱️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
      def cloneGraph(self, node: "Node") -> "Node":
          oldToNew = {}
      
          def dfs(node):
              if node in oldToNew:
                  return oldToNew[node]
      
              copy = Node(node.val)
              oldToNew[node] = copy
              for nei in node.neighbors:
                  copy.neighbors.append(dfs(nei))
              return copy
      
          return dfs(node) if node else None
      
  • 🗿 🏢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
      def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
          ROWS, COLS = len(grid), len(grid[0])
          visit = set()
      
          def dfs(r, c):
              if (
                  r < 0
                  or r == ROWS
                  or c < 0
                  or c == COLS
                  or grid[r][c] == 0
                  or (r, c) in visit
              ):
                  return 0
              visit.add((r, c))
              return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
      
          area = 0
          for r in range(ROWS):
              for c in range(COLS):
                  area = max(area, dfs(r, c))
          return area
      
  • 🅱️🏢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
      def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
          pacific = set()
          atlantic = set()
      
          for i in range(len(heights)):
              for j in range(len(heights[0])):
                  if i == 0 or j == 0:
                      pacific.add((i, j))
                  if i == len(heights)-1 or j == len(heights[0])-1:
                      atlantic.add((i, j))
      
          # pacific
          stack = list(pacific)
          while stack:
              i, j = stack.pop()
              for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                  if (ii, jj) in pacific:
                      continue
                  if self.is_valid(ii, jj, heights) and heights[ii][jj] >= heights[i][j]:
                      stack.append((ii, jj))
                      pacific.add((ii, jj))
      
          stack = list(atlantic)
          while stack:
              i, j = stack.pop()
              for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                  if (ii, jj) in atlantic:
                      continue
                  if self.is_valid(ii, jj, heights) and heights[ii][jj] >= heights[i][j]:
                      stack.append((ii, jj))
                      atlantic.add((ii, jj))
      
          return list(pacific.intersection(atlantic))
      
      def is_valid(self, i, j, heights):
          return 0 <= i <= (len(heights)-1) and 0 <= j <= (len(heights[0])-1)
      
  • 🗿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
      def solve(self, board: List[List[str]]) -> None:
          ROWS, COLS = len(board), len(board[0])
      
          def capture(r, c):
              if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":
                  return
              board[r][c] = "T"
              capture(r + 1, c)
              capture(r - 1, c)
              capture(r, c + 1)
              capture(r, c - 1)
      
          # 1. (DFS) Capture unsurrounded regions (O -> T)
          for r in range(ROWS):
              for c in range(COLS):
                  if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
                      capture(r, c)
      
          # 2. Capture surrounded regions (O -> X)
          for r in range(ROWS):
              for c in range(COLS):
                  if board[r][c] == "O":
                      board[r][c] = "X"
      
          # 3. Uncapture unsurrounded regions (T -> O)
          for r in range(ROWS):
              for c in range(COLS):
                  if board[r][c] == "T":
                      board[r][c] = "O"
      
  • 🗿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
      def orangesRotting(self, grid: List[List[int]]) -> int:
          q = collections.deque()
          fresh = 0
          time = 0
      
          for r in range(len(grid)):
              for c in range(len(grid[0])):
                  if grid[r][c] == 1:
                      fresh += 1
                  if grid[r][c] == 2:
                      q.append((r, c))
      
          directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
          while fresh > 0 and q:
              length = len(q)
              for i in range(length):
                  r, c = q.popleft()
      
                  for dr, dc in directions:
                      row, col = r + dr, c + dc
                      # if in bounds and nonrotten, make rotten
                      # and add to q
                      if (
                          row in range(len(grid))
                          and col in range(len(grid[0]))
                          and grid[row][col] == 1
                      ):
                          grid[row][col] = 2
                          q.append((row, col))
                          fresh -= 1
              time += 1
          return time if fresh == 0 else -1
      
  • 🗿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
      def walls_and_gates(self, rooms: List[List[int]]):
          ROWS, COLS = len(rooms), len(rooms[0])
          visit = set()
          q = deque()
      
          def addRooms(r, c):
              if (
                  min(r, c) < 0
                  or r == ROWS
                  or c == COLS
                  or (r, c) in visit
                  or rooms[r][c] == -1
              ):
                  return
              visit.add((r, c))
              q.append([r, c])
      
          for r in range(ROWS):
              for c in range(COLS):
                  if rooms[r][c] == 0:
                      q.append([r, c])
                      visit.add((r, c))
      
          dist = 0
          while q:
              for i in range(len(q)):
                  r, c = q.popleft()
                  rooms[r][c] = dist
                  addRooms(r + 1, c)
                  addRooms(r - 1, c)
                  addRooms(r, c + 1)
                  addRooms(r, c - 1)
              dist += 1
      
  • 🅱️Course Schedule⛅: 💡

    • DFS cycle detection (visited set, cycle set).

    • O(v+e) time, O(v) space
      def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
          # dfs
          preMap = {i: [] for i in range(numCourses)}
      
          # map each course to : prereq list
          for crs, pre in prerequisites:
              preMap[crs].append(pre)
      
          visiting = set()
      
          def dfs(crs):
              if crs in visiting:
                  return False
              if preMap[crs] == []:
                  return True
      
              visiting.add(crs)
              for pre in preMap[crs]:
                  if not dfs(pre):
                      return False
              visiting.remove(crs)
              preMap[crs] = []
              return True
      
          for c in range(numCourses):
              if not dfs(c):
                  return False
          return True
      
  • 🗿 🏢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
      def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
          prereq = {c: [] for c in range(numCourses)}
          for crs, pre in prerequisites:
              prereq[crs].append(pre)
      
          output = []
          visit, cycle = set(), set()
      
          def dfs(crs):
              if crs in cycle:
                  return False
              if crs in visit:
                  return True
      
              cycle.add(crs)
              for pre in prereq[crs]:
                  if dfs(pre) == False:
                      return False
              cycle.remove(crs)
              visit.add(crs)
              output.append(crs)
              return True
      
          for c in range(numCourses):
              if dfs(c) == False:
                  return []
          return output
      
  • 🗿Redundant Connection⛅: 💡

    • edges = [[1,2], [1,3], [2,3]] => [2,3]

    • union find, return edge if cycle (parent(x) == parent(y))

    • O(n) time, O(n) space / actually O(inv_ackerman(n))
      def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
          parents = {}
      
          def find_parent(n):
              y = parents.get(n, n)
              if y != n:
                  y = find_parent(y)
                  parents[n] = y
              return y
      
          def union(n1, n2):
              p1 = find_parent(n1)
              p2 = find_parent(n2)
              if p1 == p2:  # cycle
                  return False
              parents[p1] = p2
              return True
      
          for n1, n2 in edges:
              if not union(n1, n2):
                  return [n1, n2]
      
  • 🅱️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
      class UnionFind:
          def __init__(self):
              self.f = {}
      
          def findParent(self, x):
              y = self.f.get(x, x)
              if x != y:
                  y = self.f[x] = self.findParent(y)
              return y
      
          def union(self, x, y):
              self.f[self.findParent(x)] = self.findParent(y)
      
      
      class Solution:
          def countComponents(self, n: int, edges: List[List[int]]) -> int:
              dsu = UnionFind()
              for a, b in edges:
                  dsu.union(a, b)
              return len(set(dsu.findParent(x) for x in range(n)))
      
  • 🅱️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
      def validTree(self, n, edges):
          if not n:
              return True
          adj = {i: [] for i in range(n)}
          for n1, n2 in edges:
              adj[n1].append(n2)
              adj[n2].append(n1)
      
          visit = set()
      
          def dfs(i, prev):
              if i in visit:
                  return False
      
              visit.add(i)
              for j in adj[i]:
                  if j == prev:
                      continue
                  if not dfs(j, i):
                      return False
              return True
      
          return dfs(0, -1) and n == len(visit)
      
  • 🗿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^2*n) time, O(m^2*n) space
      def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
          if endWord not in wordList:
              return 0
      
          nei = collections.defaultdict(list)
          wordList.append(beginWord)
          for word in wordList:
              for j in range(len(word)):
                  pattern = word[:j] + "*" + word[j + 1 :]
                  nei[pattern].append(word)
      
          visit = set([beginWord])
          q = deque([beginWord])
          res = 1
          while q:
              for i in range(len(q)):
                  word = q.popleft()
                  if word == endWord:
                      return res
                  for j in range(len(word)):
                      pattern = word[:j] + "*" + word[j + 1 :]
                      for neiWord in nei[pattern]:
                          if neiWord not in visit:
                              visit.add(neiWord)
                              q.append(neiWord)
              res += 1
          return 0
      

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
      def findItinerary(self, tickets: List[List[str]]) -> List[str]:
          adj = {u: collections.deque() for u, v in tickets}
          res = ["JFK"]
      
          tickets.sort()
          for u, v in tickets:
              adj[u].append(v)
      
          def dfs(cur):
              if len(res) == len(tickets) + 1:
                  return True
              if cur not in adj:
                  return False
      
              temp = list(adj[cur])
              for v in temp:
                  adj[cur].popleft()
                  res.append(v)
                  if dfs(v):
                      return res
                  res.pop()
                  adj[cur].append(v)
              return False
      
          dfs("JFK")
          return res
      
  • 🗿Min Cost to Connect All Points⛅: 💡

    • points = [[0,0],[2,2],[3,10],[5,2],[7,0]] => 20

    • Prim’s algorithm, visited set, heappop cheapest edge

    • O(ElogV) time, O(v) space
      def minCostConnectPoints(self, points: List[List[int]]) -> int:
          N = len(points)
          adj = {i: [] for i in range(N)}  # i : list of [cost, node]
          for i in range(N):
              x1, y1 = points[i]
              for j in range(i + 1, N):
                  x2, y2 = points[j]
                  dist = abs(x1 - x2) + abs(y1 - y2)
                  adj[i].append([dist, j])
                  adj[j].append([dist, i])
      
          # Prim's
          res = 0
          visit = set()
          minH = [[0, 0]]  # [cost, point]
          while len(visit) < N:
              cost, i = heapq.heappop(minH)
              if i in visit: continue
              res += cost
              visit.add(i)
              for neiCost, nei in adj[i]:
                  if nei not in visit:
                      heapq.heappush(minH, [neiCost, nei])
          return res
      
  • 🗿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
      def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
          edges = collections.defaultdict(list)
          for u, v, w in times:
              edges[u].append((v, w))
      
          minHeap = [(0, k)]
          visit = set()
          t = 0
          while minHeap:
              w1, n1 = heapq.heappop(minHeap)
              if n1 in visit:
                  continue
              visit.add(n1)
              t = w1
      
              for n2, w2 in edges[n1]:
                  if n2 not in visit:
                      heapq.heappush(minHeap, (w1 + w2, n2))
          return t if len(visit) == n else -1
      
  • 🗿 🏢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
      def swimInWater(self, grid: List[List[int]]) -> int:
          N = len(grid)
          visit = set()
          minH = [[grid[0][0], 0, 0]]  # (time/max-height, r, c)
          directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
      
          visit.add((0, 0))
          while minH:
              t, r, c = heapq.heappop(minH)
              if r == N - 1 and c == N - 1:
                  return t
              for dr, dc in directions:
                  neiR, neiC = r + dr, c + dc
                  if (
                      neiR < 0
                      or neiC < 0
                      or neiR == N
                      or neiC == N
                      or (neiR, neiC) in visit
                  ):
                      continue
                  visit.add((neiR, neiC))
                  heapq.heappush(minH, [max(t, grid[neiR][neiC]), neiR, neiC])
      
  • 🅱️Alien Dictionary⛈️: 💡

    • topological sort, DFS cycle detection.

    • O(chars) time, O(chars) space
      def alienOrder(self, words: List[str]) -> str:
          adj = {char: set() for word in words for char in word}
      
          for i in range(len(words) - 1):
              w1, w2 = words[i], words[i + 1]
              minLen = min(len(w1), len(w2))
              if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
                  return ""
              for j in range(minLen):
                  if w1[j] != w2[j]:
                      adj[w1[j]].add(w2[j])
                      break
      
          res = []
          path = set()
          visited = set()
          def dfs(char):
              if char in path: return True  # cycle
              if char in visited: return False
      
              visited.add(char)
              path.add(char)
              for neighChar in adj[char]:
                  if dfs(neighChar): return True  # cycle
              path.remove(char)
              res.append(char)
      
          for char in adj:
              if dfs(char):
                  return ""
      
          res.reverse()
          return "".join(res)
      
  • 🗿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
      def findCheapestPrice(
          self, n: int, flights: List[List[int]], src: int, dst: int, k: int
      ) -> int:
          prices = [float("inf")] * n
          prices[src] = 0
      
          for i in range(k + 1):
              tmpPrices = prices.copy()
      
              for s, d, p in flights:  # s=source, d=dest, p=price
                  if prices[s] == float("inf"):
                      continue
                  if prices[s] + p < tmpPrices[d]:
                      tmpPrices[d] = prices[s] + p
              prices = tmpPrices
          return -1 if prices[dst] == float("inf") else prices[dst]
      

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
      def climbStairs(self, n: int) -> int:
          prev1 = 1
          prev2 = 1
          for _ in range(2, n+1):
              prev1, prev2 = prev2, prev1+prev2
          return prev2
      
  • 🗿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(n) space
      def minCostClimbingStairs(self, cost: List[int]) -> int:
          a = 0
          b = 0
          # min_cost[i] -> min(min_cost[i-1]+cost[i-1], min_cost[i-2]+cost[i-2])
          for i in range(2, len(cost)+1):
              a, b = b, min(a+cost[i-2], b+cost[i-1])
          return b
      
  • 🅱️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
      def rob(self, nums: List[int]) -> int:
          rob1, rob2 = 0, 0
          for n in nums:
              temp = max(n+rob1, rob2)
              rob1 = rob2
              rob2 = temp
          return rob2
      
  • 🅱️House Robber II⛅: 💡

    • nums = [2,3,2] => 3 (circular)

    • max(nums[0], rob1(nums[1:]), rob1(nums[:-1]))

    • O(n) time, O(1) space
      def rob(self, nums: List[int]) -> int:
          return max(nums[0], self.helper(nums[1:]), self.helper(nums[:-1]))
      
      def helper(self, nums):
          rob1, rob2 = 0, 0
      
          for n in nums:
              newRob = max(rob1 + n, rob2)
              rob1 = rob2
              rob2 = newRob
          return rob2
      
  • 🅱️🏢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
      def longestPalindrome(self, s: str) -> str:
          res = ""
          resLen = 0
      
          for i in range(len(s)):
              # odd length
              l, r = i, i
              while l >= 0 and r < len(s) and s[l] == s[r]:
                  if (r - l + 1) > resLen:
                      res = s[l : r + 1]
                      resLen = r - l + 1
                  l -= 1
                  r += 1
      
              # even length
              l, r = i, i + 1
              while l >= 0 and r < len(s) and s[l] == s[r]:
                  if (r - l + 1) > resLen:
                      res = s[l : r + 1]
                      resLen = r - l + 1
                  l -= 1
                  r += 1
      
          return res
      
  • 🅱️Palindrome Substrings⛅: 💡

    • s = "abc" => 3 (a, b, c)

    • similar to the previous one, expand and add to count

    • O(n^2) time, O(1) space
      def countSubstrings(self, s: str) -> int:
          res = 0
      
          for i in range(len(s)):
              res += self.countPali(s, i, i)
              res += self.countPali(s, i, i + 1)
          return res
      
      def countPali(self, s, l, r):
          res = 0
          while l >= 0 and r < len(s) and s[l] == s[r]:
              res += 1
              l -= 1
              r += 1
          return res
      
  • 🅱️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
      def numDecodings(self, s: str) -> int:
          dp = {len(s): 1}
      
          def dfs(i):
              if i in dp: return dp[i]
              if s[i] == "0": return 0
      
              res = dfs(i + 1)
              if i + 1 < len(s) and (
                  s[i] in "12" and s[i + 1] in "0123456"
              ):
                  res += dfs(i + 2)
              dp[i] = res
              return res
      
          return dfs(0)
      
  • 🅱️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
      def coinChange(self, coins: List[int], amount: int) -> int:
          dp = [amount + 1] * (amount + 1)
          dp[0] = 0
      
          for a in range(1, amount + 1):
              for c in coins:
                  if a - c >= 0:
                      dp[a] = min(dp[a], 1 + dp[a - c])
          return dp[amount] if dp[amount] != amount + 1 else -1
      
  • 🅱️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
      def maxProduct(self, nums: List[int]) -> int:
          # O(n)/O(1) : Time/Memory
          res = nums[0]
          curMin, curMax = 1, 1
      
          for n in nums:
      
              tmp = curMax * n
              curMax = max(n * curMax, n * curMin, n)
              curMin = min(tmp, n * curMin, n)
              res = max(res, curMax)
          return res
      
  • 🅱️Word Break⛅: 💡

    • s = "leetcode", words = ["leet", "code"] => true

    • set of words, if word in wordSet and dp(end): return True

    • O(n^2) time, O(n) space
      def wordBreak(self, s: str, wordDict: List[str]) -> bool:
          n = len(s)
          wordSet = set(wordDict)
      
          @lru_cache(None)
          def dp(start):
              if start == n:  # Found a valid way to break words
                  return True
      
              for end in range(start + 1, n + 1):  # O(N^2)
                  word = s[start:end]  # O(N)
                  if word in wordSet and dp(end): return True
              return False
      
          return dp(0)
      
  • 🅱️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
      def lengthOfLIS(self, nums: List[int]) -> int:
          LIS = [1] * len(nums)
      
          for i in range(len(nums) - 1, -1, -1):
              for j in range(i + 1, len(nums)):
                  if nums[i] < nums[j]:
                      LIS[i] = max(LIS[i], 1 + LIS[j])
          return max(LIS)
      
  • 🗿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
      def canPartition(self, nums: List[int]) -> bool:
          if sum(nums) % 2:
              return False
      
          dp = set()
          dp.add(0)
          target = sum(nums) // 2
      
          for i in range(len(nums) - 1, -1, -1):
              nextDP = set()
              for t in dp:
                  if (t + nums[i]) == target:
                      return True
                  nextDP.add(t + nums[i])
                  nextDP.add(t)
              dp = nextDP
          return False
      

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(n) space
      def uniquePaths(self, m: int, n: int) -> int:
          cache = {
              (i, j): 0
              for i in range(m)
              for j in range(n)
          }
          cache[0, 0] = 1
          for i in range(m):
              for j in range(n):
                  if (i, j) == (0, 0):
                      continue
                  cache[i, j] = cache.get((i-1, j), 0) + cache.get((i, j-1), 0)
      
          return cache[m-1, n-1]
      
      def uniquePaths(self, m: int, n: int) -> int:
        """O(n) space"""
          row = [1] * n
      
          for i in range(m - 1):
              newRow = [1] * n
              for j in range(n - 2, -1, -1):
                  newRow[j] = newRow[j + 1] + row[j]
              row = newRow
          return row[0]
      
  • 🅱️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)
      def longestCommonSubsequence(self, text1: str, text2: str) -> int:
          memo = {}
          i, j = 0, 0
          def recursive(i, j):
              if (i, j) in memo:
                  return memo[i, j]
              if i == len(text1) or j == len(text2):
                  return 0
              if text1[i] == text2[j]:
                  memo[i, j] = 1 + recursive(i+1, j+1)
              else:
                  memo[i, j] = max(recursive(i+1, j), recursive(i, j+1))
              return memo[i, j]
          return recursive(0, 0)
      
  • 🗿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
      def maxProfit(self, prices: List[int]) -> int:
      
          cache = {}
          def dfs(i, can_buy):
              if i >= len(prices):
                  return 0
              if (i, can_buy) in cache:
                  return cache[i, can_buy]
      
              result = dfs(i+1, can_buy)
              if can_buy:
                  buy = dfs(i+1, False)-prices[i]
                  result = max(result, buy)
              else:
                  sell = dfs(i+2, True)+prices[i]
                  result = max(result, sell)
              cache[i, can_buy] = result
              return result
      
          return dfs(0, True)
      
  • 🗿Coin Change 2⛅: 💡

    • amount = 5, coins = [1, 2, 5] => 4

    • Unbounded Knapsack, dfs(i, amount), start with dfs(0, 0)

    • O(n*amount) time, O(n*amount) space
      def change(self, amount: int, coins: List[int]) -> int:
          cache = {}
      
          def dfs(i, a):
              if a == amount:
                  return 1
              if a > amount:
                  return 0
              if i == len(coins):
                  return 0
              if (i, a) in cache:
                  return cache[i, a]
      
              cache[i,a] = dfs(i, a+coins[i]) + dfs(i+1, a)
              return cache[i, a]
      
          return dfs(0, 0)
      
  • 🗿Target Sum⛅: 💡

    • assign + or - nums = [1, 1, 1, 1, 1], target = 3 => 5

    • 0/1 Knapsack, O(2^n) -> O(n*sum(nums)))

    • O(n) time, O(n) space
      def findTargetSumWays(self, nums: List[int], target: int) -> int:
          dp = {}  # (index, total) -> # of ways
      
          def backtrack(i, total):
              if i == len(nums):
                  return 1 if total == target else 0
              if (i, total) in dp:
                  return dp[(i, total)]
      
              dp[(i, total)] = backtrack(i + 1, total + nums[i]) + backtrack(
                  i + 1, total - nums[i]
              )
              return dp[(i, total)]
      
          return backtrack(0, 0)
      
  • 🗿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
      def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
          if len(s1) + len(s2) != len(s3):
              return False
      
          dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
          dp[len(s1)][len(s2)] = True
      
          for i in range(len(s1), -1, -1):
              for j in range(len(s2), -1, -1):
                  if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
                      dp[i][j] = True
                  if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
                      dp[i][j] = True
          return dp[0][0]
      
  • 🗿 🏢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
      def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
          rows, cols = len(matrix), len(matrix[0])
          dp = {}
      
          def dfs(r, c, prevVal):
              if r < 0 or r == rows or c < 0 or c == cols or matrix[r][c] <= prevVal:
                  return 0
              if (r, c) in dp:
                  return dp[(r, c)]
      
              res = 1
              res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
              res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
              res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
              res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
              dp[(r, c)] = res
              return res
      
          for r in range(rows):
              for c in range(cols):
                  dfs(r, c, -1)
          return max(dp.values())
      
  • 🗿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
      def numDistinct(self, s: str, t: str) -> int:
          cache = {}
      
          for i in range(len(s) + 1):
              cache[(i, len(t))] = 1
          for j in range(len(t)):
              cache[(len(s), j)] = 0
      
          for i in range(len(s) - 1, -1, -1):
              for j in range(len(t) - 1, -1, -1):
                  if s[i] == t[j]:
                      cache[(i, j)] = cache[(i + 1, j + 1)] + cache[(i + 1, j)]
                  else:
                      cache[(i, j)] = cache[(i + 1, j)]
          return cache[(0, 0)]
      
  • 🗿Edit Distance⛈️: 💡

    • word1 = "horse", word2 = "ros" => 3 (insert, delete, replace)

    • dp, recursive

    • O(m*n) time, O(m*n) space
      def minDistance(self, word1: str, word2: str, memo=None) -> int:
          if not memo:
              memo = {}
          if (word1, word2) in memo:
              return memo[word1, word2]
      
          if word1 == word2: return 0
          if not word1: return len(word2)
          if not word2: return len(word1)
      
          if word1[0] == word2[0]:
              memo[word1, word2] = self.minDistance(word1[1:], word2[1:], memo)
              return memo[word1, word2]
          insert = 1 + self.minDistance(word1, word2[1:], memo)
          delete = 1 + self.minDistance(word1[1:], word2, memo)
          replace = 1 + self.minDistance(word1[1:], word2[1:], memo)
          memo[word1, word2] = min(insert, delete, replace)
          return memo[word1, word2]
      
  • 🗿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
      def maxCoins(self, nums: List[int]) -> int:
          cache = {}
          nums = [1] + nums + [1]
      
          for offset in range(2, len(nums)):
              for left in range(len(nums) - offset):
                  right = left + offset
                  for pivot in range(left + 1, right):
                      coins = nums[left] * nums[pivot] * nums[right]
                      coins += cache.get((left, pivot), 0) + cache.get((pivot, right), 0)
                      cache[(left, right)] = max(coins, cache.get((left, right), 0))
          return cache.get((0, len(nums) - 1), 0)
      
  • 🗿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
      def isMatch(self, s: str, p: str) -> bool:
          cache = {}
      
          def dfs(i, j):
              if (i, j) in cache:
                  return cache[(i, j)]
              if i >= len(s) and j >= len(p):
                  return True
              if j >= len(p):
                  return False
      
              match = i < len(s) and (s[i] == p[j] or p[j] == ".")
              if (j + 1) < len(p) and p[j + 1] == "*":
                  cache[(i, j)] = dfs(i, j + 2) or (  # dont use *
                      match and dfs(i + 1, j)
                  )  # use *
                  return cache[(i, j)]
              if match:
                  cache[(i, j)] = dfs(i + 1, j + 1)
                  return cache[(i, j)]
              cache[(i, j)] = False
              return False
      
          return dfs(0, 0)
      

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
      def maxSubArray(self, nums: List[int]) -> int:
          result = nums[0]
          cur_sum = 0
          for n in nums:
              cur_sum = max(cur_sum+n, n)
              result = max(result, cur_sum)
          return result
      
  • 🅱️Jump Game⛅: 💡

    • nums = [2,3,1,1,4] => true (can reach last index)

    • iterate, calculate max_so_far, if less than curren index, return False

    • O(n) time, O(1) space
      def canJump(self, nums: List[int]) -> bool:
          max_so_far = 0 
          for i, n in enumerate(nums):
              if max_so_far < i:
                  return False
              max_so_far = max(max_so_far, i+n)
          return True
      
  • 🗿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
      def jump(self, nums: List[int]) -> int:
          l, r = 0, 0
          res = 0
          while r < (len(nums) - 1):
              maxJump = 0
              for i in range(l, r + 1):
                  maxJump = max(maxJump, i + nums[i])
              l = r + 1
              r = maxJump
              res += 1
          return res
      
  • 🗿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
      def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
          start, end = len(gas) - 1, 0
          total = gas[start] - cost[start]
      
          while start >= end:
              while total < 0 and start >= end:
                  start -= 1
                  total += gas[start] - cost[start]
              if start == end:
                  return start
              total += gas[end] - cost[end]
              end += 1
          return -1
      
  • 🗿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
      def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
          if len(hand) % groupSize:
              return False
      
          count = {}
          for n in hand:
              count[n] = 1 + count.get(n, 0)
      
          minH = list(count.keys())
          heapq.heapify(minH)
          while minH:
              first = minH[0]
              for i in range(first, first + groupSize):
                  if i not in count:
                      return False
                  count[i] -= 1
                  if count[i] == 0:
                      if i != minH[0]:
                          return False
                      heapq.heappop(minH)
          return True
      
  • 🗿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
      def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
          good = set()
      
          for t in triplets:
              if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
                  continue
              for i, v in enumerate(t):
                  if v == target[i]:
                      good.add(i)
          return len(good) == 3
      
  • 🗿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
      def partitionLabels(self, S: str) -> List[int]:
          count = {}
          res = []
          i, length = 0, len(S)
          for j in range(length):
              c = S[j]
              count[c] = j
      
          curLen = 0
          goal = 0
          while i < length:
              c = S[i]
              goal = max(goal, count[c])
              curLen += 1
      
              if goal == i:
                  res.append(curLen)
                  curLen = 0
              i += 1
          return res
      
  • 🗿Valid Parenthesis String⛅: 💡

    • s = "(*)" => true

    • left_min, left_max, if l_max < 0: return False, if l_min < 0: l_min = 0.

    • O(n^2) time, O(n) space
      def checkValidString(self, s: str) -> bool:
          dp = {(len(s), 0): True}  # key=(i, leftCount) -> isValid
      
          def dfs(i, left):
              if i == len(s) or left < 0:
                  return left == 0
              if (i, left) in dp:
                  return dp[(i, left)]
      
              if s[i] == "(":
                  dp[(i, left)] = dfs(i + 1, left + 1)
              elif s[i] == ")":
                  dp[(i, left)] = dfs(i + 1, left - 1)
              else:
                  dp[(i, left)] = (
                      dfs(i + 1, left + 1) or dfs(i + 1, left - 1) or dfs(i + 1, left)
                  )
              return dp[(i, left)]
      

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
      def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
          if not intervals:
              return [newInterval]
      
          res = []
          for i, interval in enumerate(intervals):
              if interval[1] < newInterval[0]:
                  res.append(interval)
              elif newInterval[1] < interval[0]:
                  res.append(newInterval)
                  return res + intervals[i:]
              else:
                  newInterval = [
                      min(newInterval[0], interval[0]),
                      max(newInterval[1], interval[1])
                  ]
          res.append(newInterval)
          return res
      
  • 🅱️🏢Merge Intervals⛅: 💡

    • intervals = [[1,3],[2,6],[8,10],[15,18]] => [[1,6],[8,10],[15,18]]

    • Sort by start, change prev.end = max(prev.end, curr.end)

    • O(nlogn) time, O(n) space
      def merge(self, intervals: List[List[int]]) -> List[List[int]]:
          result = []
          for start, end in sorted(intervals):
              if not result or start > result[-1][1]:
                  result.append([start, end])
              else:
                  result[-1][1] = max(result[-1][1], end)
          return result
      
  • 🅱️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
      def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
          end = float("-inf")
          overlap = 0
          for s, e in sorted(intervals, key=lambda x: x[1]):
              if s >= end:
                  end = e
              else:
                  overlap += 1
          return overlap
      
  • 🅱️Meeting Rooms☀️: 💡

    • intervals = [(0,30),(5,10),(15,20)] => false

    • sort, if start < prev.end, return false

    • O(nlogn) time, O(n) space
      def canAttendMeetings(self, intervals):
          intervals.sort(key=lambda i: i[0])
      
          for i in range(1, len(intervals)):
              i1 = intervals[i - 1]
              i2 = intervals[i]
      
              if i1[1] > i2[0]:
                  return False
          return True
      
  • 🅱️🏢Meeting Rooms II⛅: 💡 min number of conference rooms.

    • intervals = [(0,30),(5,10),(15,20)] => 2

    • store all sorted timestamps, if start += 1, if end -= 1, max number of rooms

    • O(nlogn) time, O(n) space
      def minMeetingRooms(self, intervals: List[List[int]]) -> int:
          time = []
          for start, end in intervals:
              time.append((start, 1))
              time.append((end, -1))
      
          time.sort(key=lambda x: (x[0], x[1]))
      
          count = 0
          max_count = 0
          for t in time:
              count += t[1]
              max_count = max(max_count, count)
          return max_count
      
  • 🗿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
      def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
          intervals.sort()
          minHeap = []
          res = {}
          i = 0
          for q in sorted(queries):
              while i < len(intervals) and intervals[i][0] <= q:
                  l, r = intervals[i]
                  heapq.heappush(minHeap, (r - l + 1, r))
                  i += 1
      
              while minHeap and minHeap[0][1] < q:
                  heapq.heappop(minHeap)
              res[q] = minHeap[0][0] if minHeap else -1
          return [res[q] for q in queries]
      

Math & Geometry


  • 🅱️Rotate Image⛅: 💡

    • matrix = [[1,2,3],[4,5,6],[7,8,9]] => [[7,4,1],[8,5,2],[9,6,3]]

    • reverse rows, transpose

    • O(cells) time, O(1) space
      def rotate(self, matrix: List[List[int]]) -> None:
          l, r = 0, len(matrix) - 1
          matrix.reverse()
          for i in range(len(matrix)):
              for j in range(i):
                  matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
      
  • 🅱️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
      def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
          res = []
          left, right = 0, len(matrix[0])
          top, bottom = 0, len(matrix)
      
          while left < right and top < bottom:
              # get every i in the top row
              for i in range(left, right):
                  res.append(matrix[top][i])
              top += 1
              # get every i in the right col
              for i in range(top, bottom):
                  res.append(matrix[i][right - 1])
              right -= 1
              if not (left < right and top < bottom):
                  break
              # get every i in the bottom row
              for i in range(right - 1, left - 1, -1):
                  res.append(matrix[bottom - 1][i])
              bottom -= 1
              # get every i in the left col
              for i in range(bottom - 1, top - 1, -1):
                  res.append(matrix[i][left])
              left += 1
      
          return res
      
  • 🅱️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(m+n) space
      def setZeroes(self, matrix: List[List[int]]) -> None:
          # O(1)
          ROWS, COLS = len(matrix), len(matrix[0])
          rowZero = False
      
          # determine which rows/cols need to be zero
          for r in range(ROWS):
              for c in range(COLS):
                  if matrix[r][c] == 0:
                      matrix[0][c] = 0
                      if r > 0:
                          matrix[r][0] = 0
                      else:
                          rowZero = True
      
          for r in range(1, ROWS):
              for c in range(1, COLS):
                  if matrix[0][c] == 0 or matrix[r][0] == 0:
                      matrix[r][c] = 0
      
          if matrix[0][0] == 0:
              for r in range(ROWS):
                  matrix[r][0] = 0
      
          if rowZero:
              for c in range(COLS):
                  matrix[0][c] = 0
      
  • 🗿 🏢Happy Number☀️: 💡

    • n = 19 => true (12 + 92 = 82 |...| 12 + 02 + 02 = 1)

    • Hashset seen or Floyd’s cycle detection

    • O(klogn), O(k) space -> k is num of iterations
      def isHappy(self, n):
          seen = set()
          while n not in seen:
              seen.add(n)
              n = sum([int(x) **2 for x in str(n)])
          return n == 1
      
  • 🗿Plus One☀️: 💡

    • digits = [1,2,3] => [1,2,4]

    • iterate reverse, carry variable, check carry at end

    • O(n) time, O(n) space
      def plusOne(self, digits: List[int]) -> List[int]:
          result = []
          carry = 1
          for i in range(len(digits)-1, -1, -1):
              n = digits[i]+carry
              if n == 10:
                  carry = 1
                  n = 0
              else:
                  carry = 0
              result.append(n)
      
          if carry:
              result.append(1)
          return result[::-1]
      
  • 🗿Pow(x, n)⛅: 💡

    • x = 2.00000, n = 10 => 1024.00000

    • recursive, handle 0 and negatives

    • O(n) time, O(n) space
      def myPow(self, x: float, n: int) -> float:
          if n == 0: return 1
          if n < 0: return 1 / self.myPow(x, -n)
          return x*self.myPow(x, n-1)
      
      def myPow(self, x, n):
          if n == 0: return 1
          if n < 0: return 1 / self.myPow(x, -n)
          # Optimized
          if n % 2 == 1: return x * self.myPow(x, n-1)
          return self.myPow(x*x, n/2)
      
  • 🗿Multiply Strings⛅: 💡

    • num1 = "2", num2 = "3" => "6"

    • Manual multiplication, reverse, for in for

    • O(nm) time, O(n+m) space
      def multiply(self, num1: str, num2: str) -> str:
          if "0" in [num1, num2]:
              return "0"
      
          res = [0] * (len(num1) + len(num2))
          num1, num2 = num1[::-1], num2[::-1]
          for i1 in range(len(num1)):
              for i2 in range(len(num2)):
                  digit = int(num1[i1]) * int(num2[i2])
                  res[i1 + i2] += digit
                  res[i1 + i2 + 1] += res[i1 + i2] // 10
                  res[i1 + i2] = res[i1 + i2] % 10
      
          res, beg = res[::-1], 0
          while beg < len(res) and res[beg] == 0:
              beg += 1
          res = map(str, res[beg:])
          return "".join(res)
      
  • 🗿 🏢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
      def __init__(self):
          self.ptsCount = defaultdict(int)
          self.pts = []
      
      def add(self, point: List[int]) -> None:
          self.ptsCount[tuple(point)] += 1
          self.pts.append(point)
      
      def count(self, point: List[int]) -> int:
          res = 0
          px, py = point
          for x, y in self.pts:
              if (abs(py - y) != abs(px - x)) or x == px or y == py:
                  continue
              res += self.ptsCount[(x, py)] * self.ptsCount[(px, y)]
          return res
      

Bit Manipulation (rare)


Summary

Click to expand
  • 🗿Single Number☀️: 💡

    • nums = [2,2,1] => 1

    • XOR / hashset

    • O(n) time, O(1) space
      def singleNumber(self, nums: List[int]) -> int:
          result = 0
          for n in nums:
              result ^= n
          return result
      
  • 🅱️Number of 1 Bits☀️: 💡

    • n = 11 => 3 (1011)

    • either res += n & 1 and n >> 1

    • O(logn) time, O(1) space
      def hammingWeight(self, n: int) -> int:
          result = 0
          while n:
              result += n & 1
              n = n >> 1
          return result
      
  • 🅱️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
      def countBits(self, n: int) -> List[int]:
          dp = [0] * (n + 1)
          offset = 1
      
          for i in range(1, n + 1):
              if offset * 2 == i:
                  offset = i
              dp[i] = 1 + dp[i - offset]
          return dp
      
  • 🅱️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)
      def reverseBits(self, n: int) -> int:
          res = 0
          for i in range(32):
              bit = (n >> i) & 1
              res += (bit << (31 - i))
          return res
      
  • 🅱️Missing Number☀️: 💡

    • nums = [3,0,1] => 2

    • XOR index+1 and value, similar to duplicate number

    • O(n) time, O(1) space
      def missingNumber(self, nums: List[int]) -> int:
          result = 0
      
          for counter,value in enumerate(nums):
              result ^= counter+1
              result ^= value
          return result
      
  • 🅱️Sum of Two Integers⛅: 💡

    • a = 1, b = 2 => 3

    • return a if b == 0 else getSum(a^b, (a&b)<<1)

    • ...
      def getSum(self, a: int, b: int) -> int:
          def add(a, b):
              if not a or not b:
                  return a or b
              return add(a ^ b, (a & b) << 1)
      
          if a * b < 0:  # assume a < 0, b > 0
              if a > 0:
                  return self.getSum(b, a)
              if add(~a, 1) == b:  # -a == b
                  return 0
              if add(~a, 1) < b:  # -a < b
                  return add(~add(add(~a, 1), add(~b, 1)), 1)  # -add(-a, -b)
      
          return add(a, b)  # a*b >= 0 or (-a) > b > 0
      
  • 🗿Reverse Integer⛅: 💡

    • x = 123 => 321

    • TODO

    • ...
      def reverse(self, x: int) -> int:
          MIN = -2147483648  # -2^31,
          MAX = 2147483647  #  2^31 - 1
      
          res = 0
          while x:
              digit = int(math.fmod(x, 10))  # (python dumb) -1 %  10 = 9
              x = int(x / 10)  # (python dumb) -1 // 10 = -1
      
              if res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10):
                  return 0
              if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):
                  return 0
              res = (res * 10) + digit
      
          return res
      

Extra


  • 🏢Text Justification: 💡

    • words = ["This", "is", "an", "example", "of", "text", "justification."] w = 16 => ["This is an", "example of text", "justification. "]

    • if line_width + len(cur) > maxWidth:, line[j%(len(line)-1 or 1)] += ' '

    • O(n) time, O(n) space
      def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
          result = []
      
          line_width = 0
          line = []
          for w in words:
              if line_width + len(w) <= maxWidth:
                  line.append(w)
                  line_width += 1+len(w)
              else:
                  result.append(line)
                  line_width = len(w)+1
                  line = [w]
          if line:
              result.append(line)
      
          for i, line in enumerate(result):
              spaces = maxWidth - sum(len(w) for w in line)
              if i == len(result)-1:
                  result[i] = " ".join(line).ljust(maxWidth)
              else:
                  for j in range(spaces):
                      line[j%(len(line)-1 or 1)] += ' '
                  result[i] = "".join(line)
          return result
      
  • 🏢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(logN) time, O(n) space
      def __init__(self, w: List[int]):
          self.prefix_sums = []
          prefix_sum = 0
          for weight in w:
              prefix_sum += weight
              self.prefix_sums.append(prefix_sum)
      
      def pickIndex(self) -> int:
          target = self.prefix_sums[-1] * random.random()
          l, r = 0, len(self.prefix_sums)-1
          while l <= r:
              mid = (r+l) // 2
              if target == self.prefix_sums[mid]:
                  return mid
              if target > self.prefix_sums[mid]:
                  l = mid + 1
              else:
                  r = mid - 1
          return l
      
  • 🏢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
      def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
          if message not in self.cache:
              self.cache[message] = timestamp
              return True
          elif self.cache[message] + 10 > timestamp:
              return False
          else:
              self.cache[message] = timestamp
              return True
      
  • 🏢Meeting Rooms III: 💡

    • n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]] => 0

    • heap of ready rooms (room_id), heap of rooms in use (end_time, room_id)

    • O(nlogn) time, O(n) space
      def mostBooked(self, n, meetings):
          ready = [r for r in range(n)] # room_id
          rooms = []  # (end_time, room_id)
          heapify(ready)
          res = [0] * n  # times booked for each room
          for s, e in sorted(meetings):
              # check finished meetings
              while rooms and rooms[0][0] <= s:
                  _, r = heappop(rooms)
                  heappush(ready, r)
              if ready:
                  r = heappop(ready)
                  heappush(rooms, [e, r])
              else:
                  t, r = heappop(rooms)
                  # delayed
                  heappush(rooms, [t + e - s, r])
              res[r] += 1
          return res.index(max(res))
      
  • 🏢Race Car: 💡

    • target = 3 => 2 (“AA” 0 -> 1 -> 3)

    • deque, BFS, but only add reverse if pos + vel < target or pos + vel > target

    • O(logt) time, O(t) space
      def racecar(self, target: int) -> int:
          # 0 moves, 0 position, +1 velocity
          queue = collections.deque([(0, 0, 1)])
          while queue:
              moves, pos, vel = queue.popleft()
      
              if pos == target:
                  return moves
      
              queue.append((moves + 1, pos + vel, 2 * vel))
              if (pos + vel > target and vel > 0) or (pos + vel < target and vel < 0):
                  queue.append((moves + 1, pos, -vel / abs(vel)))
      
  • 🏢Shortest Path in a Grid with Obstacles Elimination: 💡

    • grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 => -1

    • simple bfs with deque [(steps, x, y, k)]

    • O(logt) time, O(t) space
      def shortestPath(self, grid: List[List[int]], k: int) -> int:
          rows, cols = len(grid), len(grid[0])
          target = (rows - 1, cols - 1)
      
          if k >= rows + cols - 2:
              return rows + cols - 2
      
          state = (0, 0, k)
          queue = deque([(0, state)])
          seen = set([state])
      
          while queue:
              steps, (row, col, k) = queue.popleft()
      
              if (row, col) == target:
                  return steps
      
              for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]:
                  if (0 <= new_row < rows) and (0 <= new_col < cols):
                      new_eliminations = k - grid[new_row][new_col]
                      new_state = (new_row, new_col, new_eliminations)
                      if new_eliminations >= 0 and new_state not in seen:
                          seen.add(new_state)
                          queue.append((steps + 1, new_state))
      
          return -1
      

Easy:

  • 🏢First Bad Version: 💡

    • n = 5, isBadVersion(3) = false, isBadVersion(4) = true

    • binary search, return r+1 (r is last good version)

    • O(logn) time, O(1) space
      def firstBadVersion(self, n: int) -> int:
          l = 1
          r = n
          while l <= r:
              mid = (l+r) // 2
              if isBadVersion(mid): r = mid-1
              else: l = mid+1
          return r+1
      
  • 🏢Longest Common Prefix: 💡

    • strs = ["flower","flow","flight"] => "fl"

    • iterate first word and compare

    • O(sum_chars) time, O(1) space
      def longestCommonPrefix(self, strs: List[str]) -> str:
          for i, c in enumerate(strs[0]):
              for string in strs[1:]:
                  if i == len(string) or string[i] != c:
                      return strs[0][:i]
          return strs[0]
      
  • 🏢Tic tac toe: 💡

    • moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] => "A"

    • Try to generalize

    • O(1) time, O(1) space
      def tictactoe(self, moves: List[List[int]]) -> str:
          n = 3
          board = [["" for _ in range(n)] for _ in range(n)]
          first = True
          for i, j in moves:
              board[i][j] = "A" if first else "B"
              first = not first
      
          for row in board:
              if all(c == "A" for c in row):
                  return "A"
              if all(c == "B" for c in row):
                  return "B"
      
          for col in range(n):
              if all(row[col] == "A" for row in board):
                  return "A"
              if all(row[col] == "B" for row in board):
                  return "B"
      
          if all(board[i][i] == "A" for i in range(n)):
              return "A"
          if all(board[i][i] == "B" for i in range(n)):
              return "B"
          if all(board[n-1-i][i] == "A" for i in range(n-1, -1, -1)):
              return "A"
          if all(board[n-1-i][i] == "B" for i in range(n-1, -1, -1)):
              return "B"
      
          return "Draw" if all(row[c] for row in board for c in range(n)) else "Pending"
      
  • 🏢Palindrome Number: 💡

    • x = 121 => true

    • new = new*10 + cur%10

    • O(logn) time, O(1) space
      def isPalindrome(self, x: int) -> bool:
          if x < 0:
              return False
      
          new = 0
          cur = x
          while cur:
              new = new*10+cur%10
              cur = cur // 10
          return new == x
      
  • 🏢Roman to Integer: 💡

    • s = "III" => 3

    • sum, but handle special

    • O(n) time, O(1) space
      def romanToInt(self, s: str) -> int:
          translations = {
              "I": 1,
              "V": 5,
              "X": 10,
              "L": 50,
              "C": 100,
              "D": 500,
              "M": 1000
          }
          number = 0
          s = s.replace("IV", "IIII").replace("IX", "VIIII")
          s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
          s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
          for char in s:
              number += translations[char]
          return number
      

Medium:

  • 🏢Range Sum Query - Mutable: 💡

    • update(i, val), sumRange(i, j)

    • Segment tree

    • O(logn) time, O(n) space

    • ...
  • 🏢Subarray Sum Equals K: 💡

    • nums = [1,1,1], k = 2 => 2 ([1, 1] and [1, 1])

    • prefix sum, result += prefix.get(current_sum-k, 0), initialize d[0] = 1

    • O(n) time, O(n) space
      def subarraySum(self, nums: List[int], k: int) -> int:
          prefix = {0: 1}
          current_sum = 0
          result = 0
          for n in nums:
              current_sum += n
              result += prefix.get(current_sum-k, 0)
              prefix[current_sum] = prefix.get(current_sum, 0) + 1
          return result
      
  • 🏢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

    • ...
  • 🏢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:

  • 🏢Poor Pigs: 💡
    • buckets = 1000, minutesToDie = 15, minutesToTest = 60 => 5
    • TODO
  • 🏢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/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/