Leetcode
List
Tricks
Counter()can be used to create adefaultdict(int)
I do not know….
String Compression
1
2
3class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
return s in (s*2)[1:-1]
Repeated String Match
1
2
3
4
5
6class 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
Find and Replace Pattern
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class 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
Minimum Time Difference
1
2
3
4
5class 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:]))
Valid Palindrome II
https://leetcode.com/problems/valid-palindrome-ii/discuss/701203/Python-Concise-O(n)
- Reverse String II
Group Shifted Strings
1
2
3
4
5
6
7
8
9class 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()
Substring with Concatenation of All Words
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class 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
Reverse Words in a String III
1
2
3class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(w[::-1] for w in s.split())
Add Strings
1
2
3
4
5
6
7
8
9
10
11
12class 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]
String Compression
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class 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
- 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]
Before and After Puzzle
1
2
3
4
5
6
7
8
9
10
11
12class 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))
Add Binary
1
2
3
4
5
6
7
8
9
10
11
12class 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]
Goat Latin
1
2
3
4
5
6
7
8
9
10
11class 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)
Complex Number Multiplication
Find And Replace in String
1
2
3
4
5
6
7
8
9
10
11
12
13
14class 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:]
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
43class 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
Read N Characters Given Read4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class 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)
Read N Characters Given Read4 II - Call multiple times
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class 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)
Reorganize String
1
2
3
4
5
6
7
8
9
10
11
12
13
14class 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)
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
27class 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)
Expressive Words
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class 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
Remove Duplicate Letters
1
2
3
4
5
6
7
8
9
10
11
12
13class 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
Encode and Decode Strings
https://leetcode.com/problems/encode-and-decode-strings/discuss/715649/Python-Straightforward
Swap For Longest Repeated Character Substring
1
2
3
4
5
6
7
8
9
10
11
12
13class 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
Minimum Swaps to Make Strings Equal
1
2
3
4
5
6
7
8class 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))
- Last Substring in Lexicographical Order
Longest Uncommon Subsequence II
1
2
3
4
5
6
7
8
9
10
11
12
13
14class 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
Stamping The Sequence
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class 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 []
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
Longest Palindromic Substring
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
17class 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
Palindrome Pairs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class 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.
- Orderly Queue
Sliding window
Maintain a state while sliding window
easy
- Dictionary, Dictionary, Dictionary
- Prefix_sum
Longest Substring Without Repeating Characters
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class 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
Find Two Non-overlapping Sub-arrays Each With Target Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class 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
Minimum Window Substring
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class 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 ''
Longest Substring with At Most Two Distinct Characters
1
2
3
4
5
6
7
8
9
10
11
12
13
14class 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
Number of Substrings Containing All Three Characters
1
2
3
4
5
6
7
8
9
10
11
12class 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
Largest Rectangle in Histogram
1
2
3
4
5
6
7
8
9
10
11class 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
Maximal Rectangle
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class 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
- Final Prices With a Special Discount in a Shop
Next Greater Element III
https://leetcode.com/problems/next-greater-element-iii/discuss/702697/Python-Concise-O(n)
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.
Valid Parentheses
1
2
3
4
5
6
7
8
9
10
11
12
13class 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
Basic Calculator II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class 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)
Minimum Remove to Make Valid Parentheses
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class 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)
Heap sort / Priority Queue
Smallest Range Covering Elements from K Lists
1
2
3
4
5
6
7
8
9
10
11
12
13
14class 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
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
22class 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]]
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
21class 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
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
21class 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
Snapshot Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class 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
Shortest Palindrome
- Shortest Palindrome
Dynamic programming
MIT 6.006 Introduction to Algorithms, Fall 2011)
Idea
- DP is a smart brute force. It remember state while exhausting all possible cases.
- DP is a DFS. Switching to BFS when it is too slow or taking too much memory to do DFS.
- Transformation formula is the key of DP.
Bottom uporTop downis just the implementation technical. Bottom upimplementation can be used to save memory when we only need states from last n levels.Pay attention to edge cases. Edge cases used to happen when each parameter(dimension variable) reaching 0.
E.g. 10. Regular Expression Matching1
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
67class 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
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
Climbing Stairs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution:
def climbStairs(self, n: int) -> int:
'''
d = {0:1, 1:1}
def helper(k):
if k in d: return d[k]
d[k] = helper(k-1) + helper(k-2)
return d[k]
return helper(n)
'''
a, b = 1, 1
if n == 1: return 1
while n > 1:
a, b = b, a+b
n-=1
return b
House Robber
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: return 0
'''
# bottom up
a, b = 0, nums[0]
for v in nums[1:]:
a, b = b, max(b, a+v)
return b
'''
# Top down
d = {-1: 0, 0: nums[0]}
def helper(k):
if k in d: return d[k]
d[k] = max(helper(k-2)+nums[k], helper(k-1))
return d[k]
return helper(len(nums)-1)
- Triangle
Counting Bits
1
2
3
4
5
6
7
8
9
10
11
12class Solution:
def countBits(self, num: int) -> List[int]:
dp = [0] * (num+1)
if num == 0: return dp
dp[1], prev = 1, 1
for i in range(2, num+1):
if i == prev * 2:
dp[i] = 1
prev = i
else:
dp[i] = 1 + dp[i-prev]
return dp
Best Time to Buy and Sell Stock with Cooldown
- Perfect Squares
- Ugly Number II
- Count Numbers with Unique Digits
Two dimension
Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/discuss/663984/python-concise-dp-on2
Unique Binary Search Trees II
Best Time to Buy and Sell Stock IV
- Guess Number Higher or Lower II
Maximal Square
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
33class Solution:
def maximalSquare(self, M: List[List[str]]) -> int:
if not M or not M[0]: return 0
m, n = len(M), len(M[0])
h, max_l = [0] * n, 0
'''
# bottom up: Time O(M*N) Space O(M*N)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
w = 0
for j in range(n):
if M[i][j] == '0':
w, h[j], dp[i+1][j+1] = 0, 0, 0
else:
w, h[j] = w+1, h[j]+1
dp[i+1][j+1] = min(w, h[j], dp[i][j]+1)
max_l = max(max_l, dp[i+1][j+1])
return max_l * max_l
'''
# bottom up: Time O(M*N) Space O(N)
dp, ndp = [0] * (n+1), [0] * (n+1)
for i in range(m):
w = 0
for j in range(n):
if M[i][j] == '0':
w, h[j], ndp[j+1] = 0, 0, 0
else:
w, h[j] = w+1, h[j]+1
ndp[j+1] = min(w, h[j], dp[j]+1)
max_l = max(max_l, ndp[j+1])
dp, ndp = ndp, [0] * (n+1)
return max_l * max_l
Stone Game II
contest/competitive games
https://leetcode.com/problems/stone-game-ii/discuss/345230/Python-DP-Solution
Scramble String
1
2
3
4
5
6
7
8
9
10class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
# Top down: Time O(N^3) Space O(N^3)
import functools
def dp(s1, s2, rev):
if s1 == s2 or s1 == s2[::-1]: return True
return any(dp(s1[:i], s2[:i], True) and dp(s1[i:], s2[i:], True) for i in range(1, len(s1))) or \
(rev and dp(s1, s2[::-1], not rev))
return dp(s1, s2, True)
Count Different Palindromic Subsequences
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution:
def countPalindromicSubsequences(self, S):
import functools
def dp(start, end): #returns the number of distinct palindromes in S[start:end]
count = 0
segment = S[start:end]
for x in 'abcd':
try:
i = segment.index(x) + start # the starting index in S
j = segment.rindex(x) + start # the ending index in S
except:
continue
count += dp(i+1, j) + 2 if i != j else 1
return count % 1000000007
return dp(0, len(S))
Minimum Cost Tree From Leaf Values
Three dimension
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
- 236. Lowest Common Ancestor of a Binary Tree
- 979. Distribute Coins in Binary Tree)
- 297. Serialize and Deserialize Binary Tree
- 108. Convert Sorted Array to Binary Search Tree
- 105. Construct Binary Tree from Preorder and Inorder Traversal
DFS
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 '')
Same Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class 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
Symmetric Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class 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
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
"""
Generate Parentheses
1
2
3
4
5
6
7
8
9
10
11
12
13class 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
Convert Sorted Array to Binary Search Tree
Construct Binary Tree from Preorder and Inorder Traversal
Serialize and Deserialize Binary Tree
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
55class 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 [""]
'''
BFS
Binary Tree Right Side View
1
2
3
4
5
6
7
8
9
10
11
12
13class 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
- Remove Invalid Parentheses
Perfect Squares
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class 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
Search Suggestions System
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class 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
- 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 | class BIT: |
- Minimum Possible Integer After at Most K Adjacent Swaps On Digits