Skip to main content

57 posts tagged with "Medium"

View All Tags

· One min read
from typing import Callable


class Solution:
def evalRPN(self, tokens: list[str]) -> int:
stack: list[int] = []
operators: dict[str, Callable[[int, int], int]] = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: int(a / b),
}
for token in tokens:
if token in operators:
b, a = stack.pop(), stack.pop()
stack.append(operators[token](a, b))
else:
stack.append(int(token))
return stack[0]

· One min read
class Solution:
def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
result = [0] * len(temperatures)
stack = []
for r in range(len(temperatures)):
while stack and temperatures[stack[-1]] < temperatures[r]: # l < r
l = stack.pop()
result[l] = r - l
stack.append(r)
return result

· One min read
import heapq
from collections import Counter
from itertools import chain, islice


class Solution: # O(n) / O(n)
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
buckets = [[] for _ in nums]
for n, c in Counter(nums).items():
buckets[-c].append(n)
return list(islice(chain.from_iterable(buckets), k))


class Solution1: # O(nlogn) / O(n)
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
heap = []
for n, c in Counter(nums).items():
heapq.heappush(heap, (-c, n))
return [heapq.heappop(heap)[1] for _ in range(k)]


class Solution2: # O(nlogn) / O(n)
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
heap = []
for n, c in Counter(nums).items():
heapq.heappush(heap, (-c, n))
return [x[1] for x in heapq.nsmallest(k, heap)]


class Solution3: # O(nlogn) / O(n)
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
return [n for n, _ in Counter(nums).most_common(k)]

· One min read
from typing import Optional


# 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 Solution1:
def largestValues(self, root: Optional[TreeNode]) -> list[int]:
result, nodes = [], [x for x in [root] if x]
while nodes:
result.append(max(x.val for x in nodes))
_next = []
_next.extend([x.left for x in nodes if x.left])
_next.extend([x.right for x in nodes if x.right])
nodes = _next
return result


class Solution:
# https://leetcode.com/problems/find-largest-value-in-each-tree-row/solutions/99000/python-bfs/
def largestValues(self, root: Optional[TreeNode]) -> list[int]:
result, nodes = [], [root]
while any(nodes):
result.append(max(x.val for x in nodes))
nodes = [x for n in nodes for x in [n.left, n.right] if x]
return result

· One min read
class SolutionR1:  # O(n*n) / O(n) ? str slice
def numDecodings(self, s: str) -> int:
m = {'': 1}

def recur(s=s):
if s in m:
return m[s]
m[s] = 0
if s[0] != '0':
m[s] += recur(s[1:])
if 10 <= int(s[:2]) <= 26:
m[s] += recur(s[2:])
return m[s]

return recur()


class SolutionR2: # O(n) / O(n)
def numDecodings(self, s: str) -> int:
m = {len(s): 1}

def recur(i=0):
if i in m:
return m[i]
m[i] = 0
if s[i] != '0':
m[i] += recur(i + 1)
if 10 <= int(s[i : i + 2]) <= 26:
m[i] += recur(i + 2)
return m[i]

return recur()


class Solution1: # O(n) / O(n)
def numDecodings(self, s: str) -> int:
dp = [0] * (len(s) + 1)
dp[0], dp[1] = 1, int(s[0] != '0')
for i in range(len(s) - 1):
if s[i + 1] != '0':
dp[i + 2] += dp[i + 1]
if 10 <= int(s[i : i + 2]) <= 26:
dp[i + 2] += dp[i]
return dp[-1]


class Solution2: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b = 1, int(s[0] != '0')
for i in range(len(s) - 1):
c = 0
if s[i + 1] != '0':
c += b
if 10 <= int(s[i : i + 2]) <= 26:
c += a
a, b = b, c
return b


class Solution3: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b = 1, int(s[0] != '0')
for i in range(len(s) - 1):
one, two = s[i + 1] != '0', 10 <= int(s[i : i + 2]) <= 26
a, b = b, b * one + a * two
return b


class Solution4: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b, p = 0, int(bool(s)), ''
for c in s:
tmp = b
if c == '0':
b = 0
if 10 <= int(p + c) <= 26:
b += a
a, p = tmp, c
return b


