Techniques
String
Longest Common Subsequence
Sample code
# ref: https://leetcode.com/problems/longest-common-subsequence/description/
from functools import cache
class Solution1:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
'''
A top-down recursive approach
* Time complexity : O(M⋅N^2)
* Space complexity : O(M⋅N)
'''
@cache
def match(p1, p2):
if p1 == len(text1) or p2 == len(text2):
return 0
# Exclude text1[p1] in the solution.
option_1 = match(p1 + 1, p2)
# Include text1[p1] in the solution, as long as
# a match for it in text2 at or after p2 exists.
first_occurence = text2.find(text1[p1], p2)
option_2 = 0
if first_occurence != -1:
option_2 = 1 + match(p1 + 1, first_occurence + 1)
return max(option_1, option_2)
return memo_solve(0, 0)
from functools import cache
class Solution2:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
'''
An optimized top-down recursive approach
* Time complexity : O(M⋅N)
* Space complexity : O(M⋅N)
'''
@cache
def memo_solve(p1, p2):
# Base case: If either string is now empty, we can't match
# up anymore characters.
if p1 == len(text1) or p2 == len(text2):
return 0
# Recursive case 1.
if text1[p1] == text2[p2]:
return 1 + memo_solve(p1 + 1, p2 + 1)
# Recursive case 2.
else:
return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
return memo_solve(0, 0)
class Solution3:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
'''
DP approach
* Time complexity : O(M⋅N)
* Space complexity : O(M⋅N)
'''
# Make a grid of 0's with len(text2) + 1 columns
# and len(text1) + 1 rows.
dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
# Iterate up each column, starting from the last one.
for col in reversed(range(len(text2))):
for row in reversed(range(len(text1))):
# If the corresponding characters for this cell are the same...
if text2[col] == text1[row]:
dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]
# Otherwise they must be different...
else:
dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])
# The original problem's answer is in dp_grid[0][0]. Return it.
return dp_grid[0][0]
class Solution4:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
'''
Space optimized DP approach
* Time complexity : O(M⋅N)
* Space complexity : O(min(M,N))
'''
# If text1 doesn't reference the shortest string, swap them.
if len(text2) < len(text1):
text1, text2 = text2, text1
# The previous column starts with all 0's and like before is 1
# more than the length of the first word.
previous = [0] * (len(text1) + 1)
# Iterate up each column, starting from the last one.
for col in reversed(range(len(text2))):
# Create a new array to represent the current column.
current = [0] * (len(text1) + 1)
for row in reversed(range(len(text1))):
if text2[col] == text1[row]:
current[row] = 1 + previous[row + 1]
else:
current[row] = max(previous[row], current[row + 1])
# The current column becomes the previous one.
previous = current
# The original problem's answer is in previous[0]. Return it.
return previous[0]
Linked List
Swap by pair
# recursive
class Solution(object):
def swapPairs(self, head: ListNode) -> ListNode:
"""
:type head: ListNode
:rtype: ListNode
"""
# If the list has no node or has only one node left.
if not head or not head.next:
return head
# Nodes to be swapped
first_node = head
second_node = head.next
# Swapping
first_node.next = self.swapPairs(second_node.next)
second_node.next = first_node
# Now the head is the second node
return second_node
# iterative
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
"""
:type head: ListNode
:rtype: ListNode
"""
# Dummy node acts as the prevNode for the head node
# of the list and hence stores pointer to the head node.
dummy = ListNode(-1)
dummy.next = head
prev_node = dummy
while head and head.next:
# Nodes to be swapped
first_node = head
second_node = head.next
# Swapping
prev_node.next = second_node
first_node.next = second_node.next
second_node.next = first_node
# Reinitializing the head and prev_node for next swap
prev_node = first_node
head = first_node.next
# Return the new head node.
return dummy.next
Interval
Minimum Removal for non-overlapping intervals
Both sorting by start or end time is feasible, but sorting by start time seems to be slower.
Sample code
# sort by end time
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
temp = sorted(intervals, key = lambda x: x[1])
ans = 0
k = -inf
for x, y in temp:
if x >= k:
k = y
else:
ans += 1
return ans
# sort by start time
class Solution:
def eraseOverlapIntervals (self, intervals: List[List[int]]) -> int:
intervals.sort()
prev, i, ans = 0, 1, 0
while (i < len(intervals)):
if (intervals[i][0] < intervals[prev][1]):
ans += 1
if (intervals[i][1] < intervals[prev][1]): prev = i
else: prev = i
i += 1
return ans
Generate Palindrome Number With Length Smaller Than n
Sample code
class Solution:
def generate_palindrome(self, n: int) -> int:
left = 1
while len(str(left)) <= n//2+1:
right = left * 10
# op = 0 indicates enumerating even-length palindromes
# op = 1 indicates enumerating odd-length palindromes
for op in [1, 0]:
if len(str(left))*2-op > n:
continue
for i in range(left, right):
combined = i
x = i // 10 if op == 1 else i
while x:
combined = combined * 10 + x % 10
x //= 10
print(combined)
left = right
Stack
Using monotonic stack to track next higher value
# https://leetcode.com/problems/daily-temperatures/
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
hottest = 0
answer = [0] * n
for curr_day in range(n - 1, -1, -1):
current_temp = temperatures[curr_day]
if current_temp >= hottest:
hottest = current_temp
continue
days = 1
while temperatures[curr_day + days] <= current_temp:
# Use information from answer to search for the next warmer day
days += answer[curr_day + days]
answer[curr_day] = days
return answer
Bit manipulation
Adding two binary string
Sample code
# ref: https://leetcode.com/problems/add-binary/description/
class Solution:
def addBinary(self, a, b) -> str:
x, y = int(a, 2), int(b, 2)
while y:
answer = x ^ y # This results in a sum of two binaries without taking carry into account.
carry = (x & y) << 1 # This gets the carry of current summationㄠ
x, y = answer, carry
return bin(x)[2:]
BST
Validating BST
Sample code
# Recurseive with range
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def validate(node, low=-math.inf, high=math.inf):
# Empty trees are valid BSTs.
if not node:
return True
# The current node's value must be between low and high.
if node.val <= low or node.val >= high:
return False
# The left and right subtree must also be valid.
return validate(node.right, node.val, high) and validate(
node.left, low, node.val
)
return validate(root)
# Recursive inorder comparison
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def inorder(root):
if not root:
return True
if not inorder(root.left):
return False
if root.val <= self.prev:
return False
self.prev = root.val
return inorder(root.right)
self.prev = -math.inf
return inorder(root)
# Iterative with range
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if not root:
return True
stack = [(root, -math.inf, math.inf)]
while stack:
root, lower, upper = stack.pop()
if not root:
continue
val = root.val
if val <= lower or val >= upper:
return False
stack.append((root.right, val, upper))
stack.append((root.left, lower, val))
return True
# Iterative inorder comparison
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack, prev = [], -math.inf
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
# If next element in inorder traversal
# is smaller than the previous one
# that's not BST.
if root.val <= prev:
return False
prev = root.val
root = root.right
return True
Find Inorder Successor
Sample code
class Solution:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
successor = None
while root:
if p.val >= root.val:
root = root.right
else:
successor = root
root = root.left
return successor
Math
Fast Exponentiation
Fast exponentiation, also known as exponentiation by squaring or binary exponentiation, is a technique for efficiently calculating large powers of a number.
Sample code
mod = 1_000_000_007
def quickmul(x: int, y: int) -> int:
ret, mul = 1, x
while y > 0:
if y % 2 == 1:
ret = ret * mul % mod
mul = mul * mul % mod
y //= 2
return ret
Random pick from list
Utlizes prefix sum combined with binary search to mock selection with weight from a given list.
from random import random
from bisect import bisect_right
class Solution:
def __init__(self, w: List[int]):
self.prop = [0]*len(w)
self.prop[0] = w[0]
for i in range(1, len(w)):
self.prop[i] = self.prop[i-1] + w[i]
total = sum(self.prop)
for i in range(len(self.prop)):
self.prop[i] /= total
def pickIndex(self) -> int:
p = random()
return bisect_right(self.prop, p)
GCD of Two Numbers
def gcd_iterative(x, y):
while y != 0:
x, y = y, x % y
return x
def gcd_recursive(a, b):
a, b = abs(a), abs(b) # Convert to positive numbers
if b == 0:
return a
return gcd_recursive(b, a % b)
Graph
Number of Connected Components in an Undirected Graph
# DFS
from collections import defaultdict
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
adjacents=defaultdict(list)
for x,y in edges:
adjacents[x].append(y)
adjacents[y].append(x)
visited=set()
count=0
for index in range(n):
if index not in visited:
self.dfsHelper(index, visited, adjacents)
count+=1
return count
def dfsHelper(self, index, visited, adjacents):
if index in visited:
return
visited.add(index)
for neighbor in adjacents[index]:
self.dfsHelper(neighbor, visited, adjacents)
## Union find
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.components = n
def find(self, A):
root = A
while root != self.parent[root]:
root = self.parent[root]
return root
def union(self, A, B):
root_A = self.find(A)
root_B = self.find(B)
if root_A == root_B:
return
self.parent[root_A] = root_B
self.components -= 1
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
unionFind = UnionFind(n)
for A, B in edges:
unionFind.union(A, B)
return unionFind.components