0%

Leetcode roadmap

Leetcode

image

List

Tricks

  1. Counter() can be used to create a defaultdict(int)

I do not know….

    1. String Compression

      1
      2
      3
      class Solution:  
      def repeatedSubstringPattern(self, s: str) -> bool:
      return s in (s*2)[1:-1]
    1. Repeated String Match

      1
      2
      3
      4
      5
      6
      class Solution:  
      def repeatedStringMatch(self, A: str, B: str) -> int:
      time = (len(B) // len(A)) + (1 if len(B) % len(A) else 0)
      if B in A * time: return time
      if B in A * (time+1): return time+1
      return -1

Pure programming

    1. Find and Replace Pattern

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      class Solution:  
      def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
      def is_valid(word):
      if len(word) != len(pattern):
      return False
      d_12, d_21 = {}, {}
      for c1, c2 in zip(word, pattern):
      if c1 not in d_12:
      if c2 in d_21:
      return False
      d_12[c1] = c2
      d_21[c2] = c1
      elif d_12[c1] != c2:
      return False
      return True
      rst = []
      for word in words:
      if is_valid(word):
      rst.append(word)
      return rst
    1. Minimum Time Difference

      1
      2
      3
      4
      5
      class Solution:  
      def findMinDifference(self, timePoints: List[str]) -> int:
      times = sorted(int(time.split(':')[0])*60+int(time.split(':')[1]) for time in timePoints)
      times.append(times[0]+60*24)
      return min(b-a for a, b in zip(times, times[1:]))
    1. Valid Palindrome II

      https://leetcode.com/problems/valid-palindrome-ii/discuss/701203/Python-Concise-O(n)

    1. Reverse String II
    1. Group Shifted Strings

      1
      2
      3
      4
      5
      6
      7
      8
      9
      class Solution:  
      def groupStrings(self, strings: List[str]) -> List[List[str]]:

      d = defaultdict(list)
      for s in strings:
      delta = ord(s[0]) - ord('a')
      ss = ''.join(chr(97+((ord(c)-97-delta) % 26)) for c in s)
      d[ss].append(s)
      return d.values()
    1. Substring with Concatenation of All Words

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      class Solution:  
      def findSubstring(self, s: str, words: List[str]) -> List[int]:
      if not words:
      return []
      c = Counter(words)
      size = len(words[0])
      rst = []
      for i in range(len(s)+1-size*len(words)):
      j, cc = i, c.copy()
      while j < i+size*len(words) and s[j:j+size] in c:
      cur_w = s[j:j+size]
      cc[cur_w] -= 1
      if cc[cur_w] < 0:
      break
      j += size
      if all(v == 0 for v in cc.values()):
      rst.append(i)
      return rst
    1. Reverse Words in a String III

      1
      2
      3
      class Solution:  
      def reverseWords(self, s: str) -> str:
      return ' '.join(w[::-1] for w in s.split())
    1. Add Strings

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      class Solution:  
      def addStrings(self, num1: str, num2: str) -> str:
      rst = ''
      carry = False
      num1, num2 = list(num1), list(num2)
      while num1 or num2:
      cur = (int(num1.pop()) if num1 else 0) + (int(num2.pop()) if num2 else 0) + carry
      rst += str(cur % 10)
      carry = cur // 10
      if carry:
      rst += '1'
      return rst[::-1]
    1. Custom Sort String

      https://leetcode.com/problems/custom-sort-string/discuss/702725/Python-Concise-O(N)-%2B-Sort

    1. String Compression

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      class Solution:  
      def compress(self, chars: List[str]) -> int:
      idx1, idx2, cnt = 0, 0, 0
      chars.append('0')
      for i, c in enumerate(chars):
      if i != 0 and chars[i] != chars[i-1]:
      chars[idx1] = chars[i-1]
      idx1 += 1
      if cnt == 1:
      continue
      for cc in str(cnt):
      chars[idx1] = cc
      idx1 += 1
      cnt = 1
      else:
      cnt += 1

      return idx1
    1. Multiply Strings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:  
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0': return '0'
num1, num2 = num1[::-1], num2[::-1]
m, n = len(num1), len(num2)
rst = [0] * (m+n)
for i1, v1 in enumerate(num1):
for i2, v2 in enumerate(num2):
rst[i1+i2] += int(v1) * int(v2)
rst[i1+i2+1] += rst[i1+i2] // 10
rst[i1+i2] %= 10
while rst[-1] == 0:
rst.pop()
return ''.join(map(str, rst))[::-1]
    1. One Edit Distance

      https://leetcode.com/problems/one-edit-distance/discuss/702870/Python-Concise-Understand-it-in-5-second

    1. Before and After Puzzle

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      class Solution:  
      def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
      start = defaultdict(list)
      for i, p in enumerate(phrases):
      words = p.split()
      a, b = words[0], ' '.join(words[1:])
      start[a].append((i, b))
      ret = []
      for i, p in enumerate(phrases):
      words = p.split()
      ret += [(p + (f' {w}' if w else '')) for j, w in start[words[-1]] if i != j]
      return sorted(set(ret))
    1. Group Anagrams

      https://leetcode.com/problems/group-anagrams/discuss/681219/Python-Concise-O(N)-no-need-to-sort-str

    1. Add Binary

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      class Solution:  
      def addBinary(self, a: str, b: str) -> str:
      a, b = list(a), list(b)
      carry, rst = False, ''
      while a or b:
      v1, v2 = int(a.pop()) if a else 0, int(b.pop()) if b else 0
      v = v1 + v2 + carry
      rst += str(v % 2)
      carry = v // 2
      if carry:
      rst += '1'
      return rst[::-1]
    1. Goat Latin

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      class Solution:  
      def toGoatLatin(self, S: str) -> str:
      words = []
      for i, s in enumerate(S.split()):
      if s[0].lower() in ['a', 'e', 'i', 'o', 'u']:
      s += 'ma'
      else:
      s = s[1:]+s[0]+'ma'
      s += 'a' * (i+1)
      words.append(s)
      return ' '.join(words)
    1. Complex Number Multiplication

      https://leetcode.com/problems/complex-number-multiplication/discuss/702715/Python-Concise-%2B-Straightforward

    1. Find And Replace in String

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      class Solution:  
      def findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
      opers = [(idx, src, tar) for idx, src, tar in zip(indexes, sources, targets)]
      opers = sorted(opers, key=lambda x: x[0])
      ret, prev = '', 0
      for idx, src, tar in opers:
      if idx > prev:
      ret += s[prev:idx]
      if s[idx:idx+len(src)] == src:
      ret += tar
      else:
      ret += s[idx:idx+len(src)]
      prev = idx + len(src)
      return ret + s[prev:]
    1. LRU Cache

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      class Node:  
      def __init__(self, key, prev=None, next=None):
      self.key, self.prev, self.next = key, prev, next

      class LRUCache:

      def __init__(self, capacity: int):
      self.cap = capacity
      self.d = {}
      self.head, self.tail = Node(None), None

      def get(self, key: int) -> int:
      if key not in self.d: return -1
      self.put(key, self.d[key][0])
      return self.d[key][0]


      def put(self, key: int, value: int) -> None:
      if key in self.d:
      self._remove(self.d[key][1])
      del self.d[key]
      if len(self.d) == self.cap:
      del self.d[self.tail.key]
      self._remove(self.tail)
      self._add_to_head(Node(key))
      self.d[key] = (value, self.head.next)

      def _add_to_head(self, node):
      node.prev, node.next = self.head, self.head.next
      if self.head.next:
      self.head.next.prev = node
      self.head.next = node
      if self.tail is None:
      self.tail = node

      def _remove(self, node):
      node.prev.next = node.next
      if node.next:
      node.next.prev = node.prev
      if self.tail == node:
      self.tail = node.prev
      if self.tail == self.head:
      self.tail = None
    1. Read N Characters Given Read4

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      class Solution:  
      def read(self, buf, n):
      """
      :type buf: Destination buffer (List[str])
      :type n: Number of characters to read (int)
      :rtype: The number of actual characters read (int)
      """
      if n <= 0: return 0
      for i in range(n)[::4]:
      tmp = [0] * 4
      size = read4(tmp)
      for j in range(size):
      buf[i+j] = tmp[j]
      if size != 4: break
      return min(n, i+size)
    1. Read N Characters Given Read4 II - Call multiple times

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      class Solution:  
      def __init__(self):
      self.remain = []

      def read(self, buf: List[str], n: int) -> int:
      while len(self.remain) < n:
      tmp = [None] * 4
      cnt = read4(tmp)
      self.remain.extend(tmp[:cnt])
      if cnt < 4:
      break
      cnt = len(self.remain)
      for i in range(min(cnt, n)):
      buf[i] = self.remain[i]
      self.remain[:n] = []
      return min(cnt, n)
    1. Reorganize String

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      class Solution:  
      def reorganizeString(self, S: str) -> str:
      rst = []
      counter = Counter(S)
      order = sorted(counter.keys(), key=lambda x: -counter[x])
      idx, size = 0, counter[order[0]]
      bucket = [[] for _ in range(size)]
      for c in order:
      for _ in range(counter[c]):
      bucket[idx].append(c)
      idx = (idx+1) % size
      if size > 1 and len(bucket[size-2]) == 1:
      return ''
      return ''.join(''.join(b) for b in bucket)
    1. Brace Expansion II

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      class Solution:  
      def braceExpansionII(self, expression: str) -> List[str]:
      def helper(pattern):
      item, items = [''], []
      pattern = deque(pattern)
      while pattern:
      cur = pattern.popleft()
      if cur == ',':
      items.append(item)
      item = ['']
      else:
      if cur == '{':
      level = 1
      sub_p = ''
      while level:
      sub_p += pattern.popleft()
      if sub_p[-1] == '{': level += 1
      elif sub_p[-1] == '}': level -= 1
      sub_p = sub_p[:-1]
      cur = helper(sub_p)
      else:
      cur = [cur]
      item = [a+b for a in item for b in cur]
      else:
      items.append(item)
      return sorted(set(s for item in items for s in item))
      return helper(expression)
    1. Remove Comments

      https://leetcode.com/problems/remove-comments/discuss/702669/Python-line-by-line-O(N)

    1. Expressive Words

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      class Solution:  
      def expressiveWords(self, S: str, words: List[str]) -> int:
      def condense(s):
      p_c, cnt, ret = s[0], 1, []
      for c in s[1:]+'$':
      if c != p_c:
      ret.append((p_c, cnt))
      p_c, cnt = c, 1
      else:
      cnt += 1
      return ret

      cond = condense(S)
      ret = 0
      for word in words:
      cond_cur = condense(word)
      if len(cond_cur) == len(cond) and all(a[0]==b[0] and (a[1]==b[1] or a[1]>b[1] and a[1]>=3) for a, b in zip(cond, cond_cur)):
      ret += 1
      return ret
    1. Remove Duplicate Letters

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      class Solution:  
      def removeDuplicateLetters(self, s: str) -> str:
      ret, start = '', 0
      chars = set(s)
      while chars:
      for c in string.ascii_lowercase:
      if c in ret or c not in s: continue
      if set(s[s.index(c):]) >= chars:
      ret += c
      chars.remove(c)
      s = s[s.index(c)+1:]
      break
      return ret
    1. Encode and Decode Strings

      https://leetcode.com/problems/encode-and-decode-strings/discuss/715649/Python-Straightforward

    1. Swap For Longest Repeated Character Substring

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      class Solution:  
      def maxRepOpt1(self, s: str) -> int:
      c_len, size = [[c, len(list(g))] for c, g in itertools.groupby(s)], 1
      ret = 0
      counter = Counter(c for c, size in c_len)
      for i, (c, size) in enumerate(c_len):
      ret = max(ret, size+(counter[c]>1))
      if i >= 2 and c_len[i-1][1] == 1 and c_len[i-2][0] == c:
      if counter[c] > 2:
      ret = max(ret, size + c_len[i-2][1] + 1)
      else:
      ret = max(ret, size + c_len[i-2][1])
      return ret
    1. Minimum Swaps to Make Strings Equal

      1
      2
      3
      4
      5
      6
      7
      8
      class Solution:  
      def minimumSwap(self, s1: str, s2: str) -> int:
      xy, yx = 0, 0
      for a, b in zip(s1, s2):
      if a == b: continue
      elif a == 'x': xy += 1
      else: yx += 1
      return -1 if (xy+yx) % 2 else ((xy+yx) // 2 + (xy%2))
    1. Valid Parenthesis String

      https://leetcode.com/problems/valid-parenthesis-string/discuss/107570/JavaC%2B%2BPython-One-Pass-Count-the-Open-Parenthesis

    1. Last Substring in Lexicographical Order
    1. Longest Uncommon Subsequence II

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      class Solution:  
      def findLUSlength(self, strs: List[str]) -> int:
      # This is an important technic to check whether a string is a substring of another string
      def is_substr(s, ss):
      idx = 0
      for c in ss:
      if idx < len(s) and c == s[idx]:
      idx += 1
      return idx == len(s)
      strs = sorted(strs, key=lambda x:len(x), reverse=True)
      for i, s in enumerate(strs):
      if all(not is_substr(s, ss) for j, ss in enumerate(strs) if i != j):
      return len(s)
      return -1
    1. Stamping The Sequence

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      class Solution:  
      def movesToStamp(self, s: str, t: str) -> List[int]:
      def check(idx):
      moved = False
      for i in range(m):
      if t[idx+i] == '?': continue
      if t[idx+i] != s[i]: return False
      moved = True
      t[idx:idx+m] = ['?'] * m
      if moved:
      ret.append(idx)
      return moved
      m, n, ret, s, t = len(s), len(t), [], list(s), list(t)
      moved = True
      while moved:
      moved = False
      for i in range(n-m+1):
      moved |= check(i)
      return ret[::-1] if t == ['?']*n else []
    1. Reverse Words in a String II

      https://leetcode.com/problems/reverse-words-in-a-string-ii/discuss/715615/Python-Concise-In-place

Palindromic

Manacher’s Algorithm
https://www.youtube.com/watch?v=nbTSfrEfo6M

    1. Longest Palindromic Substring

      https://leetcode.com/problems/longest-palindromic-substring/discuss/3337/Manacher-algorithm-in-Python-O(n)

    1. Palindromic Substrings

      O(N^2) - None Manacher’s Algorithm

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      class Solution:  
      def countSubstrings(self, s: str) -> int:
      if not s: return 0
      rst = len(s)
      i = 0
      while i < len(s):
      j = i
      while i+1 < len(s) and s[i] == s[i+1]:
      i += 1
      rst += i-j
      rr = i
      while j - 1 >= 0 and i + 1 < len(s) and s[j-1] == s[i+1]:
      j -= 1
      i += 1
      rst += 1
      i = rr + 1
      return rst
    1. Palindrome Pairs

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      class Solution:  
      def palindromePairs(self, words: List[str]) -> List[List[int]]:
      d = {word: i for i, word in enumerate(words)}
      rst = set()
      for i, word in enumerate(words):
      t = word[::-1]
      # (i, j)
      for j in range(len(t)+1):
      cur = t[j:]
      if word+cur == str(word+cur)[::-1] and cur in d and cur != word:
      rst.add((i, d[cur]))
      # (j, i)
      for j in range(len(t), -1, -1):
      cur = t[:j]
      if cur+word == str(cur+word)[::-1] and cur in d and cur != word:
      rst.add((d[cur], i))
      return [list(item) for item in rst]

Math

I do not know.
You tell me how to solve it.

    1. Orderly Queue

Sliding window

Maintain a state while sliding window

  • easy

    1. Dictionary, Dictionary, Dictionary
    2. Prefix_sum
      1. Longest Substring Without Repeating Characters

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        class Solution:  
        def lengthOfLongestSubstring(self, s: str) -> int:
        d = Counter()
        l, r, rst = 0, 0, 0
        while r < len(s):
        c = s[r]
        r += 1
        d[c] += 1
        if d[c] <= 1:
        rst = max(rst, r-l)
        else:
        while l < r:
        cc = s[l]
        l += 1
        d[cc] -= 1
        if d[cc] == 1:
        break
        return rst
      1. Find Two Non-overlapping Sub-arrays Each With Target Sum

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        class Solution:  
        def minSumOfLengths(self, arr: List[int], target: int) -> int:
        prefix = {0: -1}
        best, bests, rst = math.inf, [math.inf] * len(arr), math.inf
        cur = 0
        for i, v in enumerate(arr):
        cur += v
        if cur - target in prefix:
        begin = prefix[cur-target]
        if begin > -1:
        rst = min(rst, i-begin + bests[begin])
        best = min(best, i-begin)
        bests[i] = best
        prefix[cur] = i
        return rst if rst != math.inf else -1
      1. Minimum Window Substring

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        class Solution:  
        def minWindow(self, s: str, t: str) -> str:
        c = Counter(t)
        cnt = len(c)
        l, r, rst = 0, 0, s+t
        while r < len(s) or cnt == 0:
        if cnt == 0:
        # move l
        c[s[l]] += 1
        if c[s[l]] == 1:
        cnt += 1
        l += 1
        else:
        # move r
        c[s[r]] -= 1
        if c[s[r]] == 0:
        cnt -= 1
        r += 1
        if cnt == 0 and len(s[l:r]) < len(rst):
        rst = s[l:r]
        return rst if rst != s+t else ''
      1. Longest Substring with At Most Two Distinct Characters

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        class Solution:  
        def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        d, cnt, ret = Counter(), 2, 0
        for i, c in enumerate(s):
        d[c] += 1
        if d[c] == 1:
        cnt += 1
        if len(d) <= 2:
        ret += 1
        else:
        d[s[i-ret]] -= 1
        if d[s[i-ret]] == 0:
        del d[s[i-ret]]
        return ret
      1. Number of Substrings Containing All Three Characters

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        class Solution:  
        def numberOfSubstrings(self, s: str) -> int:
        ret, d, cnt, l = 0, Counter(), 0, 0
        for i, c in enumerate(s):
        d[c] += 1
        if d[c] == 1: cnt += 1
        if cnt == 3:
        while d[s[l]] > 1:
        d[s[l]] -= 1
        l += 1
        ret += l+1
        return ret
  • Monotone Stack

      1. Largest Rectangle in Histogram

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        class Solution:  
        def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        rst = 0
        for i, height in enumerate(heights + [0]):
        idx_prev = i
        while stack and stack[-1][1] >= height:
        idx_prev, h_prev = stack.pop()
        rst = max(rst, (i - idx_prev) * h_prev)
        stack.append((idx_prev, height))
        return rst
      1. Maximal Rectangle

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        class Solution:  
        def maximalRectangle(self, M: List[List[str]]) -> int:
        if not M or not M[0]: return 0
        m, n = len(M), len(M[0])
        rst = 0
        h = [0] * (n+1)
        for row in M:
        stack = [(0, -1)]
        for i, v in enumerate(row+[0]):
        if v == '1':
        h[i] += 1
        else:
        h[i] = 0
        idx = i
        while stack and stack[-1][0] > h[i]:
        height, idx = stack.pop()
        rst = max(rst, height * (i-idx))
        stack.append((h[i], idx))
        return rst
      1. Final Prices With a Special Discount in a Shop
      1. Next Greater Element III

        https://leetcode.com/problems/next-greater-element-iii/discuss/702697/Python-Concise-O(n)

      1. Maximum Binary Tree

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        # Definition for a binary tree node.  
        # class TreeNode:
        # def __init__(self, val=0, left=None, right=None):
        # self.val = val
        # self.left = left
        # self.right = right
        class Solution:
        def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        '''
        # Recursive
        if not nums: return None
        val = max(nums)
        return TreeNode(val, self.constructMaximumBinaryTree(nums[:nums.index(val)]),
        self.constructMaximumBinaryTree(nums[nums.index(val)+1:]))
        '''
        '''
        # Recursive optimized
        def dfs(l, r):
        if l == r: return None
        val = max(nums[l:r])
        idx = l + nums[l:r].index(val)
        return TreeNode(val, dfs(l, idx), dfs(idx+1, r))
        return dfs(0, len(nums))
        '''
        '''
        # Non-recursive
        ret = TreeNode()
        stack = [((0, len(nums)), (ret, 'l'))]
        while stack:
        (l, r), (p, dir) = stack.pop()
        if l == r: continue
        node = TreeNode(max(nums[l:r]))
        idx = l + nums[l:r].index(node.val)
        if dir == 'l': p.left = node
        else: p.right = node

        stack.append(((idx+1, r), (node, 'r')))
        stack.append(((l, idx), (node, 'l')))
        return ret.left
        '''
        # Optimal
        stack = []
        for val in nums:
        node = TreeNode(val)
        left = None
        while stack and stack[-1].val < val:
        left = stack.pop()
        node.left = left
        if stack:
        stack[-1].right = node
        stack.append(node)
        return stack[0]
  • Monotone queue

  • stack

    https://en.wikipedia.org/wiki/Stack_(abstract_data_type))

    O(1) to push and pop at end.

      1. Valid Parentheses

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        class Solution:  
        def isValid(self, s: str) -> bool:
        stack = []
        pairs = {'(': ')', '[': ']', '{': '}'}
        for c in s:
        if c in ['(', '[', '{']:
        stack.append(pairs[c])
        else:
        if stack and stack[-1] == c:
        stack.pop()
        else:
        return False
        return not stack
      1. Basic Calculator II

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        class Solution:  
        def calculate(self, s: str) -> int:
        s = s.strip().replace(' ', '')
        nums = []
        sign, val = '+', 0
        for i, c in enumerate(s):
        if c.isdigit():
        val = val*10 + int(c)
        if not c.isdigit() or i == len(s)-1:
        if sign == '+':
        nums.append(val)
        elif sign == '-':
        nums.append(-val)
        elif sign == '*':
        nums.append(nums.pop() * val)
        elif sign == '/':
        nums.append(int(nums.pop() / val))
        sign = c
        val = 0
        return sum(nums)
      1. Minimum Remove to Make Valid Parentheses

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        class Solution:  
        def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        remove = set()
        for i, c in enumerate(s):
        if c == '(':
        stack.append(i)
        elif c == ')':
        if stack:
        stack.pop()
        else:
        remove.add(i)
        for i in stack:
        remove.add(i)
        return ''.join(c for i, c in enumerate(s) if i not in remove)
      1. Score of Parentheses

        https://leetcode.com/problems/score-of-parentheses/discuss/141777/C%2B%2BJavaPython-O(1)-Space

Heap sort / Priority Queue

    1. Smallest Range Covering Elements from K Lists

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      class Solution:  
      def smallestRange(self, nums: List[List[int]]) -> List[int]:
      q = [(num[0], num, 1) for num in nums]
      heapq.heapify(q)
      rst = [min(q)[0], max(q)[0]]
      cur_max = max(q)[0]
      while True:
      val, num, idx = heapq.heappop(q)
      if idx == len(num):
      return rst
      heapq.heappush(q, (num[idx], num, idx+1))
      cur_max = max(num[idx], cur_max)
      if cur_max - q[0][0] < rst[1] - rst[0]:
      rst = [q[0][0], cur_max]

Binary Search

Ideal

  • Binary search can be used to guess answer in a known range.

Leverage library if it is available.

  • Python: bisect.bisect_left, bisect.bisect_right
  • C++: lower_bound, upper_bound
    1. Design Log Storage System

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      class LogSystem:  

      def __init__(self):
      self.data = []

      def put(self, id: int, timestamp: str) -> None:
      bisect.insort_left(self.data, (timestamp, id))

      def retrieve(self, s: str, e: str, gra: str) -> List[int]:
      gra_to_idx = {
      'Year': 4,
      'Month': 7,
      'Day': 10,
      'Hour': 13,
      'Minute': 16,
      'Second': 19
      }
      s = s[:gra_to_idx[gra]]
      e = e[:gra_to_idx[gra]]+':'+'9'*32

      idx1, idx2 = bisect.bisect_left(self.data, (s, -math.inf)), bisect.bisect(self.data, (e, math.inf))
      return [item[1] for item in self.data[idx1:idx2]]
    1. Split Array Largest Sum

      Guess answer by using binary search

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      class Solution:  
      def splitArray(self, nums: List[int], m: int) -> int:
      def valid_sum(max_sum):
      cnt, cur = 1, 0
      for num in nums:
      cur += num
      if cur > max_sum:
      cnt += 1
      cur = num
      if cnt > m:
      return False
      return True
      # Binary search
      l, r = max(nums), sum(nums)
      while l < r:
      mid = (l+r) // 2
      if valid_sum(mid):
      r = mid
      else:
      l = mid+1
      return l
    1. Minimum Number of Days to Make m Bouquets

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      class Solution:  
      def minDays(self, B: List[int], m: int, k: int) -> int:
      def ok(day):
      fl = 0
      cnt = 0
      for d in B:
      fl = fl + 1 if day >= d else 0
      if fl >= k:
      cnt += 1
      fl = 0
      return cnt >= m

      l, r = min(B), max(B)+1
      while l < r:
      #print(f'{l} {r}')
      mid = (l+r) // 2
      if ok(mid):
      r = mid
      else:
      l = mid + 1
      return l if l <= max(B) else -1
    1. Snapshot Array

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      class SnapshotArray:  

      def __init__(self, length: int):
      self.d = defaultdict(list)
      for i in range(length):
      self.d[i].append((0, 0))
      self.v = 0

      def set(self, index: int, val: int) -> None:
      self.d[index].append((self.v, val))

      def snap(self) -> int:
      self.v += 1
      return self.v - 1

      def get(self, index: int, snap_id: int) -> int:
      idx = bisect.bisect(self.d[index], (snap_id, float'inf')) - 1
      return self.d[index][idx][1]

KMP

    1. Shortest Palindrome

      1. Shortest Palindrome

Dynamic programming

MIT 6.006 Introduction to Algorithms, Fall 2011)

Idea

  1. DP is a smart brute force. It remember state while exhausting all possible cases.
  2. DP is a DFS. Switching to BFS when it is too slow or taking too much memory to do DFS.
  3. Transformation formula is the key of DP. Bottom up or Top down is just the implementation technical.
  4. Bottom up implementation can be used to save memory when we only need states from last n levels.
  5. Pay attention to edge cases. Edge cases used to happen when each parameter(dimension variable) reaching 0.
    E.g. 10. Regular Expression Matching

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
        class Solution:  
    def isMatch(self, s: str, p: str) -> bool:
    # Memorization: Time O(M*N) Space O(M*N)
    m, n = len(s), len(p)
    import functools
    @functools.lru_cache(None)
    def dp(x, y):
    if y == 0: return x == 0
    if x == 0: return y == 0 or y>=2 and p[y-1] == '*' and dp(x, y-2)
    if p[y-1] != '*':
    return p[y-1] in [s[x-1], '.'] and dp(x-1, y-1)
    else:
    return y>1 and (dp(x, y-2) or p[y-2] in [s[x-1], '.'] and dp(x-1, y))
    return dp(m, n)
    ```

    6. Same idea when dealing contest/competitive games. Find the optimal move by exhausting all possible choice.
    ```python
    DP(n) = max(Profit(move) - DP(move/next_start_point) for move in possible_moves)
    ```

    > Useful trick


    1. `dict` can be more flexible compare to `array` since you can switch between `i`, `i+1`, `i-1` as needed when dealing edge cases.
    2. Use tuple as key when multiple dimension dictionary/array is needed.

    ```python
    dp = {}
    # 1-d
    dp[0] = 10
    # 2-d
    dp[0, 0] = 10
    # 3-d
    dp[0,0,0] = 10
    ```

    3. `@lru_cache(None)` can be used for `Top down` implementation.
    4. `State transformation formular` can be identical between `bottom up` and `top down` approach if we use variable carfully.

    > [10. Regular Expression Matching]([https://leetcode.com/problems/regular-expression-matching/discuss/665501/Python-Concise-DP-Botton-up-%2B-Top-down](https://leetcode.com/problems/regular-expression-matching/discuss/665501/Python-Concise-DP-Botton-up-%2B-Top-down))
    > [44. Wildcard Matching]([https://leetcode.com/problems/wildcard-matching/discuss/687707/Python-Concise-DP-Bottom-up-%2B-Top-down](https://leetcode.com/problems/wildcard-matching/discuss/687707/Python-Concise-DP-Bottom-up-%2B-Top-down))

    ### One dimension

    - 91. Decode Ways

    ```python
    class Solution:
    def numDecodings(self, s: str) -> int:
    '''
    # Top down: Time O(N) Space O(N)
    dp = {0: 1}
    def helper(x):
    if x in dp: return dp[x]
    dp[x] = (helper(x-1) if s[x-1] != '0' else 0) + (helper(x-2) if x > 1 and 9 < int(s[x-2:x]) <= 26 else 0)
    return dp[x]
    return helper(len(s))
    '''
    # Bottom up: Time O(N) Space O(1)
    p2, p1 = 1, 1 if s[0] != '0' else 0
    for i in range(1, len(s)):
    cur = p1 if s[i] != '0' else 0
    cur += p2 if 9 < int(s[i-1:i+1]) <= 26 else 0
    if cur == 0: return 0
    p2, p1 = p1, cur
    return p1

Two dimension

Three dimension

    1. Paint House III

      https://leetcode.com/problems/paint-house-iii/discuss/674485/Python-Solution

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30

      class Solution:
      def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
      '''
      # Top down: Time O(m*n*t*n) Space O(m*n*t)
      dp = {}# idx, t, color
      def helper(x, t, c):
      if (x, t ,c) in dp: return dp[x, t, c]
      if x < t or t < 1 or x < 0: return float('inf')
      my_cost = cost[x][c] if houses[x] == 0 else (0 if houses[x] == c+1 else float('inf'))
      if x == 0 and t == 1: return my_cost
      dp[x, t, c] = helper(x-1, t, c) + my_cost
      for i in range(n):
      if i == c: continue
      dp[x, t, c] = min(dp[x, t, c], helper(x-1, t-1, i)+my_cost)
      return dp[x, t, c]
      rst = min(helper(m-1, target, c) for c in range(n))
      return rst if rst != float('inf') else -1
      '''
      # Bottom up: Time O(m*n*t*n) Space O(n*t)
      dp, ndp = {(0,0): 0}, {} # (color, group)
      for i, c in enumerate(houses):
      for cc in (range(1, n+1) if c == 0 else [c]):
      for c_prev, g_prev in dp:
      g_new = g_prev + (cc != c_prev)
      if g_new > target: continue
      ndp[cc, g_new] = min(ndp.get((cc, g_new), float('inf')), dp[c_prev, g_prev] + (cost[i][cc-1] if c == 0 else 0))
      dp, ndp = ndp, {}

      return min([dp[c, g] for c, g in dp if g == target] or [-1])

Tree

Recursive! Recursive! Recursive!

pre/in/post order traversal

https://yonglife.com/2019/05/04/binary-tree-traversal-updated/

Recursive to Non-recursive

DFS

    1. Construct String from Binary Tree

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      # Definition for a binary tree node.  
      # class TreeNode:
      # def __init__(self, val=0, left=None, right=None):
      # self.val = val
      # self.left = left
      # self.right = right
      class Solution:
      def tree2str(self, t: TreeNode) -> str:
      if t == None:
      return ''
      l, r = self.tree2str(t.left), self.tree2str(t.right)
      return f'{t.val}' + (f'({l})' if l or r else '') + (f'({r})' if r else '')
    1. Same Tree

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      class Solution:  
      def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
      '''
      # Recursive: Time O(N) Space O(N)
      if not p and not q: return True
      if not (p and q and p.val == q.val): return False
      return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
      '''
      # Non-recursive: Time O(N) Space O(N)
      stack = []
      while p or q or stack:
      while p or q:
      if not ((p and q) and p.val == q.val): return False
      stack.append((p.right, q.right))
      p, q = p.left, q.left
      p, q = stack.pop()
      return True
    1. Symmetric Tree

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      class Solution:  
      def isSymmetric(self, root: TreeNode) -> bool:
      '''
      # Recursive
      def dfs(a, b):
      if ((a is None) ^ ( b is None)) or (a and a.val != b.val): return False
      if not a: return True
      return dfs(a.left, b.right) and dfs(a.right, b.left)
      return dfs(root.left, root.right) if root else True
      '''
      # Non-recursive
      if not root: return True
      stack = [(root.left, root.right)]
      while stack:
      a, b = stack.pop()
      if (a is None) ^ (b is None): return False
      if a and a.val != b.val: return False
      if not a: continue

      stack.append((a.left, b.right))
      stack.append((a.right, b.left))
      return True
    1. Binary Search Tree Iterator

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      # Definition for a binary tree node.  
      # class TreeNode:
      # def __init__(self, val=0, left=None, right=None):
      # self.val = val
      # self.left = left
      # self.right = right
      class BSTIterator:

      def __init__(self, root: TreeNode):
      self.stack = []
      self._next(root)

      def _next(self, node):
      while node:
      self.stack.append(node)
      node = node.left

      def next(self) -> int:
      """
      @return the next smallest number
      """
      node = self.stack.pop()
      self._next(node.right)
      return node.val


      def hasNext(self) -> bool:
      """
      @return whether we have a next smallest number
      """
    1. Generate Parentheses

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      class Solution:  
      def generateParenthesis(self, n: int) -> List[str]:
      def dfs(l, r, s):
      if not l and not r:
      rst.append(s)
      return
      if l:
      dfs(l-1, r, s+'(')
      if l < r:
      dfs(l, r-1, s+')')
      rst = []
      dfs(n, n, '')
      return rst
    1. Convert Sorted Array to Binary Search Tree

      https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/719416/Python-Concise-Recursive-%2B-Non-recursive

    1. Construct Binary Tree from Preorder and Inorder Traversal

      https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/719653/Python-Concise-Recursive-%2B-Optimized-recursive-%2B-Non-recursive

    1. Serialize and Deserialize Binary Tree

      https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/719519/Python-Concise-Recursive-%2B-Non-recursive

    1. Remove Invalid Parentheses

      DFS is simple. It is only the matter of how many unnecessary subtree we can cut.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      class Solution:  
      def removeInvalidParentheses(self, s: str) -> List[str]:
      # BFS Time: 2^N Space: 2^N
      l = 0
      for c in s:
      if c == '(':
      l += 1
      elif c == ')':
      l -= 1
      if l < 0: return False
      return l == 0
      q, nq = [(s, 0)], []
      rst = []
      while q:
      for cur in q:
      if is_valid(cur[0]):
      rst.append(cur[0])
      else:
      s, cur_idx = cur
      for i in range(cur_idx, len(s)):
      if i == cur_idx or s[i-1] != s[i]:
      nq.append((s[:i]+s[i+1:], i))
      if rst:
      break
      q, nq = nq, []
      return rst

      '''
      # DFS Time: 2^N Space N
      rm_l, rm_r = 0, 0
      for c in s:
      if c == '(':
      rm_l += 1
      elif c == ')':
      if rm_l > 0:
      rm_l -= 1
      else:
      rm_r += 1
      def dfs(cur, idx, rm_l, rm_r, l):
      if idx == len(s) or rm_l < 0 or rm_r < 0 or l < 0:
      if rm_l == 0 and rm_r == 0 and l == 0:
      rst.add(cur)
      return
      if s[idx] == '(':
      dfs(cur, idx+1, rm_l-1, rm_r, l)
      dfs(cur+s[idx], idx+1, rm_l, rm_r, l+1)
      elif s[idx] == ')':
      dfs(cur, idx+1, rm_l, rm_r-1, l)
      dfs(cur+s[idx], idx+1, rm_l, rm_r, l-1)
      else:
      dfs(cur+s[idx], idx+1, rm_l, rm_r, l)
      rst = set()
      dfs('', 0, rm_l, rm_r, 0)
      return list(rst) if rst else [""]
      '''
    1. Merge Two Binary Trees

      https://leetcode.com/problems/merge-two-binary-trees/discuss/718497/Python-Concise-Recursive-%2B-Non-recursive

BFS

    1. Binary Tree Right Side View

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      class Solution:  
      def rightSideView(self, root: TreeNode) -> List[int]:
      if not root: return []
      q, nq, ret = deque([root]), deque(), [root.val]
      while q:
      cur = q.popleft()
      if cur.left: nq.append(cur.left)
      if cur.right: nq.append(cur.right)

      if not q and nq:
      ret.append(nq[-1].val)
      q, nq = nq, deque()
      return ret
    1. Remove Invalid Parentheses
    1. Word Ladder II

      https://leetcode.com/problems/word-ladder-ii/discuss/269012/Python-BFS%2BBacktrack-Greatly-Improved-by-bi-directional-BFS

    1. Perfect Squares

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      class Solution:  
      def numSquares(self, n: int) -> int:
      if n <= 2: return n
      square_table = [i*i for i in range(1, int(n**0.5)+1)]
      q, nq = [n], []
      rst = 0
      while q:
      rst += 1
      for x in q:
      for i in square_table:
      if i == x:
      return rst
      elif i > x:
      break
      nq.append(x-i)
      q, nq = nq, []
      return rst

Trie

    1. Search Suggestions System

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      class Node:  
      def __init__(self):
      self.words = []
      self.next = defaultdict(Node)
      class Solution:
      def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
      products = sorted(products)
      tries = Node()
      for product in products:
      cur = tries
      for c in product:
      cur = cur.next[c]
      cur.words.append(product)
      ret, cur = [], tries
      for c in searchWord:
      cur = cur.next[c]
      ret.append(cur.words[:3])
      return ret

Segment Tree

Binary Lifting

    1. Kth Ancestor of a Tree Node

Binary Index Tree

Wikipedia: A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class BIT:  
def __init__(self, size):
self.arr = [0] * size

def add(self, x, delta):
while x < len(self.arr):
self.arr[x] += delta
x += self._lowbit(x)

def sum(self, x):
ret = 0
while x:
ret += self.arr[x]
x -= self._lowbit(x)
return ret

def _lowbit(self, x):
return x & (-x)
    1. Minimum Possible Integer After at Most K Adjacent Swaps On Digits