class Solution: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b, p = 0, int(bool(s)), ''
for c in s:
one, two = c != '0', 10 <= int(p + c) <= 26
a, b, p = b, b * one + a * two, c
return b

· One min read
'''
f(k) = (n/k)^k
-> ln(f(k)) = k ln(n/k)
-> d ln(f(k)) / d k = ln(n/k) + k(-1/k)
-> d f(k) / f(k) d k = ln(n/k) - 1
-> f′(k) = f(k) (ln(n/k) - 1)
find the maximum:
f′(k) = 0
-> ln(n/k) = 1
-> n/k = e, 2 or 3
'''


import math


class Solution1: # O(n)
# https://leetcode.com/problems/integer-break/solutions/4136961/easy-olog-n-time-with-o1-space-complexity-easy-math-solution-with-proofs/
def integerBreak(self, n: int) -> int:
if n < 4:
return n - 1
result = 1
while n > 4:
result *= 3
n -= 3
return n * result


class Solution2: # O(log(n))
def integerBreak(self, n: int) -> int:
if n < 4:
return n - 1
return 2 ** (-n % 3) * 3 ** ((n - 4) // 3 + (n - 1) % 3)


class Solution: # O(1)
def integerBreak(self, n: int) -> int:
if n < 4:
return n - 1
return int(math.pow(2, -n % 3) * math.pow(3, (n - 4) // 3 + (n - 1) % 3))

· One min read
class Solution1:
def lengthOfLongestSubstring(self, s: str) -> int:
result, chars = 0, set()
for j, c in enumerate(s):
while c in chars:
i = j - len(chars)
chars.remove(s[i])
chars.add(c)
result = max(result, len(chars))
return result


class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
result, i, chars = 0, 0, {}
for j, char in enumerate(s):
i = max(i, chars.get(char, -1) + 1)
chars[char] = j
result = max(result, j - i + 1)
return result

· One min read
class Solution1:
def rotate(self, nums: list[int], k: int) -> None:
if len(nums) > 1:
k %= len(nums)
nums[:-k], nums[-k:] = nums[-k:], nums[:-k]


class Solution:
def rotate(self, nums: list[int], k: int) -> None:
def reverse(start, stop):
for i in range((stop - start) // 2):
l, r = start + i, stop - 1 - i
nums[l], nums[r] = nums[r], nums[l]

k %= len(nums)
reverse(0, len(nums) - k)
reverse(len(nums) - k, len(nums))
reverse(0, len(nums))

· One min read
from ..notes import gcd


class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next


class Solution:
def insertGreatestCommonDivisors(self, head: ListNode) -> ListNode:
node = head
while node.next:
node.next = ListNode(val=gcd(node.val, node.next.val), next=node.next)
node = node.next.next
return head

· One min read
class Solution1:
def getSum(self, a: int, b: int) -> int:
MASK, xor, carry = 1023, a ^ b, (a & b) << 1
if carry & MASK:
return self.getSum(xor, carry)
return xor & MASK if carry else xor


class Solution:
def getSum(self, a: int, b: int) -> int:
MASK = 1023
while b & MASK:
a, b = a ^ b, (a & b) << 1
return a & MASK if b else a

· One min read
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
for i in range(len(text1)):
for j in range(len(text2)):
if text1[i] == text2[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
return dp[-1][-1]

· One min read
class Solution:
def threeSum(self, nums: list[int]):
result = set()
zero, neg, pos = counters = {}, {}, {}
for num in nums:
counter = counters[(num > 0) + (num != 0)]
counter[num] = counter.get(num, 0) + 1
# 0,0,0
if zero.get(0, 0) >= 3:
result.add((0, 0, 0))
# -,+,?
for n in neg:
for p in pos:
target: int = -(n + p)
counter = counters[(target > 0) + (target != 0)]
if target in counter:
triplet = tuple(sorted([n, p, target]))
if target in (n, p): # duplicate
if counter[target] >= 2:
result.add(triplet)
else:
result.add(triplet)
return result

· One min read
class Solution:
def search(self, nums: list[int], target: int) -> int:
lo, hi = 0, len(nums)
target_is_rotated = target < nums[0]
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
mid_is_rotated = nums[mid] < nums[0]
if (mid_is_rotated, target_is_rotated) == (True, False): # [t] [m]
hi = mid
elif (mid_is_rotated, target_is_rotated) == (False, True): # [m] [t]
lo = mid + 1
# same side
elif nums[mid] > target:
hi = mid
else:
lo = mid + 1
return -1


class Solution1:
def search(self, nums: list[int], target: int) -> int:
# https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/14435/clever-idea-making-it-simple/
lo, hi = 0, len(nums)
target_is_rotated = target < nums[0]
inf = (-1) ** target_is_rotated * float('inf')
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
mid_is_rotated = nums[mid] < nums[0]
if (nums[mid], inf)[mid_is_rotated != target_is_rotated] > target:
hi = mid
else:
lo = mid + 1
return -1

· One min read
class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
M, N = len(matrix), len(matrix[0])
lo, hi = 0, M * N
while lo < hi:
mid = (lo + hi) // 2
row, col = divmod(mid, N)
if matrix[row][col] == target:
return True
if matrix[row][col] > target:
hi = mid
else:
lo = mid + 1
return False


class Solution1:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
M, N = len(matrix), len(matrix[0])
lo, hi = 0, M
while lo < hi:
mid = (lo + hi) // 2
if matrix[mid][0] == target:
return True
if matrix[mid][0] > target:
hi = mid
else:
lo = mid + 1
row = matrix[lo - 1]
lo, hi = 0, N
while lo < hi:
mid = (lo + hi) // 2
if row[mid] == target:
return True
if row[mid] > target:
hi = mid
else:
lo = mid + 1
return False

· One min read
class Solution:
def letterCombinations(self, digits: str):
LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
letters = [LETTERS[i] for i in map(int, digits)]

def backtracking(comb: str, i: int):
if i == len(digits):
yield comb
return
for char in letters[i]:
yield from backtracking(comb + char, i + 1)

yield from backtracking('', 0) if digits else []


class Solution1:
def letterCombinations(self, digits: str) -> list[str]:
result = []

def backtracking(comb: str, letters: list[str]):
if not letters:
return result.append(comb)
for char in letters[0]:
backtracking(comb + char, letters[1:])

LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
backtracking('', [LETTERS[i] for i in map(int, digits)])
return result if digits else []


class Solution2:
def letterCombinations(self, digits: str) -> list[str]:
LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
letters = [LETTERS[i] for i in map(int, digits)]
result = []

def backtracking(comb: str, i: int):
if i == len(digits):
return result.append(comb)
for char in letters[i]:
backtracking(comb + char, i + 1)

backtracking('', 0)
return result if digits else []

· One min read
from bisect import bisect_left


class SolutionDp: # O(n*n) / O(n)
def lengthOfLIS(self, nums: list[int]) -> int:
result, dp = 1, [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
result = max(result, dp[i])
return result


class SolutionBs: # O(n*log(n)) / O(n)
def lengthOfLIS(self, nums: list[int]) -> int:
result, dp = 0, [0] * len(nums)
for num in nums:
lo = bisect_left(dp, num, hi=result)
result, dp[lo] = max(result, lo + 1), num
return result


class SolutionBsLessSpace: # O(n*log(n)) / O(n)
def lengthOfLIS(self, nums: list[int]) -> int:
result, dp = 0, []
for i in range(len(nums)):
if dp and nums[i] <= dp[-1]:
dp[bisect_left(dp, nums[i])] = nums[i]
else:
result += 1
dp.append(nums[i])
return result


class SolutionBsInPlace: # O(n*log(n)) / O(1)
def lengthOfLIS(self, nums: list[int]) -> int:
result = 0
for i in range(len(nums)):
lo = bisect_left(nums, nums[i], hi=result)
result, nums[lo] = max(result, lo + 1), nums[i]
return result

· One min read
class Solution:
def asteroidCollision(self, asteroids: list[int]) -> list[int]:
s: list[int] = []
for a in asteroids:
s.append(a)
while len(s) > 1 and s[-2] > 0 > s[-1]:
if s[-2] == -s[-1]:
s.pop()
elif s[-2] < -s[-1]:
s[-2] = s[-1]
s.pop()
return s

· One min read
from typing import Optional


class Node:
def __init__(
self,
value=0,
key=0, # for eviction
left: Optional['Node'] = None,
right: Optional['Node'] = None,
):
self.key = key
self.value = value
self.left = left
self.right = right

def append(self, node: 'Node'):
node.left = self
node.right = self.right
if self.right:
self.right.left = node
self.right = node

def isolate(self):
if self.left:
self.left.right = self.right
if self.right:
self.right.left = self.left


class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dict: dict[int, Node] = {}
self.fresh = Node()
self.stale = Node()
self.fresh.right = self.stale
self.stale.left = self.fresh
self.amount = 0

def get(self, key: int) -> int:
node = self.dict.get(key, Node(-1))
if key in self.dict:
node.isolate()
self.fresh.append(node)
return node.value

def put(self, key: int, value: int) -> None:
if key in self.dict:
self.dict[key].isolate()
else:
if self.amount == self.capacity:
evicted = self.stale.left
if evicted:
evicted.isolate()
self.dict.pop(evicted.key)
else:
self.amount += 1
node = self.dict.setdefault(key, Node(key=key))
self.fresh.append(node)
node.value = value

· One min read
class SnapshotArray:
def __init__(self, length: int):
self._array: list[list[tuple[int, int]]] = [[(-1, 0)] for _ in range(length)]
self._snap_id = -1

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

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

@staticmethod
def bs_r(a, t):
l, r = 0, len(a)
while l < r:
m = (l + r) // 2
if a[m] > t:
r = m
else:
l = m + 1
return l

def get(self, index: int, snap_id: int) -> int:
low = self.bs_r(self._array[index], (snap_id,))
return self._array[index][low - 1][1]

· One min read
class Solution1:
def minFlips(self, a: int, b: int, c: int) -> int:
def flip_last_bits(numbers: tuple[int, ...]):
a, b, c = (n & 1 for n in numbers)
return 2 if (a + b, c) == (2, 0) else int(a + b + c == 1)

result, numbers = 0, (a, b, c)
while any(numbers):
result += flip_last_bits(numbers)
numbers = tuple(n >> 1 for n in numbers)
return result


class Solution2:
def minFlips(self, a: int, b: int, c: int) -> int:
def count(n):
return bin(n).count('1')

return count((a | b) ^ c) + count(a & b & ~c)

· One min read
from ..notes import Uf


class Solution:
# https://leetcode.com/problems/number-of-provinces/solutions/923039/union-find-with-union-by-ranks-and-path-compression/
def findCircleNum(self, isConnected: list[list[int]]) -> int:
uf = Uf(list(range(len(isConnected))))
for i in range(len(isConnected)):
for j in range(i + 1, len(isConnected)):
if isConnected[i][j]:
uf.union(i, j)
return len(set(uf.find(x) for x in range(len(isConnected))))

· One min read
from collections import deque
from heapq import heappop, heappush
from itertools import product
from sys import maxsize

cellT = tuple[int, int]
countT = int


class Solution1:
# [BFS] Runtime 1349 ms Beats 5.1%
def shortestPathBinaryMatrix(self, grid: list[list[int]]):
cellsT = set[cellT]

N = len(grid)
dummy_start_cell = (-1, -1)
bottom_right_cell = (N - 1, N - 1)

def find_adjacents(curr_row: int, curr_col: int):
def is_valid(cand_cell: cellT):
cand_row, cand_col = cand_cell
return (
0 <= cand_row < N
and 0 <= cand_col < N
and grid[cand_row][cand_col] == 0
)

cand_cells = (
(curr_row + row_offset, curr_col + col_offset)
for row_offset, col_offset in product(range(-1, 2), repeat=2)
)
return filter(is_valid, cand_cells)

queue: deque[cellsT] = deque([{dummy_start_cell}])
visiteds: cellsT = set()
count: countT = 1
while queue:
next_: cellsT = set()
q: cellsT = queue.popleft()
for cell in q:
visiteds.add(cell)
for adjacent in find_adjacents(*cell):
if adjacent in visiteds:
continue
if adjacent == bottom_right_cell:
return count
next_.add(adjacent)
if next_:
queue.append(next_)
count += 1
return -1


class Solution2:
# [dijkstra] Runtime 995 ms Beats 6.89%
def shortestPathBinaryMatrix(self, grid: list[list[int]]):
N = len(grid)
dummy_start_cell = (-1, -1)
bottom_right_cell = (N - 1, N - 1)

def find_adjacents(curr_row: int, curr_col: int):
def is_valid(cand_cell: cellT):
cand_row, cand_col = cand_cell
return (
0 <= cand_row < N
and 0 <= cand_col < N
and grid[cand_row][cand_col] == 0
)

cand_cells = (
(curr_row + row_offset, curr_col + col_offset)
for row_offset, col_offset in product(range(-1, 2), repeat=2)
)
return filter(is_valid, cand_cells)

heap: list[tuple[countT, cellT]] = [(0, dummy_start_cell)]
visiteds: set[cellT] = set()
while heap:
cost, vertex = heappop(heap)
if vertex == bottom_right_cell:
return cost
for new_vertex in find_adjacents(*vertex):
if new_vertex in visiteds:
continue
visiteds.add(new_vertex)
new_cost = cost + 1
heappush(heap, (new_cost, new_vertex))
return -1


class Solution3:
# [A*] Runtime 513 ms Beats 97.17%
def shortestPathBinaryMatrix(self, grid: list[list[int]]):
N = len(grid)
dummy_start_cell = (-1, -1)
bottom_right_cell = (N - 1, N - 1)

def find_adjacents(curr_row: int, curr_col: int):
def is_valid(cand_cell: cellT):
cand_row, cand_col = cand_cell
return (
0 <= cand_row < N
and 0 <= cand_col < N
and grid[cand_row][cand_col] == 0
)

cand_cells = (
(curr_row + row_offset, curr_col + col_offset)
for row_offset, col_offset in product(range(-1, 2), repeat=2)
)
return filter(is_valid, cand_cells)

def heuristic(cell_row: int, cell_col: int):
return max(abs(N - 1 - cell_row), abs(N - cell_col))

heap: list[tuple[countT, countT, cellT]] = [(-maxsize, 0, dummy_start_cell)]
costs: dict[cellT, countT] = {}
while heap:
estimate, cost, vertex = heappop(heap)
if vertex == bottom_right_cell:
return cost
for new_vertex in find_adjacents(*vertex):
new_cost = cost + 1
if costs.get(new_vertex, maxsize) > new_cost:
costs[new_vertex] = new_cost
new_estimate = new_cost + heuristic(*new_vertex)
heappush(heap, (new_estimate, new_cost, new_vertex))
return -1

· One min read
from collections import defaultdict


class UndergroundSystem:
def __init__(self):
checkInStationNameT = checkOutStationNameT = str
checkInTimeT = travelTimeT = int
idT = countT = int
self.check_in: dict[idT, tuple[checkInTimeT, checkInStationNameT]] = {}
self.time: defaultdict[
tuple[checkInStationNameT, checkOutStationNameT], tuple[travelTimeT, countT]
] = defaultdict(lambda: (0, 0))

def checkIn(self, id: int, stationName: str, t: int) -> None:
self.check_in[id] = (t, stationName)

def checkOut(self, id: int, stationName: str, t: int) -> None:
check_in_time, check_in_station_name = self.check_in.pop(id)
_key = check_in_station_name, stationName
_travel_time, _count = self.time[_key]
self.time[_key] = _travel_time + (t - check_in_time), _count + 1

def getAverageTime(self, startStation: str, endStation: str) -> float:
_key = startStation, endStation
travel_time, count = self.time[_key]
return travel_time / count

· One min read
from math import isqrt


class Solution:
def bulbSwitch(self, n: int) -> int:
'''
-> find the amount number of intergers that have odd number of factors
-> only the square numbers have odd number of factors
-> find the max number that number's square <= n
'''
for i in range(n):
if (i + 1) ** 2 > n:
return i
return n


class Solution0:
def bulbSwitch(self, n: int) -> int:
return int(n**0.5)


class Solution2:
def bulbSwitch(self, n: int) -> int:
return isqrt(n)

· One min read
class Solution:
def mincostTickets(self, days: list[int], costs: list[int]) -> int:
day_costs = dict(zip([1, 7, 30], costs))
N = days[-1]
dp = [0] * (N + 1)
travel = set(days)
for i in range(1, N + 1):
if i in travel:
dp[i] = min(dp[max(0, i - d)] + c for d, c in day_costs.items())
else:
dp[i] = dp[i - 1]
return dp[-1]

· One min read
class Solution1:
def simplifyPath(self, path: str) -> str:
stack = []
for p in path.split('/'):
if p == '..':
stack.pop() if stack else None
elif p and p != '.':
stack.append(p)
return '/' + '/'.join(stack)


class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for p in path.split('/'):
d = {'': stack, '.': stack, '..': stack[:-1]}
stack = d.get(p, stack + [p])
return '/' + '/'.join(stack)

· One min read
from collections import deque


# Definition for a Node.
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []


class Solution1:
def cloneGraph(self, node: 'Node') -> 'Node':
visited = {}

def dfs(node):
if node in visited:
return visited[node]
visited[node] = Node(val=node.val)
# note: create new node first, then update the neighbors
visited[node].neighbors = [dfs(x) for x in node.neighbors]
return visited[node]

return node and dfs(node)


class Solution2:
def cloneGraph(self, node: 'Node') -> 'Node':
def bfs(node):
visited = {node: Node(val=node.val)}
queue = [node]
while queue:
next_ = []
for q in queue:
for n in q.neighbors:
if n not in visited:
visited[n] = Node(val=n.val)
next_.append(n)
visited[q].neighbors.append(visited[n])
queue = next_
return visited[node]

return node and bfs(node)


class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
def bfs(node):
visited = {node: Node(val=node.val)}
queue = deque([node])
while queue:
q = queue.popleft()
for n in q.neighbors:
if n not in visited:
visited[n] = Node(val=n.val)
queue.append(n)
visited[q].neighbors.append(visited[n])
return visited[node]

return node and bfs(node)

· One min read
from typing import Optional


class Node:
def __init__(self, is_end: bool = False):
self.is_end = is_end
self.children: dict[str, Node] = {}

def __repr__(self):
return f'''{'! ' if self.is_end else ''}{self.children}'''


class Trie:
def __init__(self):
self.root = Node()

def insert(self, word: str) -> None:
node = self.root
for c in word:
node.children[c] = node.children.get(c, Node())
node = node.children[c]
node.is_end = True

def _last_node_same_with(self, word: str) -> Optional[Node]:
node = self.root
for c in word:
if c not in node.children:
return
node = node.children[c]
return node

def search(self, word: str) -> bool:
node = self._last_node_same_with(word)
return bool(node) and node.is_end

def startsWith(self, word: str) -> bool:
node = self._last_node_same_with(word)
return bool(node)

· One min read
from typing import Optional


class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next


class Solution1:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
l = r = d = ListNode(next=head)
for _ in range(n - 1):
r = r.next
while r.next and r.next.next is not None:
l, r = l.next, r.next
l.next = l.next.next
return d.next


class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
l = r = head
for _ in range(n):
r = r.next
if r is None:
return head.next
while r.next:
l, r = l.next, r.next
l.next = l.next.next
return head

· One min read
class Solution:
def multiply(self, num1: str, num2: str) -> str:
ZERO = '0'
if ZERO in (num1, num2):
return ZERO

def ord_(x):
return ord(x) - ord(ZERO)

def chr_(x):
return chr(x + ord(ZERO))

L1, L2 = len(num1) - 1, len(num2) - 1
result = []
carry = 0
i = 0
while (i <= L1 + L2) or carry:
j = max(0, i - L2)
while j <= min(i, L1):
n1, n2 = num1[L1 - j], num2[L2 - i + j]
carry += ord_(n1) * ord_(n2)
j += 1
result.append(chr_(carry % 10))
carry //= 10
i += 1
return ''.join(result)[::-1]

· One min read
class Solution:
def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
if not matrix or not matrix[0]:
return []
result = []
t, b, l, r = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
while t <= b and l <= r:
result.extend([matrix[t][x] for x in range(l, r + 1)])
result.extend([matrix[x][r] for x in range(t + 1, b + 1)])
if t < b and l < r:
result.extend([matrix[b][x] for x in range(r - 1, l, -1)])
result.extend([matrix[x][l] for x in range(b, t, -1)])
t, b, l, r = t + 1, b - 1, l + 1, r - 1
return result

· One min read
import heapq
from collections import Counter


class Solution1:
def topKFrequent(self, words: list[str], k: int) -> list[str]:
c = Counter(words)
return [x for x in sorted(c, key=lambda key: (-c[key], key))][:k]


class Solution:
def topKFrequent(self, words: list[str], k: int) -> list[str]:
c = Counter(words)
return heapq.nsmallest(k, c, key=lambda key: (-c[key], key))

· One min read
class Solution:  # O(n) / O(n)
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
def characterReplacement(self, s: str, k: int) -> int:
c = {} # counter
mf = 0 # max_freq
i = 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if not ((j - i + 1) - mf <= k): # shift right
c[s[i]] -= 1
i += 1
return len(s) - i # length


class Solution2: # O(n) / O(n)
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
def characterReplacement(self, s: str, k: int) -> int:
c = {}
mf, i = 0, 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if i - mf >= k:
c[s[j - i]] -= 1
else:
i += 1 # update when more
return i


class SolutionBS: # O(log(n)) / O(n)
# TODO: review
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/2805777
def characterReplacement(self, s: str, k: int) -> int:
def too_long(length: int):
c = {}
mf, i = 0, 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if length - mf <= k:
return False
if j - i + 1 > length:
c[s[i]] -= 1
i += 1
return True

l, r = 0, len(s)
while l < r:
m = (l + r) // 2
l, r = (l, m) if too_long(length=m + 1) else (m + 1, r)
return (l - 1) + 1

· One min read
class Solution:
def computeArea(
self,
ax1: int,
ay1: int,
ax2: int,
ay2: int,
bx1: int,
by1: int,
bx2: int,
by2: int,
) -> int:
(ax1, ax2), (ay1, ay2), (bx1, bx2), (by1, by2) = map(
sorted,
((ax1, ax2), (ay1, ay2), (bx1, bx2), (by1, by2)),
)
return sum(
(
(ax2 - ax1) * (ay2 - ay1),
(bx2 - bx1) * (by2 - by1),
-(
max(0, min(ax2, bx2) - max(ax1, bx1))
* max(0, min(ay2, by2) - max(ay1, by1))
),
)
)

· One min read
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None


class Solution:
def lowestCommonAncestor(self, root, p, q):
if root.val > max(p.val, q.val):
return self.lowestCommonAncestor(root.left, p, q)
if root.val < min(p.val, q.val):
return self.lowestCommonAncestor(root.right, p, q)
return root

· One min read
# 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 isValidBST(self, root, lo=float('-inf'), hi=float('inf')) -> bool:
'''
[5,4,6,null,null,3,7] => false
'''
return (not root) or all(
[
lo < root.val < hi,
self.isValidBST(root.left, lo, root.val),
self.isValidBST(root.right, root.val, hi),
]
)

· One min read
from functools import reduce


# 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 levelOrder(self, root) -> list[list[int]]:
result, q = [], [root]
while True:
q = [x for x in q if x]
v = [x.val for x in q]
if not v:
break
result.append(v)
q = reduce(lambda a, b: a + [b.left, b.right], q, [])
return result

· One min read
class Solution:
def detectCycle(self, head):
'''
.___a___.___C-b___.
(_________) -> C: cycle
b

slow: a+C-b + xC
fast: a+C-b + yC

2 slow = fast
=> a+C-b = (y-2x)C
=> a = (y-2x-1)C+b

.___(y-2x-1)C+b___.___C-b___.
(_________)
b

=> a mod C = b mod C
'''
l = r = head
while r and r.next:
l, r = l.next, r.next.next
if l is r:
break
else:
return

while head is not r:
head, r = head.next, r.next
return head