Don't memorize 200 problems — learn the patterns behind them. Solutions are in Python, with Big-O. Examples use classic, public problems (Two Sum, Binary Search, etc.).
Big-O describes how runtime grows as input size n grows. Lower is better.
| Big-O | Name | Example |
|---|---|---|
O(1) | constant | look up a dict/array index |
O(log n) | logarithmic | binary search |
O(n) | linear | one loop over the data |
O(n log n) | log-linear | good sorting (merge/quick) |
O(n²) | quadratic | nested loops |
O(2ⁿ) | exponential | naive recursion (avoid!) |
O(1) on hash maps/sets is relative to n — hashing a string key still costs O(m) for a length-m string.| Operation | Big-O |
|---|---|
| Add / remove at the end | O(1) amortized |
| Add / remove at arbitrary index | O(n) |
| Access / modify at index | O(1) |
| Check if element exists | O(n) |
| Two pointers / sliding window | O(n·k) (k = work per step) |
| Build a prefix sum | O(n) |
| Subarray sum from a prefix sum | O(1) |
| Operation | Big-O |
|---|---|
| Add / remove a character | O(n) |
| Access at index | O(1) |
| Concatenate two strings | O(n + m) |
| Create a substring | O(m) |
Build via "".join(list) | O(n) |
| Operation | Big-O |
|---|---|
| Add / remove with pointer at spot | O(1) (doubly linked) |
| Add / remove at arbitrary position | O(n) |
| Access at arbitrary position | O(n) |
| Reverse between i and j | O(j − i) |
| Detect a cycle (fast/slow) | O(n) |
| Operation | Big-O |
|---|---|
| Add / remove / look up a key | O(1) |
| Check if a value exists | O(n) |
| Iterate over keys / values | O(n) |
| Operation | Big-O |
|---|---|
| Push / pop / peek (stack) | O(1) |
| Enqueue / dequeue / peek (queue) | O(1) |
| Check if element exists | O(n) |
| Operation | Big-O |
|---|---|
| Binary tree DFS / BFS | O(n·k) (k = work per node) |
| BST add / remove / search | O(log n) avg, O(n) worst (unbalanced) |
| Heap add / remove-min | O(log n) |
| Heap find-min | O(1) |
| Heap check if exists | O(n) |
| Binary search | O(log n) |
| Operation | Big-O |
|---|---|
| Sorting | O(n log n) |
| Graph DFS / BFS (time) | O(n·k + e) (n nodes, e edges) |
| Graph DFS / BFS (space) | O(n), or O(n + e) to store the graph |
| DP (time) | O(n·k) (n states, k work/state) |
| DP (space) | O(n) (n states) |
| Constraint on n | Likely target complexity | Think… |
|---|---|---|
n ≤ 10 | O(n!) / O(n²·n!) | backtracking, brute-force recursion |
10 < n ≤ 20 | O(2ⁿ) | subsets/subsequences (take / don't take) |
20 < n ≤ 100 | O(n³) | brute force with nested loops |
100 < n ≤ 1,000 | O(n²) | nested loops, often optimal here |
1,000 < n < 100,000 | O(n log n) or O(n) | sort, heap, hash map, two pointers, monotonic stack, binary search |
100,000 < n < 1,000,000 | O(n) | almost certainly a hash map |
n > 1,000,000 (or 10⁹+) | O(log n) / O(1) | binary search, math tricks, clever hashing |
O(n). Otherwise you usually can't beat O(log n). An O(n) solution can hide a constant factor of ~40 (e.g. looping the 26 letters → O(26n)). Don't be confidently wrong about optimality — "I think this is optimal, but it may be improvable" is the safe phrasing.seen set prevents revisiting nodes / cycles").directions array instead of writing 4 near-identical blocks; use helper functions.O(n)). This is why understanding beats memorizing.CONDITION / # do logic parts). This is the single highest-leverage thing to memorize for interviews.def fn(arr):
left = ans = 0
right = len(arr) - 1
while left < right:
# do logic with left and right
if CONDITION:
left += 1
else:
right -= 1
return ansdef fn(arr1, arr2):
i = j = ans = 0
while i < len(arr1) and j < len(arr2):
# do logic
if CONDITION:
i += 1
else:
j += 1
while i < len(arr1):
# do logic
i += 1
while j < len(arr2):
# do logic
j += 1
return ansdef fn(arr):
left = ans = curr = 0
for right in range(len(arr)):
# add arr[right] to curr
while WINDOW_CONDITION_BROKEN:
# remove arr[left] from curr
left += 1
# update ans
return ansclass Solution:
def fn(self, arr):
prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(prefix[-1] + arr[i])
return prefixCollect chars in a list, then "".join() — building a string with += in a loop is O(n²) in Python. (In JS, benchmarks show += is actually faster than .join().)
class Solution:
def fn(self, arr): # arr is a list of characters
ans = []
for c in arr:
ans.append(c)
return "".join(ans)class Solution:
def fn(self, head):
slow = head
fast = head
ans = 0
while fast and fast.next:
# do logic
slow = slow.next
fast = fast.next.next
return ansclass Solution:
def fn(self, head):
curr = head
prev = None
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prevPrefix-count with a hash map (e.g. "subarrays summing to k").
from collections import defaultdict
class Solution:
def fn(self, arr, k):
counts = defaultdict(int)
counts[0] = 1
ans = curr = 0
for num in arr:
# update curr (running value)
ans += counts[curr - k]
counts[curr] += 1
return ansSame idea maintains a monotonic queue. For monotonic decreasing, just flip > to <.
class Solution:
def fn(self, arr):
stack = []
ans = 0
for num in arr:
while stack and stack[-1] > num:
# do logic
stack.pop()
stack.append(num)
return ansclass Solution:
def dfs(self, root):
if not root:
return
ans = 0
# do logic
self.dfs(root.left)
self.dfs(root.right)
return ansclass Solution:
def dfs(self, root):
stack = [root]
ans = 0
while stack:
node = stack.pop()
# do logic
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ansfrom collections import deque
class Solution:
def fn(self, root):
queue = deque([root])
ans = 0
while queue:
current_length = len(queue)
# do logic for the current level
for _ in range(current_length):
node = queue.popleft()
# do logic
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return ansAssume nodes 0..n-1 and an adjacency-list graph. Convert other inputs to this form first.
def fn(graph):
def dfs(self, node):
ans = 0
# do logic
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
ans += dfs(neighbor)
return ans
seen = {START_NODE}
return dfs(START_NODE)def fn(graph):
stack = [START_NODE]
seen = {START_NODE}
ans = 0
while stack:
node = stack.pop()
# do logic
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
stack.append(neighbor)
return ansfrom collections import deque
def fn(graph):
queue = deque([START_NODE])
seen = {START_NODE}
ans = 0
while queue:
node = queue.popleft()
# do logic
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
return ansimport heapq
def fn(arr, k):
heap = []
for num in arr:
# push according to the problem's criteria
heapq.heappush(heap, (CRITERIA, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for num in heap]class Solution:
def fn(self, arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
# do something
return mid
if arr[mid] > target:
right = mid - 1
else:
left = mid + 1
# left is the insertion point
return leftclass Solution:
def fn(self, arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] >= target:
right = mid
else:
left = mid + 1
return leftclass Solution:
def fn(self, arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] > target:
right = mid
else:
left = mid + 1
return leftdef fn(arr):
def check(self, x):
# returns True/False depending on the problem
return BOOLEAN
left = MINIMUM_POSSIBLE_ANSWER
right = MAXIMUM_POSSIBLE_ANSWER
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return leftdef fn(arr):
def check(self, x):
return BOOLEAN
left = MINIMUM_POSSIBLE_ANSWER
right = MAXIMUM_POSSIBLE_ANSWER
while left <= right:
mid = (left + right) // 2
if check(mid):
left = mid + 1
else:
right = mid - 1
return rightdef backtrack(curr, OTHER_ARGUMENTS):
if BASE_CASE:
# modify the answer
return
ans = 0
for ITERATE_OVER_INPUT:
# modify the current state
ans += backtrack(curr, OTHER_ARGUMENTS)
# undo the modification of the current state
return ansdef fn(arr):
def dp(self, STATE):
if BASE_CASE:
return 0
if STATE in memo:
return memo[STATE]
ans = RECURRENCE_RELATION(STATE)
memo[STATE] = ans
return ans
memo = {}
return dp(STATE_FOR_WHOLE_INPUT)dp array sized by your state variables (so dp(4,6) becomes dp[4][6]); (2) set the same base cases (often just init to 0); (3) write for-loops over the state variables, iterating from the base cases toward the answer state; (4) copy the recurrence in, turning every dp(...) call into dp[...] array access; (5) return dp[...] instead of dp(...).class TrieNode: # a class is only needed if you store data per node
def __init__(self):
self.data = None # store data at nodes if you wish
self.children = {}
def fn(words):
root = TrieNode()
for word in words:
curr = root
for c in word:
if c not in curr.children:
curr.children[c] = TrieNode()
curr = curr.children[c]
# curr now holds a full word — give it an attribute if you want
return rootfrom math import inf
from heapq import heappop, heappush
class Solution:
def fn(self, graph, source, n):
distances = [inf] * n
distances[source] = 0
heap = [(0, source)]
while heap:
curr_dist, node = heappop(heap)
if curr_dist > distances[node]:
continue
for nei, weight in graph[node]:
dist = curr_dist + weight
if dist < distances[nei]:
distances[nei] = dist
heappush(heap, (dist, nei))
return distancesPattern: hash set — for each number, check if target − number was already seen. O(n) time.
def two_number_sum(nums, target):
seen = set()
for n in nums:
complement = target - n
if complement in seen:
return [complement, n]
seen.add(n)
return []
# two_number_sum([3, 5, -4, 8, 11, 1, -1, 6], 10) -> [11, -1]Pattern: two pointers — walk the main array, advance the second pointer on each match. O(n).
def is_valid_subsequence(array, sequence):
i = 0
for value in array:
if i == len(sequence):
break
if sequence[i] == value:
i += 1
return i == len(sequence)Pattern: halve the search range each step. O(log n).
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1k consecutive numbers.Pattern: keep a running window sum; slide it instead of recomputing. O(n).
def max_subarray_sum(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # add new, drop old
best = max(best, window)
return bestPattern: a single pass keeping the top 3. O(n).
def three_largest(nums):
top = [None, None, None]
for n in nums:
if top[2] is None or n > top[2]:
top = [top[1], top[2], n]
elif top[1] is None or n > top[1]:
top = [top[1], n, top[2]]
elif top[0] is None or n > top[0]:
top = [n, top[1], top[2]]
return topPattern: walk the list, flipping each next pointer. O(n) time, O(1) space.
def reverse_list(head):
prev = None
while head:
nxt = head.next # save the next node
head.next = prev # flip the pointer
prev = head # move prev forward
head = nxt # move head forward
return prev # new headDFS (depth-first) uses recursion / a stack; BFS (breadth-first, level by level) uses a queue.
def dfs(node): # depth-first (pre-order)
if node is None:
return
print(node.value)
dfs(node.left)
dfs(node.right)
from collections import deque
def bfs(root): # breadth-first (level order)
queue = deque([root])
while queue:
node = queue.popleft()
print(node.value)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)Pattern: naive recursion is O(2ⁿ). Memoize (cache) results to make it O(n).
def fib(n, memo={}):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]Square each number of a sorted array, return sorted. Two pointers from both ends (largest squares are at the ends). O(n).
class Solution:
def sorted_squared(self, arr):
res = [0] * len(arr)
lo, hi = 0, len(arr) - 1
for i in range(len(arr) - 1, -1, -1):
if abs(arr[lo]) > abs(arr[hi]):
res[i] = arr[lo] ** 2; lo += 1
else:
res[i] = arr[hi] ** 2; hi -= 1
return resFind all triplets that sum to the target. Sort, then for each number use two pointers. O(n²).
class Solution:
def three_number_sum(self, nums, target):
nums.sort()
res = []
for i in range(len(nums) - 2):
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == target:
res.append([nums[i], nums[lo], nums[hi]]); lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return resPick one number from each array so their difference is smallest. Sort both, walk two pointers. O(n log n).
class Solution:
def smallest_difference(self, a, b):
a.sort(); b.sort()
i = j = 0; best = float("inf"); pair = []
while i < len(a) and j < len(b):
if abs(a[i] - b[j]) < best:
best = abs(a[i] - b[j]); pair = [a[i], b[j]]
if a[i] < b[j]: i += 1
elif a[i] > b[j]: j += 1
else: return [a[i], b[j]]
return pairMove all copies of a value to the end, in place. Two pointers. O(n).
class Solution:
def move_to_end(self, arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi:
while lo < hi and arr[hi] == target: hi -= 1
if arr[lo] == target:
arr[lo], arr[hi] = arr[hi], arr[lo]
lo += 1
return arrIs the array entirely non-increasing or non-decreasing? One pass. O(n).
class Solution:
def is_monotonic(self, arr):
up = all(arr[i] <= arr[i+1] for i in range(len(arr)-1))
down = all(arr[i] >= arr[i+1] for i in range(len(arr)-1))
return up or downEach output[i] = product of all other numbers — without division. Prefix & suffix products. O(n).
class Solution:
def array_of_products(self, arr):
n = len(arr); res = [1] * n
left = 1
for i in range(n):
res[i] = left; left *= arr[i]
right = 1
for i in range(n - 1, -1, -1):
res[i] *= right; right *= arr[i]
return resReturn the first value that appears twice. Hash set. O(n).
class Solution:
def first_duplicate(self, arr):
seen = set()
for n in arr:
if n in seen: return n
seen.add(n)
return -1Combine overlapping [start, end] ranges. Sort by start, then merge. O(n log n).
class Solution:
def merge_intervals(self, intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedLargest sum of any contiguous subarray. Track best ending here vs. restart. O(n).
class Solution:
def max_subarray(self, arr):
cur = best = arr[0]
for n in arr[1:]:
cur = max(n, cur + n)
best = max(best, cur)
return bestclass Solution:
def is_palindrome(self, s):
lo, hi = 0, len(s) - 1
while lo < hi:
if s[lo] != s[hi]: return False
lo += 1; hi -= 1
return True
# or simply: return s == s[::-1]Shift each letter by a key (wrapping around the alphabet). O(n).
class Solution:
def caesar_cipher(self, s, key):
out = []
for ch in s:
code = (ord(ch) - ord("a") + key) % 26
out.append(chr(ord("a") + code))
return "".join(out)class Solution:
def first_non_repeating(self, s):
counts = {}
for ch in s: counts[ch] = counts.get(ch, 0) + 1
for i, ch in enumerate(s):
if counts[ch] == 1: return i
return -1class Solution:
def run_length_encode(self, s):
out = []; count = 1
for i in range(1, len(s) + 1):
if i < len(s) and s[i] == s[i-1] and count < 9:
count += 1
else:
out.append(str(count) + s[i-1]); count = 1
return "".join(out)
# "AAAAAAAAAAAAABBCCCCDD" -> "9A4A2B4C2D"class Solution:
def bubble_sort(self, a):
for i in range(len(a)):
for j in range(len(a) - 1 - i):
if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j]
return a
def insertion_sort(self, a):
for i in range(1, len(a)):
j = i
while j > 0 and a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]; j -= 1
return a
def selection_sort(self, a):
for i in range(len(a)):
m = i
for j in range(i+1, len(a)):
if a[j] < a[m]: m = j
a[i], a[m] = a[m], a[i]
return aclass Solution:
def quick_sort(self, a):
if len(a) <= 1: return a
pivot = a[len(a)//2]
left = [x for x in a if x < pivot]
mid = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return self.quick_sort(left) + mid + self.quick_sort(right)
def merge_sort(self, a):
if len(a) <= 1: return a
m = len(a) // 2
L, R = self.merge_sort(a[:m]), self.merge_sort(a[m:])
res = []; i = j = 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: res.append(L[i]); i += 1
else: res.append(R[j]); j += 1
return res + L[i:] + R[j:]class Solution:
# Non-Constructible Change: smallest amount you CAN'T make
def non_constructible_change(self, coins):
coins.sort()
change = 0
for c in coins:
if c > change + 1: break
change += c
return change + 1
# Tandem Bicycle: pair fastest with slowest (fastest total speed)
def tandem_bicycle(self, red, blue, fastest=True):
red.sort(); blue.sort()
if fastest: blue.reverse()
return sum(max(r, b) for r, b in zip(red, blue))class Solution:
def min_coins(self, n, denoms):
dp = [float("inf")] * (n + 1)
dp[0] = 0
for coin in denoms:
for amount in range(coin, n + 1):
dp[amount] = min(dp[amount], dp[amount - coin] + 1)
return dp[n] if dp[n] != float("inf") else -1class Solution:
def ways_to_make_change(self, n, denoms):
dp = [0] * (n + 1)
dp[0] = 1
for coin in denoms:
for amount in range(coin, n + 1):
dp[amount] += dp[amount - coin]
return dp[n]class Solution:
def max_subset_no_adjacent(self, arr):
if not arr: return 0
prev, cur = 0, arr[0]
for n in arr[1:]:
prev, cur = cur, max(cur, prev + n)
return curclass Solution:
def levenshtein(self, a, b):
dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
for i in range(len(a)+1): dp[i][0] = i
for j in range(len(b)+1): dp[0][j] = j
for i in range(1, len(a)+1):
for j in range(1, len(b)+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[-1][-1]class Solution:
def find_closest(self, root, target):
closest = root.value; node = root
while node:
if abs(target - node.value) < abs(target - closest):
closest = node.value
node = node.left if target < node.value else node.right
return closestclass Solution:
def validate_bst(self, node, lo=float("-inf"), hi=float("inf")):
if node is None: return True
if not (lo < node.value < hi): return False
return (self.validate_bst(node.left, lo, node.value) and
self.validate_bst(node.right, node.value, hi))class Solution:
def invert_tree(self, node):
if node is None: return
node.left, node.right = node.right, node.left
self.invert_tree(node.left)
self.invert_tree(node.right)class Solution:
def in_order(self, node, out): # left, root, right -> sorted!
if node:
self.in_order(node.left, out); out.append(node.value); self.in_order(node.right, out)
def pre_order(self, node, out): # root, left, right
if node:
out.append(node.value); self.pre_order(node.left, out); self.pre_order(node.right, out)
def post_order(self, node, out): # left, right, root
if node:
self.post_order(node.left, out); self.post_order(node.right, out); out.append(node.value)Are all brackets ()[]{} properly matched? Push opens, match on closes. O(n).
class Solution:
def balanced_brackets(self, s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stackBuildings that can see the sunset (taller than all buildings toward the direction). O(n).
class Solution:
def sunset_views(self, buildings, direction):
res, tallest = [], 0
rng = range(len(buildings)) if direction == "WEST" else range(len(buildings)-1, -1, -1)
for i in rng:
if buildings[i] > tallest:
res.append(i); tallest = buildings[i]
return res if direction == "WEST" else res[::-1]For each item, the next larger one to its right (wrapping around). Monotonic stack. O(n).
class Solution:
def next_greater(self, arr):
n = len(arr); res = [-1] * n; stack = []
for i in range(2 * n):
idx = i % n
while stack and arr[stack[-1]] < arr[idx]:
res[stack.pop()] = arr[idx]
if i < n: stack.append(idx)
return resclass Solution:
def eval_rpn(self, tokens):
ops = {"+": lambda a,b: a+b, "-": lambda a,b: a-b,
"*": lambda a,b: a*b, "/": lambda a,b: int(a/b)}
stack = []
for t in tokens:
if t in ops:
b = stack.pop(); a = stack.pop(); stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]class Solution:
def sort_stack(self, stack):
if not stack: return stack
top = stack.pop()
self.sort_stack(stack)
self._insert(stack, top)
return stack
def _insert(self, stack, val):
if not stack or stack[-1] <= val:
stack.append(val); return
top = stack.pop(); self._insert(stack, val); stack.append(top)Two pointers k apart; when the fast one ends, slow is at the node before the target. O(n).
class Solution:
def remove_kth_from_end(self, head, k):
fast = slow = head
for _ in range(k): fast = fast.next
if fast is None: return head.next # removing the head
while fast.next:
fast = fast.next; slow = slow.next
slow.next = slow.next.next
return headTwo numbers stored as digit lists (ones digit first) — add them. O(n).
class Solution:
def sum_lists(self, l1, l2):
dummy = Node(0); cur = dummy; carry = 0
while l1 or l2 or carry:
total = carry
if l1: total += l1.value; l1 = l1.next
if l2: total += l2.value; l2 = l2.next
carry, digit = divmod(total, 10)
cur.next = Node(digit); cur = cur.next
return dummy.nextclass Solution:
def permutations(self, arr):
if len(arr) <= 1: return [arr[:]]
res = []
for i in range(len(arr)):
rest = arr[:i] + arr[i+1:]
for p in self.permutations(rest):
res.append([arr[i]] + p)
return resclass Solution:
def powerset(self, arr):
subsets = [[]]
for n in arr:
subsets += [s + [n] for s in subsets]
return subsets
# [1,2] -> [[], [1], [2], [1,2]]class Solution:
def phone_mnemonics(self, digits):
keys = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno",
"7":"pqrs","8":"tuv","9":"wxyz","0":"0","1":"1"}
res = []
def backtrack(i, cur):
if i == len(digits):
res.append("".join(cur)); return
for ch in keys[digits[i]]:
cur.append(ch); backtrack(i+1, cur); cur.pop()
backtrack(0, [])
return resWays to climb height stairs taking 1..maxSteps at a time. DP. O(n·k).
class Solution:
def staircase(self, height, max_steps):
ways = [1] + [0] * height
for h in range(1, height + 1):
for step in range(1, min(h, max_steps) + 1):
ways[h] += ways[h - step]
return ways[height]Binary search in a rotated sorted array. Decide which half is sorted each step. O(log n).
class Solution:
def shifted_binary_search(self, arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
if arr[lo] <= arr[mid]: # left half sorted
if arr[lo] <= target < arr[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half sorted
if arr[mid] < target <= arr[hi]: lo = mid + 1
else: hi = mid - 1
return -1First and last index of a target in a sorted array. Two binary searches. O(log n).
class Solution:
def search_range(self, arr, target):
def bound(left):
lo, hi, res = 0, len(arr) - 1, -1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
res = mid
if left: hi = mid - 1
else: lo = mid + 1
elif arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return res
return [bound(True), bound(False)]Like quicksort but only recurse into the side with the answer. Average O(n).
class Solution:
def quickselect(self, arr, k): # k is 1-indexed position
lo, hi = 0, len(arr) - 1
while True:
pivot = arr[hi]; p = lo
for i in range(lo, hi):
if arr[i] < pivot:
arr[i], arr[p] = arr[p], arr[i]; p += 1
arr[p], arr[hi] = arr[hi], arr[p]
if p == k - 1: return arr[p]
elif p < k - 1: lo = p + 1
else: hi = p - 1Rows & columns both sorted. Start top-right, move left/down. O(n+m).
class Solution:
def search_matrix(self, matrix, target):
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target: return [row, col]
elif matrix[row][col] > target: col -= 1
else: row += 1
return [-1, -1]Sliding window + a map of last-seen positions. O(n).
class Solution:
def longest_unique_substring(self, s):
seen = {}; start = 0; best = [0, 1]
for i, ch in enumerate(s):
if ch in seen and seen[ch] >= start:
start = seen[ch] + 1
if i + 1 - start > best[1] - best[0]:
best = [start, i + 1]
seen[ch] = i
return s[best[0]:best[1]]Expand around every center (odd & even). O(n²).
class Solution:
def longest_palindrome(self, s):
res = ""
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
for i in range(len(s)):
for cand in (expand(i, i), expand(i, i+1)):
if len(cand) > len(res): res = cand
return resclass Solution:
def group_anagrams(self, words):
groups = {}
for w in words:
key = "".join(sorted(w))
groups.setdefault(key, []).append(w)
return list(groups.values())class Solution:
def valid_ip_addresses(self, s):
res = []
def ok(part):
return len(part) == 1 or (part[0] != "0" and int(part) <= 255)
for a in range(1, 4):
for b in range(a+1, a+4):
for c in range(b+1, b+4):
p1, p2, p3, p4 = s[:a], s[a:b], s[b:c], s[c:]
if 1 <= len(p4) <= 3 and all(ok(p) for p in (p1,p2,p3,p4)):
res.append(f"{p1}.{p2}.{p3}.{p4}")
return resclass Solution:
def reverse_words(self, s):
return " ".join(s.split()[::-1])
# "the sky is blue" -> "blue is sky the"Are two strings at most one insert/delete/replace apart? O(n).
class Solution:
def one_edit(self, a, b):
if abs(len(a) - len(b)) > 1: return False
i = j = 0; edited = False
while i < len(a) and j < len(b):
if a[i] != b[j]:
if edited: return False
edited = True
if len(a) > len(b): i += 1
elif len(a) < len(b): j += 1
else: i += 1; j += 1
else:
i += 1; j += 1
return TrueDetect a cycle in a directed graph (adjacency list). DFS tracking the current path. O(V+E).
class Solution:
def cycle_in_graph(self, edges):
n = len(edges)
visited = [False] * n; in_path = [False] * n
def dfs(node):
visited[node] = in_path[node] = True
for nb in edges[node]:
if not visited[nb]:
if dfs(nb): return True
elif in_path[nb]:
return True
in_path[node] = False
return False
return any(dfs(i) for i in range(n) if not visited[i])Flip any group of 1s not connected to the border to 0. Mark border-connected 1s, then clear the rest. O(w·h).
class Solution:
def remove_islands(self, matrix):
rows, cols = len(matrix), len(matrix[0])
def fill(r, c):
stack = [(r, c)]
while stack:
r, c = stack.pop()
if 0 <= r < rows and 0 <= c < cols and matrix[r][c] == 1:
matrix[r][c] = 2 # mark as safe
stack += [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]
for r in range(rows):
for c in range(cols):
if (r in (0, rows-1) or c in (0, cols-1)) and matrix[r][c] == 1:
fill(r, c)
for r in range(rows):
for c in range(cols):
matrix[r][c] = 1 if matrix[r][c] == 2 else 0
return matrixRead a matrix in a spiral. Shrink four borders inward. O(n).
class Solution:
def spiral_traverse(self, matrix):
res = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right + 1): res.append(matrix[top][c])
for r in range(top + 1, bottom + 1): res.append(matrix[r][right])
if top < bottom:
for c in range(right - 1, left - 1, -1): res.append(matrix[bottom][c])
if left < right:
for r in range(bottom - 1, top, -1): res.append(matrix[r][left])
top += 1; bottom -= 1; left += 1; right -= 1
return resLength of the longest "up then down" run. Find each peak, expand both ways. O(n).
class Solution:
def longest_peak(self, arr):
longest = 0; i = 1
while i < len(arr) - 1:
if not (arr[i-1] < arr[i] > arr[i+1]):
i += 1; continue
left = i - 2
while left >= 0 and arr[left] < arr[left + 1]: left -= 1
right = i + 2
while right < len(arr) and arr[right] < arr[right - 1]: right += 1
longest = max(longest, right - left - 1)
i = right
return longestSort an array containing three distinct values, in place, in one pass. O(n).
class Solution:
def three_number_sort(self, arr, order):
first, second = order[0], order[1]
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] == first:
arr[low], arr[mid] = arr[mid], arr[low]; low += 1; mid += 1
elif arr[mid] == second:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]; high -= 1
return arrFewest jumps to reach the end, where each value is the max jump length. Greedy. O(n).
class Solution:
def min_jumps(self, arr):
if len(arr) == 1: return 0
jumps = 0; max_reach = arr[0]; steps = arr[0]
for i in range(1, len(arr) - 1):
max_reach = max(max_reach, i + arr[i])
steps -= 1
if steps == 0:
jumps += 1; steps = max_reach - i
return jumps + 1Water trapped above each bar = min(tallest left, tallest right) − its height. O(n).
class Solution:
def water_area(self, heights):
n = len(heights)
left_max = [0] * n; right_max = [0] * n
m = 0
for i in range(n): left_max[i] = m; m = max(m, heights[i])
m = 0
for i in range(n - 1, -1, -1): right_max[i] = m; m = max(m, heights[i])
return sum(max(0, min(left_max[i], right_max[i]) - heights[i]) for i in range(n))Sizes of every connected group of 1s in a grid. Flood-fill each. O(w·h).
class Solution:
def river_sizes(self, matrix):
sizes = []
visited = [[False] * len(matrix[0]) for _ in matrix]
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if matrix[r][c] == 1 and not visited[r][c]:
size = 0; stack = [(r, c)]
while stack:
i, j = stack.pop()
if (i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0])
or visited[i][j] or matrix[i][j] == 0):
continue
visited[i][j] = True; size += 1
stack += [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
sizes.append(size)
return sizesOrder tasks so each comes after its prerequisites. Kahn's algorithm (in-degrees + queue). O(V+E).
from collections import deque
class Solution:
def topological_sort(self, jobs, deps):
graph = {j: [] for j in jobs}
indegree = {j: 0 for j in jobs}
for a, b in deps: # a must come before b
graph[a].append(b); indegree[b] += 1
queue = deque(j for j in jobs if indegree[j] == 0)
order = []
while queue:
j = queue.popleft(); order.append(j)
for nb in graph[j]:
indegree[nb] -= 1
if indegree[nb] == 0: queue.append(nb)
return order if len(order) == len(jobs) else [] # [] means a cycleShortest distance from a start node to all others (non-negative weights). Min-heap. O(E log V).
import heapq
class Solution:
def dijkstra(self, start, edges):
# edges[i] = list of [destination, weight]
dist = [float("inf")] * len(edges); dist[start] = 0
pq = [(0, start)]
while pq:
d, node = heapq.heappop(pq)
if d > dist[node]: continue
for nb, w in edges[node]:
if d + w < dist[nb]:
dist[nb] = d + w; heapq.heappush(pq, (d + w, nb))
return [-1 if d == float("inf") else d for d in dist]Track which items are connected. Near-O(1) with path compression.
class UnionFind:
def __init__(self): self.parent = {}
def add(self, x): self.parent.setdefault(x, x)
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path compression
x = self.parent[x]
return x
def union(self, a, b):
self.parent[self.find(a)] = self.find(b)Find which words appear on the board (8-directional). Trie of words + DFS.
class Solution:
def boggle_board(self, board, words):
trie = {}
for w in words: # build a trie
node = trie
for ch in w: node = node.setdefault(ch, {})
node["*"] = w
rows, cols = len(board), len(board[0])
found = set()
def dfs(r, c, node, visited):
if (r < 0 or c < 0 or r >= rows or c >= cols or (r, c) in visited
or board[r][c] not in node):
return
node = node[board[r][c]]; visited = visited | {(r, c)}
if "*" in node: found.add(node["*"])
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
dfs(r + dr, c + dc, node, visited)
for r in range(rows):
for c in range(cols):
dfs(r, c, trie, set())
return list(found)class Solution:
def lcs(self, a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]class Solution:
def lis(self, arr):
if not arr: return 0
dp = [1] * len(arr)
for i in range(len(arr)):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Maximize value within a weight capacity. Classic 2-D DP. O(n·capacity).
class Solution:
def knapsack(self, items, capacity):
# items = [[value, weight], ...]
dp = [[0] * (capacity + 1) for _ in range(len(items) + 1)]
for i in range(1, len(items) + 1):
value, weight = items[i-1]
for c in range(capacity + 1):
if weight > c:
dp[i][c] = dp[i-1][c]
else:
dp[i][c] = max(dp[i-1][c], dp[i-1][c - weight] + value)
return dp[-1][-1]class BST:
def __init__(self, value):
self.value = value; self.left = None; self.right = None
def insert(self, value):
node = self
while True:
if value < node.value:
if node.left is None: node.left = BST(value); break
node = node.left
else:
if node.right is None: node.right = BST(value); break
node = node.right
return self
def contains(self, value):
node = self
while node:
if value < node.value: node = node.left
elif value > node.value: node = node.right
else: return True
return Falseimport heapq
nums = [5, 2, 8, 1]
heapq.heapify(nums) # O(n) -> smallest is always nums[0]
heapq.heappush(nums, 3) # O(log n)
smallest = heapq.heappop(nums) # remove + return the min, O(log n)
# Max-heap trick: push/pop the NEGATIVE of each valueGet/put in O(1), evicting the least-recently-used item. An OrderedDict does the heavy lifting.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict(); self.capacity = capacity
def get(self, key):
if key not in self.cache: return -1
self.cache.move_to_end(key) # mark most-recently-used
return self.cache[key]
def put(self, key, value):
if key in self.cache: self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # evict least-recently-usedclass SuffixTrie:
def __init__(self, string):
self.root = {}; self.end = "*"
for i in range(len(string)):
self._insert(string[i:])
def _insert(self, s):
node = self.root
for ch in s: node = node.setdefault(ch, {})
node[self.end] = True
def contains(self, s):
node = self.root
for ch in s:
if ch not in node: return False
node = node[ch]
return self.end in nodeFind a pattern in text in O(n+m) using a precomputed "failure" table.
class Solution:
def kmp_search(self, text, pattern):
lps = [0] * len(pattern) # longest prefix = suffix table
k = 0
for i in range(1, len(pattern)):
while k > 0 and pattern[i] != pattern[k]: k = lps[k-1]
if pattern[i] == pattern[k]: k += 1
lps[i] = k
j = 0
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]: j = lps[j-1]
if text[i] == pattern[j]: j += 1
if j == len(pattern): return i - j + 1 # start index of match
return -1Fill the grid by trying digits and backtracking when stuck. 0 = empty.
class Solution:
def solve_sudoku(self, board):
def valid(r, c, val):
for i in range(9):
if board[r][i] == val or board[i][c] == val: return False
br, bc = 3 * (r // 3), 3 * (c // 3)
for i in range(br, br + 3):
for j in range(bc, bc + 3):
if board[i][j] == val: return False
return True
def solve():
for r in range(9):
for c in range(9):
if board[r][c] == 0:
for val in range(1, 10):
if valid(r, c, val):
board[r][c] = val
if solve(): return True
board[r][c] = 0 # backtrack
return False
return True
solve()
return boardAll valid arrangements of n <div></div> pairs (same idea as "generate parentheses").
class Solution:
def generate_div_tags(self, n):
res = []
def build(open_used, close_used, cur):
if open_used < n:
build(open_used + 1, close_used, cur + "<div>")
if close_used < open_used:
build(open_used, close_used + 1, cur + "</div>")
if close_used == n:
res.append(cur)
build(0, 0, "")
return resMedian of a growing stream. Keep a max-heap of the low half & a min-heap of the high half. O(log n) per add.
import heapq
class ContinuousMedian:
def __init__(self):
self.lo = [] # max-heap (store negatives)
self.hi = [] # min-heap
def add(self, num):
heapq.heappush(self.lo, -num)
heapq.heappush(self.hi, -heapq.heappop(self.lo)) # balance
if len(self.hi) > len(self.lo):
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def median(self):
if len(self.lo) > len(self.hi): return -self.lo[0]
return (-self.lo[0] + self.hi[0]) / 2import heapq
class Solution:
def heap_sort(self, arr):
heapq.heapify(arr) # O(n)
return [heapq.heappop(arr) for _ in range(len(arr))] # n × O(log n)O(log(min(m,n))) by binary-searching the partition point.
class Solution:
def median_two_sorted(self, a, b):
if len(a) > len(b): a, b = b, a
m, n = len(a), len(b)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
a_l = a[i-1] if i > 0 else float("-inf")
a_r = a[i] if i < m else float("inf")
b_l = b[j-1] if j > 0 else float("-inf")
b_r = b[j] if j < n else float("inf")
if a_l <= b_r and b_l <= a_r:
if (m + n) % 2: return max(a_l, b_l)
return (max(a_l, b_l) + min(a_r, b_r)) / 2
elif a_l > b_r: hi = i - 1
else: lo = i + 1Cheapest set of edges connecting every node. Sort edges, add if they join two different groups (union-find). O(E log E).
class Solution:
def kruskal(self, n, edges):
# edges = [(weight, u, v), ...]
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]; x = parent[x]
return x
total = 0
for w, u, v in sorted(edges):
ru, rv = find(u), find(v)
if ru != rv:
parent[ru] = rv; total += w
return totalimport heapq
class Solution:
def prim(self, n, adj):
# adj[u] = list of (weight, v)
visited = [False] * n; pq = [(0, 0)]; total = 0
while pq:
w, u = heapq.heappop(pq)
if visited[u]: continue
visited[u] = True; total += w
for weight, v in adj[u]:
if not visited[v]: heapq.heappush(pq, (weight, v))
return totalfrom collections import deque
class Solution:
def min_knight_moves(self, start, target):
moves = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]
q = deque([(start[0], start[1], 0)]); seen = {tuple(start)}
while q:
r, c, d = q.popleft()
if [r, c] == target: return d
for dr, dc in moves:
nxt = (r + dr, c + dc)
if nxt not in seen:
seen.add(nxt); q.append((nxt[0], nxt[1], d + 1))class Solution:
def zigzag_traverse(self, matrix):
H, W = len(matrix) - 1, len(matrix[0]) - 1
res = []; r = c = 0; down = True
while 0 <= r <= H and 0 <= c <= W:
res.append(matrix[r][c])
if down:
if c == 0 or r == H:
down = False
if r == H: c += 1
else: r += 1
else: r += 1; c -= 1
else:
if r == 0 or c == W:
down = True
if c == W: r += 1
else: c += 1
else: r -= 1; c += 1
return resAll quadruplets summing to target. Hash pair-sums while scanning. Average O(n²).
class Solution:
def four_number_sum(self, nums, target):
pair_sums = {}; res = []
for i in range(1, len(nums) - 1):
for j in range(i + 1, len(nums)):
need = target - (nums[i] + nums[j])
for pair in pair_sums.get(need, []):
res.append(pair + [nums[i], nums[j]])
for k in range(i):
s = nums[i] + nums[k]
pair_sums.setdefault(s, []).append([nums[k], nums[i]])
return resSmallest subarray that, if sorted, makes the whole array sorted. O(n).
class Solution:
def subarray_sort(self, arr):
max_so_far = arr[0]; right = -1
for i in range(len(arr)):
if arr[i] < max_so_far: right = i
else: max_so_far = arr[i]
min_so_far = arr[-1]; left = -1
for i in range(len(arr) - 1, -1, -1):
if arr[i] > min_so_far: left = i
else: min_so_far = arr[i]
return [left, right]Longest run of consecutive integers (any order). Hash set. O(n).
class Solution:
def largest_range(self, arr):
nums = set(arr); best = []; longest = 0
for n in arr:
if n - 1 not in nums: # start of a run
length = 1
while n + length in nums: length += 1
if length > longest:
longest = length; best = [n, n + length - 1]
return bestGive each child ≥1 reward; a higher score than a neighbor needs more. Two passes. O(n).
class Solution:
def min_rewards(self, scores):
rewards = [1] * len(scores)
for i in range(1, len(scores)):
if scores[i] > scores[i-1]: rewards[i] = rewards[i-1] + 1
for i in range(len(scores) - 2, -1, -1):
if scores[i] > scores[i+1]:
rewards[i] = max(rewards[i], rewards[i+1] + 1)
return sum(rewards)Biggest rectangle in a histogram. Monotonic stack of increasing heights. O(n).
class Solution:
def largest_rectangle(self, heights):
stack = []; best = 0
for i, h in enumerate(heights + [0]): # sentinel flushes the stack
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return bestSmallest window of big that contains every char of small (minimum window substring). O(n).
from collections import Counter
class Solution:
def smallest_substring(self, big, small):
need = Counter(small); missing = len(small)
left = 0; best = ""
for right, ch in enumerate(big):
if need[ch] > 0: missing -= 1
need[ch] -= 1
while missing == 0: # window has everything
if not best or right - left + 1 < len(best):
best = big[left:right + 1]
need[big[left]] += 1
if need[big[left]] > 0: missing += 1
left += 1
return bestFewest spaces to break a digit string into "known" numbers. Memoized recursion. O(n³).
class Solution:
def numbers_in_pi(self, pi, numbers):
known = set(numbers); cache = {}
def helper(idx):
if idx == len(pi): return -1 # -1 cancels the last +1
if idx in cache: return cache[idx]
best = float("inf")
for i in range(idx, len(pi)):
if pi[idx:i+1] in known:
best = min(best, 1 + helper(i + 1))
cache[idx] = best
return best
result = helper(0)
return -1 if result == float("inf") else resultJumping by each value, do you visit every index exactly once and land back at the start? O(n).
class Solution:
def single_cycle_check(self, arr):
visited = 0; idx = 0
while visited < len(arr):
if visited > 0 and idx == 0: return False # back to start too early
visited += 1
idx = (idx + arr[idx]) % len(arr)
return idx == 0Circular road of cities with fuel — find the only city you can start from and finish the loop. O(n).
class Solution:
def valid_starting_city(self, distances, fuel, mpg):
min_remaining = 0; remaining = 0; start = 0
for i in range(1, len(distances)):
remaining += fuel[i-1] * mpg - distances[i-1]
if remaining < min_remaining:
min_remaining = remaining; start = i
return startThe element appearing > n/2 times — in O(n) time, O(1) space.
class Solution:
def majority_element(self, nums):
count = 0; candidate = None
for n in nums:
if count == 0: candidate = n
count += 1 if n == candidate else -1
return candidateNon-comparison sort for non-negative ints — bucket by each digit. O(d·n).
class Solution:
def radix_sort(self, arr):
if not arr: return arr
max_val = max(arr); exp = 1
while max_val // exp > 0:
buckets = [[] for _ in range(10)]
for num in arr:
buckets[(num // exp) % 10].append(num)
arr = [num for bucket in buckets for num in bucket]
exp *= 10
return arrHow many pairs are out of order? Piggyback on merge sort. O(n log n).
class Solution:
def count_inversions(self, arr):
def sort_count(a):
if len(a) <= 1: return a, 0
mid = len(a) // 2
left, lc = sort_count(a[:mid])
right, rc = sort_count(a[mid:])
merged = []; i = j = inv = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inv += len(left) - i # rest of left are all inversions
merged += left[i:] + right[j:]
return merged, lc + rc + inv
return sort_count(arr)[1]Place N queens so none attack each other. Backtrack column by column, tracking used columns & diagonals.
class Solution:
def non_attacking_queens(self, n):
cols = set(); diag1 = set(); diag2 = set()
def place(row):
if row == n: return 1
count = 0
for col in range(n):
if col in cols or (row+col) in diag1 or (row-col) in diag2:
continue
cols.add(col); diag1.add(row+col); diag2.add(row-col)
count += place(row + 1)
cols.discard(col); diag1.discard(row+col); diag2.discard(row-col)
return count
return place(0)class Solution:
def merge_two_lists(self, l1, l2):
dummy = Node(0); tail = dummy
while l1 and l2:
if l1.value <= l2.value: tail.next = l1; l1 = l1.next
else: tail.next = l2; l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.nextFind the middle, reverse the second half, compare. O(n) time, O(1) space.
class Solution:
def is_palindrome_list(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
prev = None # reverse second half
while slow:
slow.next, prev, slow = prev, slow, slow.next
left, right = head, prev
while right:
if left.value != right.value: return False
left = left.next; right = right.next
return True1→2→3→4→5 becomes 1→5→2→4→3. Split, reverse the back half, interleave. O(n).
class Solution:
def zip_linked_list(self, head):
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next; fast = fast.next.next
second = slow.next; slow.next = None
prev = None
while second:
second.next, prev, second = prev, second, second.next
first, second = head, prev
while second:
f_next, s_next = first.next, second.next
first.next = second; second.next = f_next
first, second = f_next, s_next
return headclass Solution:
def swap_pairs(self, head):
dummy = Node(0); dummy.next = head; prev = dummy
while prev.next and prev.next.next:
a, b = prev.next, prev.next.next
a.next = b.next; b.next = a; prev.next = b
prev = a
return dummy.nextLowest common ancestor when nodes have a .parent. Equalize depths, then climb together. O(d).
class Solution:
def get_depth(self, node, top):
d = 0
while node != top: node = node.parent; d += 1
return d
def youngest_common_ancestor(self, top, a, b):
da, db = self.get_depth(a, top), self.get_depth(b, top)
while da > db: a = a.parent; da -= 1
while db > da: b = b.parent; db -= 1
while a != b: a = a.parent; b = b.parent
return aclass Solution:
def inorder(self, root):
res = []; stack = []; node = root
while stack or node:
while node:
stack.append(node); node = node.left
node = stack.pop()
res.append(node.value)
node = node.right
return resLargest sum along any path. At each node, best = node + best-left-branch + best-right-branch. O(n).
class Solution:
def max_path_sum(self, root):
best = [float("-inf")]
def helper(node):
if not node: return 0
left = max(helper(node.left), 0)
right = max(helper(node.right), 0)
best[0] = max(best[0], node.value + left + right)
return node.value + max(left, right)
helper(root)
return best[0]class Solution:
def is_symmetric(self, root):
def mirror(a, b):
if not a and not b: return True
if not a or not b or a.value != b.value: return False
return mirror(a.left, b.right) and mirror(a.right, b.left)
return mirror(root, root)class Solution:
def is_balanced(self, root):
def check(node):
if not node: return 0
lh = check(node.left); rh = check(node.right)
if lh == -1 or rh == -1 or abs(lh - rh) > 1: return -1
return max(lh, rh) + 1
return check(root) != -1class Solution:
def max_sum_increasing(self, arr):
sums = arr[:]
for i in range(len(arr)):
for j in range(i):
if arr[j] < arr[i] and sums[j] + arr[i] > sums[i]:
sums[i] = sums[j] + arr[i]
return max(sums)Paths from top-left to bottom-right moving only right/down. O(w·h).
class Solution:
def num_ways(self, width, height):
dp = [[1] * width for _ in range(height)]
for r in range(1, height):
for c in range(1, width):
dp[r][c] = dp[r-1][c] + dp[r][c-1]
return dp[height-1][width-1]class Solution:
def max_profit_k(self, prices, k):
if not prices: return 0
dp = [0] * len(prices)
for _ in range(k):
max_diff = -prices[0]; new = [0] * len(prices)
for d in range(1, len(prices)):
new[d] = max(new[d-1], prices[d] + max_diff)
max_diff = max(max_diff, dp[d] - prices[d])
dp = new
return dp[-1]class Solution:
def dice_throws(self, num_dice, num_sides, target):
dp = [[0] * (target + 1) for _ in range(num_dice + 1)]
dp[0][0] = 1
for d in range(1, num_dice + 1):
for t in range(1, target + 1):
for s in range(1, min(t, num_sides) + 1):
dp[d][t] += dp[d-1][t-s]
return dp[num_dice][target]Tallest stack of disks where each must be strictly smaller in all 3 dimensions. DP after sorting by height. O(n²).
class Solution:
def disk_stacking(self, disks):
disks.sort(key=lambda d: d[2]) # by height
heights = [d[2] for d in disks]
seq = [None] * len(disks); max_i = 0
for i in range(len(disks)):
for j in range(i):
if all(disks[j][k] < disks[i][k] for k in range(3)):
if heights[j] + disks[i][2] > heights[i]:
heights[i] = heights[j] + disks[i][2]; seq[i] = j
if heights[i] >= heights[max_i]: max_i = i
stack = []; i = max_i
while i is not None:
stack.append(disks[i]); i = seq[i]
return stack[::-1]class Solution:
def tournament_winner(self, competitions, results):
scores = {"": 0}; best = ""
for i, (home, away) in enumerate(competitions):
winner = home if results[i] == 1 else away
scores[winner] = scores.get(winner, 0) + 3
if scores[winner] > scores[best]: best = winner
return bestclass Solution:
def transpose(self, matrix):
return [[matrix[r][c] for r in range(len(matrix))]
for c in range(len(matrix[0]))]class Solution:
def product_sum(self, arr, depth=1):
total = 0
for el in arr:
if isinstance(el, list):
total += self.product_sum(el, depth + 1)
else:
total += el
return total * depthOrder shortest jobs first so everyone waits the least. Greedy. O(n log n).
class Solution:
def min_waiting_time(self, queries):
queries.sort()
total = 0
for i, duration in enumerate(queries):
total += duration * (len(queries) - i - 1)
return totalclass Solution:
def common_characters(self, strings):
result = set(strings[0])
for s in strings[1:]:
result &= set(s)
return list(result)Pairs where one word is the other reversed (e.g. "diaper"/"repaid"). O(n·len).
class Solution:
def semordnilap(self, words):
seen = set(words); pairs = []
for w in words:
rev = w[::-1]
if rev in seen and rev != w:
pairs.append([w, rev]); seen.discard(w); seen.discard(rev)
return pairsclass Solution:
def branch_sums(self, root):
sums = []
def helper(node, running):
if not node: return
running += node.value
if not node.left and not node.right:
sums.append(running); return
helper(node.left, running); helper(node.right, running)
helper(root, 0)
return sumsclass Solution:
def node_depths(self, root, depth=0):
if not root: return 0
return depth + self.node_depths(root.left, depth + 1) + self.node_depths(root.right, depth + 1)class Solution:
def middle_node(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
return slow(sorted list — drop consecutive equal nodes). O(n).
class Solution:
def dedup_sorted_list(self, head):
node = head
while node:
while node.next and node.next.value == node.value:
node.next = node.next.next
node = node.next
return headDetect where a linked list loops back. Slow/fast pointers, then reset one to the head. O(n), O(1).
class Solution:
def find_loop(self, head):
slow = head.next; fast = head.next.next
while slow != fast:
slow = slow.next; fast = fast.next.next
slow = head
while slow != fast:
slow = slow.next; fast = fast.next
return slow # node where the loop startsA stack that also returns its current min & max in O(1) (store them at each level).
class MinMaxStack:
def __init__(self):
self.stack = []; self.minmax = []
def push(self, num):
if self.minmax:
mn, mx = self.minmax[-1]
self.minmax.append((min(mn, num), max(mx, num)))
else:
self.minmax.append((num, num))
self.stack.append(num)
def pop(self): self.minmax.pop(); return self.stack.pop()
def peek(self): return self.stack[-1]
def get_min(self): return self.minmax[-1][0]
def get_max(self): return self.minmax[-1][1]Do two arrays produce identical BSTs? Compare roots, then left/right subsets recursively. O(n²).
class Solution:
def same_bsts(self, a, b):
if len(a) != len(b): return False
if not a: return True
if a[0] != b[0]: return False
left_a = [x for x in a[1:] if x < a[0]]
left_b = [x for x in b[1:] if x < b[0]]
right_a = [x for x in a[1:] if x >= a[0]]
right_b = [x for x in b[1:] if x >= b[0]]
return self.same_bsts(left_a, left_b) and self.same_bsts(right_a, right_b)Find free slots ≥ duration in two people's calendars. Merge busy blocks, return the gaps.
class Solution:
def calendar_matching(self, c1, b1, c2, b2, duration):
to_min = lambda t: int(t.split(":")[0]) * 60 + int(t.split(":")[1])
to_str = lambda m: f"{m//60}:{m%60:02d}"
blocks = [["0:00", b1[0]]] + c1 + [[b1[1], "23:59"]] \
+ [["0:00", b2[0]]] + c2 + [[b2[1], "23:59"]]
busy = sorted([[to_min(s), to_min(e)] for s, e in blocks])
merged = [busy[0]]
for s, e in busy[1:]:
if s <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], e)
else: merged.append([s, e])
free = []
for i in range(1, len(merged)):
if merged[i][0] - merged[i-1][1] >= duration:
free.append([to_str(merged[i-1][1]), to_str(merged[i][0])])
return freeCan the graph be 2-colored so no edge joins same colors? BFS, alternate colors. O(V+E).
from collections import deque
class Solution:
def two_colorable(self, edges):
colors = [None] * len(edges)
colors[0] = True
queue = deque([0])
while queue:
node = queue.popleft()
for nb in edges[node]:
if colors[nb] is None:
colors[nb] = not colors[node]; queue.append(nb)
elif colors[nb] == colors[node]:
return False
return TrueLike Dijkstra but guided by a heuristic toward the goal. Min-heap on (cost + estimate).
import heapq
class Solution:
def a_star(self, start, end, graph):
# graph[node] = list of (neighbor, cost); positions are (row, col)
h = lambda a, b: abs(a[0]-b[0]) + abs(a[1]-b[1]) # Manhattan estimate
pq = [(h(start, end), 0, start)]
g = {start: 0}
while pq:
_, cost, node = heapq.heappop(pq)
if node == end: return cost
for nb, w in graph.get(node, []):
ng = cost + w
if nb not in g or ng < g[nb]:
g[nb] = ng
heapq.heappush(pq, (ng + h(nb, end), ng, nb))
return -1Is there a currency cycle that multiplies to > 1? Take −log of rates → a profitable cycle is a negative cycle (Bellman-Ford). O(n³).
import math
class Solution:
def detect_arbitrage(self, rates):
n = len(rates)
graph = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
dist = [0] * n
for _ in range(n - 1): # relax edges n-1 times
for u in range(n):
for v in range(n):
if dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
for u in range(n): # one more pass detects a neg cycle
for v in range(n):
if dist[u] + graph[u][v] < dist[v]:
return True
return FalseIs three an interleaving of one and two (keeping each one's order)? Memoized recursion. O(n·m).
class Solution:
def interweaving(self, one, two, three):
if len(one) + len(two) != len(three): return False
cache = {}
def helper(i, j):
if i == len(one) and j == len(two): return True
if (i, j) in cache: return cache[(i, j)]
res = False
k = i + j
if i < len(one) and one[i] == three[k]: res = helper(i + 1, j)
if not res and j < len(two) and two[j] == three[k]: res = helper(i, j + 1)
cache[(i, j)] = res
return res
return helper(0, 0)Longest chain where each word becomes the next by adding one letter. Sort by length, DP. O(n·L²).
class Solution:
def longest_string_chain(self, words):
words.sort(key=len)
best = {}; longest = 1
for w in words:
best[w] = 1
for i in range(len(w)):
pred = w[:i] + w[i+1:] # remove one char
if pred in best:
best[w] = max(best[w], best[pred] + 1)
longest = max(longest, best[w])
return longestFewest cuts so every piece is a palindrome. Precompute palindromes, then DP. O(n²).
class Solution:
def palindrome_min_cuts(self, s):
n = len(s)
is_pal = [[False] * n for _ in range(n)]
for i in range(n): is_pal[i][i] = True
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and (length == 2 or is_pal[i+1][j-1]):
is_pal[i][j] = True
cuts = [0] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
cuts[i] = min(cuts[j] + 1 for j in range(i) if is_pal[j+1][i])
return cuts[-1]from collections import Counter
class Solution:
def generate_document(self, characters, document):
available = Counter(characters)
for ch in document:
if available[ch] <= 0: return False
available[ch] -= 1
return TruePair tasks for k workers (2 each) to minimize total time — pair fastest with slowest. O(n log n).
class Solution:
def task_assignment(self, k, durations):
order = sorted(range(len(durations)), key=lambda i: durations[i])
return [[order[i], order[len(durations) - 1 - i]] for i in range(k)]class Solution:
def best_seat(self, seats):
best, max_space, left = -1, 0, 0
while left < len(seats):
right = left + 1
while right < len(seats) and seats[right] == 0: right += 1
if right - left - 1 > max_space:
max_space = right - left - 1; best = (left + right) // 2
left = right
return bestclass Solution:
def missing_numbers(self, nums):
total = sum(range(1, len(nums) + 3))
missing_sum = total - sum(nums)
avg = missing_sum // 2
low = sum(x for x in nums if x <= avg)
a = sum(range(1, avg + 1)) - low
return [a, missing_sum - a]Smallest axis-aligned rectangle from a set of points. Check diagonal corner pairs. O(n²).
class Solution:
def minimum_area_rectangle(self, points):
seen = set(map(tuple, points)); best = float("inf")
for i in range(len(points)):
for j in range(i):
x1, y1 = points[i]; x2, y2 = points[j]
if x1 != x2 and y1 != y2 and (x1, y2) in seen and (x2, y1) in seen:
best = min(best, abs(x1 - x2) * abs(y1 - y2))
return best if best != float("inf") else 0Largest sum of any size×size square. 2-D prefix sums. O(w·h).
class Solution:
def max_sum_submatrix(self, matrix, size):
rows, cols = len(matrix), len(matrix[0])
s = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
s[r+1][c+1] = matrix[r][c] + s[r][c+1] + s[r+1][c] - s[r][c]
best = float("-inf")
for r in range(size, rows + 1):
for c in range(size, cols + 1):
total = s[r][c] - s[r-size][c] - s[r][c-size] + s[r-size][c-size]
best = max(best, total)
return bestPick the block minimizing the max distance to every requirement. Precompute nearest each side. O(b·r).
class Solution:
def apartment_hunting(self, blocks, reqs):
n = len(blocks); dists = []
for req in reqs:
closest = [float("inf")] * n; nearest = float("inf")
for i in range(n):
if blocks[i][req]: nearest = i
closest[i] = abs(i - nearest)
for i in range(n - 1, -1, -1):
if blocks[i][req]: nearest = i
closest[i] = min(closest[i], abs(i - nearest))
dists.append(closest)
best, best_max = 0, float("inf")
for i in range(n):
worst = max(d[i] for d in dists)
if worst < best_max: best_max, best = worst, i
return bestLeaves are numbers (≥0); internal nodes are operators (−1 add, −2 subtract, −3 divide, −4 multiply).
class Solution:
def evaluate_expression_tree(self, node):
if node.value >= 0: return node.value
left = self.evaluate_expression_tree(node.left)
right = self.evaluate_expression_tree(node.right)
if node.value == -1: return left + right
if node.value == -2: return left - right
if node.value == -3: return int(left / right)
return left * rightSum of node depths across every subtree. O(n) with a helper that returns sum + count.
class Solution:
def all_kinds_of_node_depths(self, root):
def helper(node):
if not node: return (0, 0) # (sum_of_depths, node_count)
ls, lc = helper(node.left)
rs, rc = helper(node.right)
depth_sum = ls + lc + rs + rc # +1 depth for each descendant
return (depth_sum, lc + rc + 1)
def total(node):
if not node: return 0
return helper(node)[0] + total(node.left) + total(node.right)
return total(root)class Solution:
def flatten_tree(self, root):
node = root
while node:
if node.left:
rightmost = node.left
while rightmost.right: rightmost = rightmost.right
rightmost.right = node.right
node.right = node.left; node.left = None
node = node.right
return rootHow many tree shapes with n nodes (the Catalan numbers). DP. O(n²).
class Solution:
def number_of_binary_tree_topologies(self, n):
cache = [1]
for m in range(1, n + 1):
total = 0
for left in range(m):
total += cache[left] * cache[m - 1 - left]
cache.append(total)
return cache[n]Longest run of valid () parentheses. Stack of indices. O(n).
class Solution:
def longest_balanced(self, s):
stack = [-1]; longest = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack: stack.append(i)
else: longest = max(longest, i - stack[-1])
return longestFor each element, how many to its right are smaller. Insert into a sorted list from the right. O(n²) (O(n log n) with a BIT).
import bisect
class Solution:
def right_smaller_than(self, arr):
res = [0] * len(arr); sorted_seen = []
for i in range(len(arr) - 1, -1, -1):
pos = bisect.bisect_left(sorted_seen, arr[i])
res[i] = pos
sorted_seen.insert(pos, arr[i])
return resMaximize a[i]−a[j]+a[k]−a[l] for i<j<k<l. Build four running-best arrays. O(n).
class Solution:
def maximize_expression(self, arr):
n = len(arr)
if n < 4: return 0
maxA = [arr[0]] * n
for i in range(1, n): maxA[i] = max(maxA[i-1], arr[i])
maxAB = [float("-inf")] * n
for i in range(1, n): maxAB[i] = max(maxAB[i-1], maxA[i-1] - arr[i])
maxABC = [float("-inf")] * n
for i in range(2, n): maxABC[i] = max(maxABC[i-1], maxAB[i-1] + arr[i])
maxABCD = [float("-inf")] * n
for i in range(3, n): maxABCD[i] = max(maxABCD[i-1], maxABC[i-1] - arr[i])
return maxABCD[n-1]Max profit picking jobs (1 day each) by their deadlines within a 7-day week. Greedy by pay.
class Solution:
def optimal_freelancing(self, jobs):
LIMIT = 7
jobs.sort(key=lambda j: j["payment"], reverse=True)
taken = [False] * LIMIT; profit = 0
for job in jobs:
for day in range(min(job["deadline"], LIMIT) - 1, -1, -1):
if not taken[day]:
taken[day] = True; profit += job["payment"]; break
return profitBuild a balanced BST from a sorted array — recurse on the middle. O(n).
class Solution:
def min_height_bst(self, arr):
def build(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = BST(arr[mid])
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(arr) - 1)Reverse in-order (right, node, left) gives values largest-first. O(h+k).
class Solution:
def kth_largest_bst(self, root, k):
stack = []; node = root; count = 0
while stack or node:
while node:
stack.append(node); node = node.right
node = stack.pop(); count += 1
if count == k: return node.value
node = node.leftclass Solution:
def reconstruct_bst(self, preorder):
idx = [0]
def build(bound=float("inf")):
if idx[0] == len(preorder) or preorder[idx[0]] >= bound:
return None
val = preorder[idx[0]]; idx[0] += 1
node = BST(val)
node.left = build(val)
node.right = build(bound)
return node
return build()class Solution:
def find_successor(self, node):
if node.right: # leftmost of the right subtree
node = node.right
while node.left: node = node.left
return node
while node.parent and node.parent.right == node:
node = node.parent # climb until we go up-left
return node.parentclass Solution:
def merge_trees(self, t1, t2):
if not t1: return t2
if not t2: return t1
t1.value += t2.value
t1.left = self.merge_trees(t1.left, t2.left)
t1.right = self.merge_trees(t1.right, t2.right)
return t1Do two trees have the same left-to-right leaf sequence?
class Solution:
def compare_leaf_traversal(self, t1, t2):
def leaves(node, out):
if not node: return
if not node.left and not node.right:
out.append(node.value); return
leaves(node.left, out); leaves(node.right, out)
a, b = [], []
leaves(t1, a); leaves(t2, b)
return a == bAll nodes exactly k edges from a target. Map parents, then BFS treating the tree as a graph. O(n).
from collections import deque
class Solution:
def find_nodes_distance_k(self, tree, target, k):
parents = {}
def map_parents(node, parent=None):
if not node: return
parents[node.value] = parent
map_parents(node.left, node); map_parents(node.right, node)
def find(node):
if not node or node.value == target: return node
return find(node.left) or find(node.right)
map_parents(tree)
start = find(tree)
queue = deque([(start, 0)]); seen = {start.value}; res = []
while queue:
node, dist = queue.popleft()
if dist == k: res.append(node.value); continue
for nb in (node.left, node.right, parents[node.value]):
if nb and nb.value not in seen:
seen.add(nb.value); queue.append((nb, dist + 1))
return resPick one negative (sweet) + one positive (savory) dish with sum closest to target without exceeding it. Two pointers. O(n log n).
class Solution:
def sweet_and_savory(self, dishes, target):
sweet = sorted(d for d in dishes if d < 0)
savory = sorted(d for d in dishes if d > 0)
best = [0, 0]; best_diff = float("inf")
i, j = 0, len(savory) - 1
while i < len(sweet) and j >= 0:
total = sweet[i] + savory[j]
if total > target:
j -= 1
else:
if target - total < best_diff:
best_diff = target - total; best = [sweet[i], savory[j]]
i += 1
return bestWrap every occurrence of a substring with underscores, merging overlaps. O(n+m).
class Solution:
def underscorify_substring(self, string, substring):
locs = []; start = 0
while True:
i = string.find(substring, start)
if i == -1: break
locs.append([i, i + len(substring)]); start = i + 1
merged = []
for loc in locs:
if merged and loc[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], loc[1])
else: merged.append(loc)
out = []; m = 0
for i in range(len(string) + 1):
if m < len(merged) and i == merged[m][0]: out.append("_")
if m < len(merged) and i == merged[m][1]: out.append("_"); m += 1
if i < len(string): out.append(string[i])
return "".join(out)Which small strings appear inside the big string? Build a trie of the big string's suffixes.
class Solution:
def multi_string_search(self, big, small):
trie = {}
for i in range(len(big)): # all suffixes
node = trie
for ch in big[i:]:
node = node.setdefault(ch, {})
def contains(word):
node = trie
for ch in word:
if ch not in node: return False
node = node[ch]
return True
return [contains(w) for w in small]Click a cell: a mine → "X"; otherwise show the mine count, and flood-fill zeros. "M"=mine, "H"=hidden.
class Solution:
def reveal_minesweeper(self, board, row, col):
if board[row][col] == "M":
board[row][col] = "X"; return board
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
def mines(r, c):
return sum(1 for dr, dc in dirs
if 0 <= r+dr < len(board) and 0 <= c+dc < len(board[0])
and board[r+dr][c+dc] == "M")
stack = [(row, col)]
while stack:
r, c = stack.pop()
if board[r][c] != "H": continue
n = mines(r, c)
board[r][c] = str(n) if n > 0 else "0"
if n == 0:
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0 <= nr < len(board) and 0 <= nc < len(board[0]) and board[nr][nc] == "H":
stack.append((nr, nc))
return boardAn in-order walk of a BST is sorted — the two out-of-order nodes are the swapped pair. O(n).
class Solution:
def repair_bst(self, tree):
first = second = prev = None
def inorder(node):
nonlocal first, second, prev
if not node: return
inorder(node.left)
if prev and prev.value > node.value:
if not first: first = prev
second = node
prev = node
inorder(node.right)
inorder(tree)
first.value, second.value = second.value, first.value
return treeIs the middle node a descendant of one outer node and an ancestor of the other? O(h).
class Solution:
def validate_three_nodes(self, one, two, three):
def is_descendant(node, target):
while node and node != target:
node = node.left if target.value < node.value else node.right
return node == target
if is_descendant(two, one): return is_descendant(three, two)
if is_descendant(two, three): return is_descendant(one, two)
return FalseMin total moves for two knights to land on the same square. BFS from one; they move alternately.
from collections import deque
class Solution:
def knight_connection(self, a, b):
moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
q = deque([(a[0], a[1], 0)]); seen = {tuple(a)}
while q:
r, c, d = q.popleft()
if [r, c] == b: return (d + 1) // 2
for dr, dc in moves:
nxt = (r + dr, c + dc)
if nxt not in seen:
seen.add(nxt); q.append((nxt[0], nxt[1], d + 1))Max points on a single straight line. Group by reduced slope (use gcd to normalize). O(n²).
from math import gcd
class Solution:
def line_through_points(self, points):
best = 1
for i in range(len(points)):
slopes = {}
for j in range(i + 1, len(points)):
dx = points[j][0] - points[i][0]
dy = points[j][1] - points[i][1]
g = gcd(dx, dy) or 1
slope = (dx // g, dy // g)
slopes[slope] = slopes.get(slope, 1) + 1
best = max(best, slopes[slope])
return bestMatch interns ↔ teams so no pair would both rather swap. The classic stable-matching algorithm.
class Solution:
def stable_internships(self, interns, teams):
chosen = {} # team -> intern
free = list(range(len(interns)))
next_choice = [0] * len(interns)
while free:
intern = free.pop(0)
team = interns[intern][next_choice[intern]]
next_choice[intern] += 1
if team not in chosen:
chosen[team] = intern
else:
current = chosen[team]; pref = teams[team]
if pref.index(intern) < pref.index(current):
chosen[team] = intern; free.append(current)
else:
free.append(intern)
return [[team, intern] for team, intern in chosen.items()]Shortest prefix of each word that no other word shares. Trie with counts. O(total chars).
class Solution:
def shortest_unique_prefixes(self, strings):
trie = {}
for s in strings: # build trie, counting visits
node = trie
for ch in s:
node = node.setdefault(ch, {"count": 0})
node["count"] += 1
res = []
for s in strings:
node = trie; prefix = ""
for ch in s:
node = node[ch]; prefix += ch
if node["count"] == 1: break # unique from here
res.append(prefix)
return resIs there a square whose border is all 0s? Precompute consecutive zeros right/down, then check each square. O(n³).
class Solution:
def square_of_zeroes(self, matrix):
n = len(matrix)
info = [[[0, 0] for _ in range(n)] for _ in range(n)] # [right, down]
for r in range(n - 1, -1, -1):
for c in range(n - 1, -1, -1):
if matrix[r][c] == 0:
info[r][c][0] = 1 + (info[r][c+1][0] if c+1 < n else 0)
info[r][c][1] = 1 + (info[r+1][c][1] if r+1 < n else 0)
for r in range(n):
for c in range(n):
for size in range(2, n - max(r, c) + 1):
br, bc = r + size - 1, c + size - 1
if (info[r][c][0] >= size and info[r][c][1] >= size and
info[r][bc][1] >= size and info[br][c][0] >= size):
return True
return FalseMin possible max-station-time when splitting ordered steps across k stations. Binary-search the answer. O(n log(sum)).
class Solution:
def optimal_assembly_line(self, durations, num_stations):
def feasible(max_time):
used, current = 1, 0
for d in durations:
if d > max_time: return False
if current + d > max_time: used += 1; current = d
else: current += d
return used <= num_stations
lo, hi, best = max(durations), sum(durations), sum(durations)
while lo <= hi:
mid = (lo + hi) // 2
if feasible(mid): best = mid; hi = mid - 1
else: lo = mid + 1
return bestGiven a pattern of x's & y's, find strings for x and y that rebuild s. Try every length of x. O(n²).
class Solution:
def pattern_matcher(self, pattern, s):
if len(pattern) > len(s): return []
swapped = pattern[0] != "x"
p = ["x" if c == "y" else "y" for c in pattern] if swapped else list(pattern)
cx, cy = p.count("x"), p.count("y")
first_y = p.index("y") if cy else None
if cy:
for lx in range(1, len(s) // cx + 1):
rem = len(s) - lx * cx
if rem % cy: continue
ly = rem // cy
yi = first_y * lx
x, y = s[:lx], s[yi:yi + ly]
if "".join(x if c == "x" else y for c in p) == s:
return [y, x] if swapped else [x, y]
else:
if len(s) % cx: return []
x = s[: len(s) // cx]
if x * cx == s:
return ["", x] if swapped else [x, ""]
return []Rewire every node's right to point to its sibling on the same level. Recurse left before mutating right.
class Solution:
def right_sibling_tree(self, root):
def mutate(node, parent, is_left):
if node is None: return
left, right = node.left, node.right
mutate(left, node, True)
if parent is None: node.right = None
elif is_left: node.right = parent.right
else: node.right = parent.right.left if parent.right else None
mutate(right, node, False)
mutate(root, None, False)
return rootFewest new routes so every airport is reachable from the start. Score unreachable airports by how many other unreachable ones they unlock; add greedily.
class Solution:
def airport_connections(self, airports, routes, start):
graph = {a: [] for a in airports}
for src, dst in routes: graph[src].append(dst)
reachable = set()
def dfs(node):
if node in reachable: return
reachable.add(node)
for nb in graph[node]: dfs(nb)
dfs(start)
def reach_count(node, seen):
if node in seen: return 0
seen.add(node)
total = 0 if node in reachable else 1
for nb in graph[node]: total += reach_count(nb, seen)
return total
scored = sorted(((a, reach_count(a, set())) for a in airports if a not in reachable),
key=lambda x: -x[1])
connections = 0
for airport, _ in scored:
if airport in reachable: continue
connections += 1
dfs(airport)
return connectionsBiggest rectangle of empty land (0s) in a grid. Row-by-row histogram + largest-rectangle. O(rows·cols).
class Solution:
def largest_park(self, land):
cols = len(land[0]); heights = [0] * cols; best = 0
for row in land:
for c in range(cols):
heights[c] = 0 if row[c] == 1 else heights[c] + 1
stack = [] # largest rectangle in histogram
for i in range(cols + 1):
h = heights[i] if i < cols else 0
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return bestCan one cut split the tree into two equal-sum halves? Returns that half-sum or 0.
class Solution:
def split_binary_tree(self, tree):
def total(node):
return 0 if not node else node.value + total(node.left) + total(node.right)
whole = total(tree)
if whole % 2: return 0
found = [False]
def helper(node):
if not node: return 0
s = node.value + helper(node.left) + helper(node.right)
if s == whole // 2: found[0] = True
return s
helper(tree)
return whole // 2 if found[0] else 0class Solution:
def count_bsts(self, tree):
count = [0]
def helper(node): # returns (is_bst, min, max)
if not node: return (True, float("inf"), float("-inf"))
lb, lmin, lmax = helper(node.left)
rb, rmin, rmax = helper(node.right)
is_bst = lb and rb and lmax < node.value < rmin
if is_bst: count[0] += 1
return (is_bst, min(lmin, node.value), max(rmax, node.value))
helper(tree)
return count[0]Where two lists join. Swap each pointer to the other list's head when it ends — they meet at the join. O(n).
class Solution:
def merging_linked_lists(self, l1, l2):
a, b = l1, l2
while a != b:
a = a.next if a else l2
b = b.next if b else l1
return a # the shared node (or None)class DLL:
def __init__(self): self.head = self.tail = None
def set_head(self, node):
if not self.head: self.head = self.tail = node; return
self.insert_before(self.head, node)
def insert_before(self, node, new):
self.remove(new)
new.prev, new.next = node.prev, node
if node.prev is None: self.head = new
else: node.prev.next = new
node.prev = new
def remove(self, node):
if node is self.head: self.head = node.next
if node is self.tail: self.tail = node.prev
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
node.prev = node.next = Noneclass MinHeap:
def __init__(self, array):
self.heap = array
for i in range((len(array) - 2) // 2, -1, -1): # heapify, O(n)
self.sift_down(i)
def sift_down(self, i):
n = len(self.heap)
while 2*i + 1 < n:
child = 2*i + 1
if 2*i + 2 < n and self.heap[2*i+2] < self.heap[child]:
child = 2*i + 2
if self.heap[child] < self.heap[i]:
self.heap[i], self.heap[child] = self.heap[child], self.heap[i]; i = child
else: break
def sift_up(self, i):
while i > 0 and self.heap[i] < self.heap[(i-1)//2]:
self.heap[i], self.heap[(i-1)//2] = self.heap[(i-1)//2], self.heap[i]; i = (i-1)//2
def insert(self, v):
self.heap.append(v); self.sift_up(len(self.heap) - 1)
def remove(self):
self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
v = self.heap.pop(); self.sift_down(0); return vSplit N liters into bottle sizes to maximize total price (like rod-cutting), returning the split. O(n²).
class Solution:
def juice_bottling(self, prices):
n = len(prices) - 1
dp = [0] * len(prices); splits = [[] for _ in prices]
for size in range(1, len(prices)):
for liters in range(1, size + 1):
if dp[size - liters] + prices[liters] > dp[size]:
dp[size] = dp[size - liters] + prices[liters]
splits[size] = splits[size - liters] + [liters]
return splits[n]Chance the dealer busts (goes over the target). Dealer draws (cards 1–10) until within 4 of target. Memoized.
class Solution:
def blackjack_probability(self, target, starting):
cache = {}
def helper(current):
if current > target: return 1.0 # busted
if current + 4 >= target: return 0.0 # dealer stands, safe
if current in cache: return cache[current]
cache[current] = sum(helper(current + d) for d in range(1, 11)) / 10
return cache[current]
return round(helper(starting), 3)Is the graph connected with no "bridge" edges (every edge lies on a cycle)? DFS arrival/low times (Tarjan). O(V+E).
class Solution:
def two_edge_connected(self, edges):
n = len(edges)
if n == 0: return True
arrival = [-1] * n
def dfs(node, prev, time):
arrival[node] = time; lowest = time
for nb in edges[node]:
if arrival[nb] == -1:
low = dfs(nb, node, time + 1)
if low == -1: return -1 # bridge below
if low <= arrival[node] and node != 0 is False: pass
lowest = min(lowest, low)
elif nb != prev:
lowest = min(lowest, arrival[nb])
if lowest == arrival[node] and node != 0: # edge to parent is a bridge
return -1
return lowest
if dfs(0, -1, 0) == -1: return False
return all(a != -1 for a in arrival) # also fully connectedDoes any subarray sum to 0? If a running sum repeats, the slice between is 0. O(n).
class Solution:
def zero_sum_subarray(self, nums):
seen = {0}; running = 0
for n in nums:
running += n
if running in seen: return True
seen.add(running)
return Falseclass Solution:
def binary_tree_diameter(self, tree):
diameter = [0]
def height(node):
if not node: return 0
lh, rh = height(node.left), height(node.right)
diameter[0] = max(diameter[0], lh + rh)
return max(lh, rh) + 1
height(tree)
return diameter[0]Each pass, positives convert their negative neighbors. How many passes to flip all? Multi-source BFS. O(w·h).
from collections import deque
class Solution:
def minimum_passes_of_matrix(self, matrix):
q = deque((r, c) for r in range(len(matrix))
for c in range(len(matrix[0])) if matrix[r][c] > 0)
passes = 0
while q:
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r+dr, c+dc
if 0 <= nr < len(matrix) and 0 <= nc < len(matrix[0]) and matrix[nr][nc] < 0:
matrix[nr][nc] *= -1; q.append((nr, nc))
passes += 1
return -1 if any(v < 0 for row in matrix for v in row) else max(passes - 1, 0)class Solution:
def best_digits(self, number, k):
stack = []
for d in number:
while k > 0 and stack and stack[-1] < d:
stack.pop(); k -= 1
stack.append(d)
return "".join(stack[:len(stack) - k]) if k else "".join(stack)Positive = moving right, negative = left. Use a stack; resolve collisions. O(n).
class Solution:
def colliding_asteroids(self, asteroids):
stack = []
for a in asteroids:
alive = True
while alive and a < 0 and stack and stack[-1] > 0:
if stack[-1] < -a: stack.pop()
elif stack[-1] == -a: stack.pop(); alive = False
else: alive = False
if alive: stack.append(a)
return stackfrom collections import Counter
class Solution:
def minimum_characters_for_words(self, words):
max_counts = {}
for word in words:
for ch, cnt in Counter(word).items():
max_counts[ch] = max(max_counts.get(ch, 0), cnt)
out = []
for ch, cnt in max_counts.items(): out += [ch] * cnt
return outHow many squares can be formed from a set of points? Check each pair as a diagonal. O(n²).
class Solution:
def count_squares(self, points):
pts = {(x, y) for x, y in points}; count = 0
for x1, y1 in points:
for x2, y2 in points:
if (x1, y1) == (x2, y2): continue
mx, my = (x1 + x2) / 2, (y1 + y2) / 2
dx, dy = x1 - mx, y1 - my
if (mx - dy, my + dx) in pts and (mx + dy, my - dx) in pts:
count += 1
return count // 4 # each square counted 4×Flip one water cell to land — what's the biggest land block possible? Label regions, then test each water cell. O(w·h).
class Solution:
def largest_island(self, grid):
n, m = len(grid), len(grid[0])
rid = [[-1]*m for _ in range(n)]; sizes = {}; cur = 0
def fill(r, c, cur):
stack = [(r, c)]; size = 0
while stack:
i, j = stack.pop()
if 0<=i<n and 0<=j<m and grid[i][j]==0 and rid[i][j]==-1:
rid[i][j] = cur; size += 1
stack += [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]
return size
for r in range(n):
for c in range(m):
if grid[r][c]==0 and rid[r][c]==-1:
sizes[cur] = fill(r, c, cur); cur += 1
best = max(sizes.values(), default=0)
for r in range(n):
for c in range(m):
if grid[r][c]==1:
ids = {rid[r+dr][c+dc] for dr, dc in ((1,0),(-1,0),(0,1),(0,-1))
if 0<=r+dr<n and 0<=c+dc<m and grid[r+dr][c+dc]==0}
best = max(best, 1 + sum(sizes[i] for i in ids))
return bestEvery element is at most k spots from its sorted position. A size-(k+1) min-heap. O(n log k).
import heapq
class Solution:
def sort_k_sorted(self, array, k):
heap = array[:k+1]; heapq.heapify(heap); idx = 0
for i in range(k+1, len(array)):
array[idx] = heapq.heappop(heap); idx += 1
heapq.heappush(heap, array[i])
while heap:
array[idx] = heapq.heappop(heap); idx += 1
return arrayimport heapq
class Solution:
def merge_sorted_arrays(self, arrays):
heap = [(arr[0], i, 0) for i, arr in enumerate(arrays) if arr]
heapq.heapify(heap); res = []
while heap:
val, a, e = heapq.heappop(heap); res.append(val)
if e + 1 < len(arrays[a]):
heapq.heappush(heap, (arrays[a][e+1], a, e+1))
return resRotate a list by k. Make it circular, then break it at the right spot. O(n).
class Solution:
def shift_linked_list(self, head, k):
length = 1; tail = head
while tail.next: tail = tail.next; length += 1
k %= length
if k == 0: return head
tail.next = head # circular
new_tail = head
for _ in range(length - k - 1): new_tail = new_tail.next
new_head = new_tail.next; new_tail.next = None
return new_headLCA on an org chart (n-ary tree, no parent links). Count how many of the two appear in each subtree. O(n).
class Solution:
def lowest_common_manager(self, top, one, two):
def helper(manager):
count = 0
for report in manager.direct_reports:
found, lca = helper(report)
if lca: return 0, lca
count += found
if manager in (one, two): count += 1
return count, (manager if count == 2 else None)
return helper(top)[1]Can imprecise measuring cups produce a target range? Memoized recursion.
class Solution:
def ambiguous_measurements(self, cups, low, high):
cache = {}
def can(low, high):
if low <= 0 and high <= 0: return False
if (low, high) in cache: return cache[(low, high)]
result = False
for cl, ch in cups:
if low <= cl and ch <= high:
result = True; break
if can(max(0, low - cl), max(0, high - ch)):
result = True; break
cache[(low, high)] = result
return result
return can(low, high)Simplify a Unix-style path (handle ., .., extra slashes). Stack. O(n).
class Solution:
def shorten_path(self, path):
is_abs = path[0] == "/"
tokens = [t for t in path.split("/") if t and t != "."]
stack = [""] if is_abs else []
for t in tokens:
if t == "..":
if not stack or stack[-1] == "..":
if not is_abs: stack.append(t)
elif stack[-1] != "":
stack.pop()
else:
stack.append(t)
if stack == [""]: return "/"
return "/".join(stack)Reorder so everything < k comes before == k before > k. Build three sublists, then stitch. O(n).
class Solution:
def rearrange_linked_list(self, head, k):
parts = {"less": [None, None], "equal": [None, None], "greater": [None, None]}
node = head
while node:
nxt = node.next; node.next = None
b = "less" if node.value < k else "greater" if node.value > k else "equal"
h, t = parts[b]
if not h: parts[b] = [node, node]
else: t.next = node; parts[b][1] = node
node = nxt
new_head = prev_tail = None
for h, t in (parts["less"], parts["equal"], parts["greater"]):
if h is None: continue
if new_head is None: new_head = h
if prev_tail: prev_tail.next = h
prev_tail = t
return new_headMin laptops for overlapping rental times. Sort starts & ends, sweep with two pointers. O(n log n).
class Solution:
def laptop_rentals(self, times):
if not times: return 0
starts = sorted(t[0] for t in times)
ends = sorted(t[1] for t in times)
used = max_used = s = e = 0
while s < len(starts):
if starts[s] < ends[e]:
used += 1; s += 1; max_used = max(max_used, used)
else:
used -= 1; e += 1
return max_usedWhich big strings can be built by concatenating the smaller ones (word-break)? DP per string. O(n·L²).
class Solution:
def strings_made_up_of_strings(self, strings, substrings):
subs = set(substrings)
max_len = max((len(s) for s in substrings), default=0)
out = []
for s in strings:
n = len(s); dp = [False] * (n + 1); dp[0] = True
for i in range(1, n + 1):
for j in range(max(0, i - max_len), i):
if dp[j] and s[j:i] in subs:
dp[i] = True; break
if dp[n]: out.append(s)
return outLongest prefix shared by the most strings. Build a counting trie, then follow the most-visited path. O(total chars).
class Solution:
def longest_most_frequent_prefix(self, strings):
trie = {}
for s in strings:
node = trie
for ch in s:
node = node.setdefault(ch, {"_count": 0})
node["_count"] += 1
best_count = len(strings)
node = trie; prefix = ""
while True:
nxt = next(((ch, c) for ch, c in node.items()
if ch != "_count" and c["_count"] == best_count), None)
if not nxt: break
prefix += nxt[0]; node = nxt[1]
return prefixWater poured at a source flows down, splitting 50/50 around walls (1s). Return how much reaches each bottom slot. Row-by-row simulation; carry % as negatives.
class Solution:
def waterfall_streams(self, array, source):
rows = [r[:] for r in array]
rows[0][source] = -1 # -1 == 100% water
for r in range(len(rows) - 1):
for c in range(len(rows[r])):
cur = rows[r][c]
if cur >= 0: continue # no water here
if rows[r+1][c] == 0: # falls straight down
rows[r+1][c] += cur; continue
split = cur / 2 # blocked → split left/right
left = c
while left - 1 >= 0:
left -= 1
if rows[r][left] == 1: break
if rows[r+1][left] == 0: rows[r+1][left] += split; break
right = c
while right + 1 < len(rows[r]):
right += 1
if rows[r][right] == 1: break
if rows[r+1][right] == 0: rows[r+1][right] += split; break
return [(-v) * 100 if v < 0 else 0 for v in rows[-1]]Merge nums2 into nums1 in place — fill from the back to avoid overwriting. O(m+n).
class Solution:
def merge(self, nums1, m, nums2, n):
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]; i -= 1
else:
nums1[k] = nums2[j]; j -= 1
k -= 1class Solution:
def remove_element(self, nums, val):
k = 0
for n in nums:
if n != val: nums[k] = n; k += 1
return kclass Solution:
def remove_duplicates(self, nums):
if not nums: return 0
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k-1]:
nums[k] = nums[i]; k += 1
return kclass Solution:
def remove_duplicates_ii(self, nums):
k = 0
for n in nums:
if k < 2 or n != nums[k-2]:
nums[k] = n; k += 1
return kclass Solution:
def majority_element(self, nums):
count = 0; cand = None
for n in nums:
if count == 0: cand = n
count += 1 if n == cand else -1
return candclass Solution:
def rotate(self, nums, k):
k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]class Solution:
def max_profit(self, prices):
min_price = float("inf"); profit = 0
for p in prices:
min_price = min(min_price, p)
profit = max(profit, p - min_price)
return profitUnlimited trades → grab every upward step. O(n).
class Solution:
def max_profit_ii(self, prices):
return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))class Solution:
def can_jump(self, nums):
reach = 0
for i, n in enumerate(nums):
if i > reach: return False
reach = max(reach, i + n)
return Trueclass Solution:
def jump(self, nums):
jumps = end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == end:
jumps += 1; end = farthest
return jumpsclass Solution:
def h_index(self, citations):
citations.sort(reverse=True)
h = 0
for i, c in enumerate(citations):
if c >= i + 1: h = i + 1
else: break
return hArray for O(1) random + dict of value→index; on remove, swap with the last element.
import random
class RandomizedSet:
def __init__(self):
self.data = []; self.idx = {}
def insert(self, val):
if val in self.idx: return False
self.idx[val] = len(self.data); self.data.append(val); return True
def remove(self, val):
if val not in self.idx: return False
i = self.idx[val]; last = self.data[-1]
self.data[i] = last; self.idx[last] = i
self.data.pop(); del self.idx[val]; return True
def getRandom(self):
return random.choice(self.data)Prefix products left-to-right, then multiply by suffix products right-to-left. No division. O(n).
class Solution:
def product_except_self(self, nums):
n = len(nums); res = [1] * n
left = 1
for i in range(n):
res[i] = left; left *= nums[i]
right = 1
for i in range(n - 1, -1, -1):
res[i] *= right; right *= nums[i]
return resclass Solution:
def can_complete_circuit(self, gas, cost):
if sum(gas) < sum(cost): return -1
total = start = 0
for i in range(len(gas)):
total += gas[i] - cost[i]
if total < 0: total = 0; start = i + 1
return startTwo passes: reward left-to-right for rising ratings, then right-to-left. O(n).
class Solution:
def candy(self, ratings):
n = len(ratings); c = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i-1]: c[i] = c[i-1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i+1]: c[i] = max(c[i], c[i+1] + 1)
return sum(c)class Solution:
def trap(self, height):
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]; left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]; right -= 1
return waterclass Solution:
def roman_to_int(self, s):
v = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
total = 0
for i in range(len(s)):
if i + 1 < len(s) and v[s[i]] < v[s[i+1]]: total -= v[s[i]]
else: total += v[s[i]]
return totalclass Solution:
def int_to_roman(self, num):
vals = [(1000,"M"),(900,"CM"),(500,"D"),(400,"CD"),(100,"C"),(90,"XC"),
(50,"L"),(40,"XL"),(10,"X"),(9,"IX"),(5,"V"),(4,"IV"),(1,"I")]
res = []
for v, sym in vals:
while num >= v: res.append(sym); num -= v
return "".join(res)class Solution:
def length_of_last_word(self, s):
parts = s.split()
return len(parts[-1]) if parts else 0class Solution:
def longest_common_prefix(self, strs):
if not strs: return ""
prefix = strs[0]
for s in strs[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1]
if not prefix: return ""
return prefixclass Solution:
def reverse_words(self, s):
return " ".join(s.split()[::-1])class Solution:
def convert(self, s, num_rows):
if num_rows == 1: return s
rows = [""] * num_rows
r, step = 0, 1
for c in s:
rows[r] += c
if r == 0: step = 1
elif r == num_rows - 1: step = -1
r += step
return "".join(rows)class Solution:
def str_str(self, haystack, needle):
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i:i+m] == needle: return i
return -1Greedily pack words per line, then distribute spaces evenly (extra spaces go to the left gaps); last line is left-justified.
class Solution:
def full_justify(self, words, max_width):
res = []; line = []; length = 0
for w in words:
if length + len(line) + len(w) > max_width:
slots = max(1, len(line) - 1)
for i in range(max_width - length):
line[i % slots] += " "
res.append("".join(line)); line = []; length = 0
line.append(w); length += len(w)
res.append(" ".join(line).ljust(max_width))
return resclass Solution:
def is_palindrome(self, s):
cleaned = [c.lower() for c in s if c.isalnum()]
return cleaned == cleaned[::-1]class Solution:
def is_subsequence(self, s, t):
i = 0
for c in t:
if i < len(s) and s[i] == c: i += 1
return i == len(s)class Solution:
def two_sum_ii(self, numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target: return [lo + 1, hi + 1]
if s < target: lo += 1
else: hi -= 1class Solution:
def max_area(self, height):
lo, hi, best = 0, len(height) - 1, 0
while lo < hi:
best = max(best, min(height[lo], height[hi]) * (hi - lo))
if height[lo] < height[hi]: lo += 1
else: hi -= 1
return bestSort, fix one number, then two-pointer the rest. Skip duplicates. O(n²).
class Solution:
def three_sum(self, nums):
nums.sort(); res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0: lo += 1
elif s > 0: hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1; hi -= 1
while lo < hi and nums[lo] == nums[lo-1]: lo += 1
while lo < hi and nums[hi] == nums[hi+1]: hi -= 1
return resclass Solution:
def min_subarray_len(self, target, nums):
left = total = 0; best = float("inf")
for right in range(len(nums)):
total += nums[right]
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]; left += 1
return best if best != float("inf") else 0class Solution:
def length_of_longest_substring(self, s):
seen = {}; left = best = 0
for right, c in enumerate(s):
if c in seen and seen[c] >= left:
left = seen[c] + 1
seen[c] = right
best = max(best, right - left + 1)
return bestfrom collections import Counter
class Solution:
def find_substring(self, s, words):
if not words: return []
wl, n = len(words[0]), len(words); total = wl * n
need = Counter(words); res = []
for i in range(len(s) - total + 1):
seen = Counter()
for j in range(i, i + total, wl):
word = s[j:j+wl]
if word not in need: break
seen[word] += 1
if seen[word] > need[word]: break
else:
res.append(i)
return resExpand right to cover all needed chars, then shrink left while still valid. O(n).
from collections import Counter
class Solution:
def min_window(self, s, t):
need = Counter(t); missing = len(t)
left = start = 0; end = float("inf")
for right, c in enumerate(s):
if need[c] > 0: missing -= 1
need[c] -= 1
while missing == 0:
if right - left < end - start: start, end = left, right
need[s[left]] += 1
if need[s[left]] > 0: missing += 1
left += 1
return s[start:end+1] if end != float("inf") else ""class Solution:
def is_valid_sudoku(self, board):
seen = set()
for r in range(9):
for c in range(9):
v = board[r][c]
if v == ".": continue
for key in ((v, "row", r), (v, "col", c), (v, "box", r//3, c//3)):
if key in seen: return False
seen.add(key)
return TruePop the top row, rotate the rest counter-clockwise, repeat. O(m·n).
class Solution:
def spiral_order(self, matrix):
res = []
while matrix:
res += matrix.pop(0)
matrix = [list(row) for row in zip(*matrix)][::-1]
return resclass Solution:
def rotate_image(self, matrix):
matrix.reverse() # flip vertically
for i in range(len(matrix)): # then transpose
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]class Solution:
def set_zeroes(self, matrix):
rows, cols = set(), set()
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if matrix[r][c] == 0: rows.add(r); cols.add(c)
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if r in rows or c in cols: matrix[r][c] = 0Encode next state in bit 2 so neighbors still read the old state (bit 1), then shift. O(m·n), O(1) space.
class Solution:
def game_of_life(self, board):
rows, cols = len(board), len(board[0])
for r in range(rows):
for c in range(cols):
live = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
if (dr or dc) and 0 <= r+dr < rows and 0 <= c+dc < cols:
live += board[r+dr][c+dc] & 1
if board[r][c] & 1:
if live in (2, 3): board[r][c] |= 2
elif live == 3: board[r][c] |= 2
for r in range(rows):
for c in range(cols):
board[r][c] >>= 1from collections import Counter
class Solution:
def can_construct(self, ransom_note, magazine):
return not (Counter(ransom_note) - Counter(magazine))class Solution:
def is_isomorphic(self, s, t):
return len(set(s)) == len(set(t)) == len(set(zip(s, t)))class Solution:
def word_pattern(self, pattern, s):
words = s.split()
if len(pattern) != len(words): return False
return len(set(pattern)) == len(set(words)) == len(set(zip(pattern, words)))from collections import Counter
class Solution:
def is_anagram(self, s, t):
return Counter(s) == Counter(t)from collections import defaultdict
class Solution:
def group_anagrams(self, strs):
groups = defaultdict(list)
for s in strs:
groups[tuple(sorted(s))].append(s)
return list(groups.values())class Solution:
def two_sum(self, nums, target):
seen = {}
for i, n in enumerate(nums):
if target - n in seen: return [seen[target - n], i]
seen[n] = iclass Solution:
def is_happy(self, n):
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = sum(int(d) ** 2 for d in str(n))
return n == 1class Solution:
def contains_nearby_duplicate(self, nums, k):
last = {}
for i, n in enumerate(nums):
if n in last and i - last[n] <= k: return True
last[n] = i
return FalsePut all in a set; only start counting from numbers with no left neighbor. O(n).
class Solution:
def longest_consecutive(self, nums):
s = set(nums); best = 0
for n in s:
if n - 1 not in s:
length = 1
while n + length in s: length += 1
best = max(best, length)
return bestclass Solution:
def summary_ranges(self, nums):
res = []; i = 0
while i < len(nums):
start = nums[i]
while i + 1 < len(nums) and nums[i+1] == nums[i] + 1: i += 1
res.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
i += 1
return resclass Solution:
def merge_intervals(self, intervals):
intervals.sort()
res = [intervals[0]]
for s, e in intervals[1:]:
if s <= res[-1][1]: res[-1][1] = max(res[-1][1], e)
else: res.append([s, e])
return resclass Solution:
def insert_interval(self, intervals, new):
res = []; i = 0; n = len(intervals)
while i < n and intervals[i][1] < new[0]:
res.append(intervals[i]); i += 1
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]; i += 1
res.append(new)
while i < n: res.append(intervals[i]); i += 1
return resSort by end, shoot at each non-overlapping end. Greedy. O(n log n).
class Solution:
def find_min_arrow_shots(self, points):
points.sort(key=lambda p: p[1])
arrows = 1; end = points[0][1]
for s, e in points[1:]:
if s > end: arrows += 1; end = e
return arrowsclass Solution:
def is_valid(self, s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for c in s:
if c in pairs:
if not stack or stack.pop() != pairs[c]: return False
else:
stack.append(c)
return not stackclass Solution:
def simplify_path(self, path):
stack = []
for part in path.split("/"):
if part in ("", "."): continue
if part == "..":
if stack: stack.pop()
else: stack.append(part)
return "/" + "/".join(stack)class MinStack:
def __init__(self): self.stack = []
def push(self, val):
m = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, m))
def pop(self): self.stack.pop()
def top(self): return self.stack[-1][0]
def getMin(self): return self.stack[-1][1]class Solution:
def eval_rpn(self, tokens):
stack = []
ops = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
"*": lambda a, b: a * b, "/": lambda a, b: int(a / b)}
for t in tokens:
if t in ops:
b = stack.pop(); a = stack.pop(); stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]Handle + - ( ). Push the running result & sign on (, fold back on ). O(n).
class Solution:
def calculate(self, s):
stack = []; result = 0; num = 0; sign = 1
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c in "+-":
result += sign * num; num = 0
sign = 1 if c == "+" else -1
elif c == "(":
stack.append(result); stack.append(sign)
result = 0; sign = 1
elif c == ")":
result += sign * num; num = 0
result = result * stack.pop() + stack.pop() # sign, then prev result
return result + sign * numclass Solution:
def has_cycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
if slow == fast: return True
return Falseclass Solution:
def add_two_numbers(self, l1, l2):
dummy = ListNode(0); cur = dummy; carry = 0
while l1 or l2 or carry:
total = carry
if l1: total += l1.val; l1 = l1.next
if l2: total += l2.val; l2 = l2.next
carry, digit = divmod(total, 10)
cur.next = ListNode(digit); cur = cur.next
return dummy.nextclass Solution:
def merge_two_lists(self, l1, l2):
dummy = ListNode(0); tail = dummy
while l1 and l2:
if l1.val <= l2.val: tail.next = l1; l1 = l1.next
else: tail.next = l2; l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.nextMap each old node to its clone, then wire up next/random. O(n).
class Solution:
def copy_random_list(self, head):
if not head: return None
clone = {}
cur = head
while cur:
clone[cur] = Node(cur.val); cur = cur.next
cur = head
while cur:
clone[cur].next = clone.get(cur.next)
clone[cur].random = clone.get(cur.random)
cur = cur.next
return clone[head]class Solution:
def reverse_between(self, head, left, right):
dummy = ListNode(0, head); prev = dummy
for _ in range(left - 1): prev = prev.next
cur = prev.next
for _ in range(right - left):
nxt = cur.next
cur.next = nxt.next
nxt.next = prev.next
prev.next = nxt
return dummy.nextclass Solution:
def reverse_k_group(self, head, k):
node = head
for _ in range(k): # need k nodes
if not node: return head
node = node.next
prev = None; cur = head
for _ in range(k):
nxt = cur.next; cur.next = prev; prev = cur; cur = nxt
head.next = self.reverse_k_group(cur, k)
return prevclass Solution:
def remove_nth_from_end(self, head, n):
dummy = ListNode(0, head); fast = slow = dummy
for _ in range(n): fast = fast.next
while fast.next:
fast = fast.next; slow = slow.next
slow.next = slow.next.next
return dummy.nextclass Solution:
def delete_duplicates_ii(self, head):
dummy = ListNode(0, head); prev = dummy; cur = head
while cur:
if cur.next and cur.val == cur.next.val:
while cur.next and cur.val == cur.next.val: cur = cur.next
prev.next = cur.next
else:
prev = prev.next
cur = cur.next
return dummy.nextclass Solution:
def rotate_right(self, head, k):
if not head or not head.next: return head
n = 1; tail = head
while tail.next: tail = tail.next; n += 1
k %= n
if k == 0: return head
tail.next = head # circular
new_tail = head
for _ in range(n - k - 1): new_tail = new_tail.next
new_head = new_tail.next; new_tail.next = None
return new_headclass Solution:
def partition(self, head, x):
less = ListNode(0); greater = ListNode(0)
lt, gt = less, greater
while head:
if head.val < x: lt.next = head; lt = lt.next
else: gt.next = head; gt = gt.next
head = head.next
gt.next = None; lt.next = greater.next
return less.nextAn OrderedDict gives O(1) get/put with recency tracking (move_to_end).
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict(); self.cap = capacity
def get(self, key):
if key not in self.cache: return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache: self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False)class Solution:
def max_depth(self, root):
if not root: return 0
return 1 + max(self.max_depth(root.left), self.max_depth(root.right))class Solution:
def is_same_tree(self, p, q):
if not p and not q: return True
if not p or not q or p.val != q.val: return False
return self.is_same_tree(p.left, q.left) and self.is_same_tree(p.right, q.right)class Solution:
def invert_tree(self, root):
if root:
root.left, root.right = self.invert_tree(root.right), self.invert_tree(root.left)
return rootclass Solution:
def is_symmetric(self, root):
def mirror(a, b):
if not a and not b: return True
if not a or not b or a.val != b.val: return False
return mirror(a.left, b.right) and mirror(a.right, b.left)
return mirror(root, root)First preorder value is the root; its index in inorder splits left/right. O(n).
class Solution:
def build_tree(self, preorder, inorder):
idx = {v: i for i, v in enumerate(inorder)}
pre = [0]
def build(lo, hi):
if lo > hi: return None
val = preorder[pre[0]]; pre[0] += 1
node = TreeNode(val); mid = idx[val]
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(inorder) - 1)class Solution:
def build_tree_post(self, inorder, postorder):
idx = {v: i for i, v in enumerate(inorder)}
post = [len(postorder) - 1]
def build(lo, hi):
if lo > hi: return None
val = postorder[post[0]]; post[0] -= 1
node = TreeNode(val); mid = idx[val]
node.right = build(mid + 1, hi) # right before left (postorder reversed)
node.left = build(lo, mid - 1)
return node
return build(0, len(inorder) - 1)Use the already-linked current level to build the next level's next chain. O(n), O(1) extra.
class Solution:
def connect(self, root):
head = root
while head:
dummy = Node(0); tail = dummy; cur = head
while cur:
if cur.left: tail.next = cur.left; tail = tail.next
if cur.right: tail.next = cur.right; tail = tail.next
cur = cur.next
head = dummy.next
return rootclass Solution:
def flatten(self, root):
node = root
while node:
if node.left:
rightmost = node.left
while rightmost.right: rightmost = rightmost.right
rightmost.right = node.right
node.right = node.left; node.left = None
node = node.rightclass Solution:
def has_path_sum(self, root, target):
if not root: return False
if not root.left and not root.right: return root.val == target
rem = target - root.val
return self.has_path_sum(root.left, rem) or self.has_path_sum(root.right, rem)class Solution:
def sum_numbers(self, root):
def dfs(node, cur):
if not node: return 0
cur = cur * 10 + node.val
if not node.left and not node.right: return cur
return dfs(node.left, cur) + dfs(node.right, cur)
return dfs(root, 0)class Solution:
def max_path_sum(self, root):
best = [float("-inf")]
def gain(node):
if not node: return 0
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
best[0] = max(best[0], node.val + left + right)
return node.val + max(left, right)
gain(root)
return best[0]class BSTIterator:
def __init__(self, root):
self.stack = []
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node); node = node.left
def next(self):
node = self.stack.pop()
self._push_left(node.right)
return node.val
def hasNext(self):
return bool(self.stack)If left and right heights match, it's a perfect subtree → 2^h − 1. Otherwise recurse. O(log²n).
class Solution:
def count_nodes(self, root):
if not root: return 0
lh = rh = 0; l = r = root
while l: lh += 1; l = l.left
while r: rh += 1; r = r.right
if lh == rh: return (1 << lh) - 1
return 1 + self.count_nodes(root.left) + self.count_nodes(root.right)class Solution:
def lowest_common_ancestor(self, root, p, q):
if not root or root == p or root == q: return root
left = self.lowest_common_ancestor(root.left, p, q)
right = self.lowest_common_ancestor(root.right, p, q)
if left and right: return root
return left or rightfrom collections import deque
class Solution:
def right_side_view(self, root):
if not root: return []
res = []; queue = deque([root])
while queue:
n = len(queue)
for i in range(n):
node = queue.popleft()
if i == n - 1: res.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return resfrom collections import deque
class Solution:
def average_of_levels(self, root):
res = []; queue = deque([root])
while queue:
n = len(queue); total = 0
for _ in range(n):
node = queue.popleft(); total += node.val
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
res.append(total / n)
return resfrom collections import deque
class Solution:
def level_order(self, root):
if not root: return []
res = []; queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft(); level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
res.append(level)
return resfrom collections import deque
class Solution:
def zigzag_level_order(self, root):
if not root: return []
res = []; queue = deque([root]); ltr = True
while queue:
level = deque()
for _ in range(len(queue)):
node = queue.popleft()
if ltr: level.append(node.val)
else: level.appendleft(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
res.append(list(level)); ltr = not ltr
return resIn-order visits values sorted → the min gap is between adjacent values. O(n).
class Solution:
def get_minimum_difference(self, root):
prev = [None]; best = [float("inf")]
def inorder(node):
if not node: return
inorder(node.left)
if prev[0] is not None:
best[0] = min(best[0], node.val - prev[0])
prev[0] = node.val
inorder(node.right)
inorder(root)
return best[0]class Solution:
def kth_smallest(self, root, k):
stack = []; node = root
while stack or node:
while node:
stack.append(node); node = node.left
node = stack.pop(); k -= 1
if k == 0: return node.val
node = node.rightclass Solution:
def is_valid_bst(self, root):
def valid(node, low, high):
if not node: return True
if not (low < node.val < high): return False
return valid(node.left, low, node.val) and valid(node.right, node.val, high)
return valid(root, float("-inf"), float("inf"))class Solution:
def num_islands(self, grid):
if not grid: return 0
count = 0
def sink(r, c):
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == "1":
grid[r][c] = "0"
sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == "1":
count += 1; sink(r, c)
return countAny 'O' connected to the border survives — mark those first, flip the rest. O(m·n).
class Solution:
def surrounded(self, board):
if not board: return
rows, cols = len(board), len(board[0])
def mark(r, c):
if 0 <= r < rows and 0 <= c < cols and board[r][c] == "O":
board[r][c] = "#"
mark(r+1, c); mark(r-1, c); mark(r, c+1); mark(r, c-1)
for r in range(rows): mark(r, 0); mark(r, cols-1)
for c in range(cols): mark(0, c); mark(rows-1, c)
for r in range(rows):
for c in range(cols):
board[r][c] = "O" if board[r][c] == "#" else "X"class Solution:
def clone_graph(self, node):
if not node: return None
clones = {}
def dfs(n):
if n in clones: return clones[n]
copy = Node(n.val); clones[n] = copy
for nb in n.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)Build a weighted graph (a/b = v, b/a = 1/v); each query is a DFS multiplying edge weights.
from collections import defaultdict
class Solution:
def calc_equation(self, equations, values, queries):
graph = defaultdict(dict)
for (a, b), v in zip(equations, values):
graph[a][b] = v; graph[b][a] = 1 / v
def dfs(src, dst, seen):
if src not in graph or dst not in graph: return -1.0
if src == dst: return 1.0
seen.add(src)
for nb, w in graph[src].items():
if nb not in seen:
res = dfs(nb, dst, seen)
if res != -1.0: return w * res
return -1.0
return [dfs(a, b, set()) for a, b in queries]Detect a cycle in the prereq graph via 3-color DFS. O(V+E).
from collections import defaultdict
class Solution:
def can_finish(self, num_courses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites: graph[b].append(a)
state = [0] * num_courses # 0=unseen, 1=visiting, 2=done
def dfs(node):
if state[node] == 1: return False
if state[node] == 2: return True
state[node] = 1
for nb in graph[node]:
if not dfs(nb): return False
state[node] = 2
return True
return all(dfs(i) for i in range(num_courses))Kahn's topological sort (BFS on in-degrees). O(V+E).
from collections import defaultdict, deque
class Solution:
def find_order(self, num_courses, prerequisites):
graph = defaultdict(list); indeg = [0] * num_courses
for a, b in prerequisites:
graph[b].append(a); indeg[a] += 1
queue = deque(i for i in range(num_courses) if indeg[i] == 0)
order = []
while queue:
node = queue.popleft(); order.append(node)
for nb in graph[node]:
indeg[nb] -= 1
if indeg[nb] == 0: queue.append(nb)
return order if len(order) == num_courses else []from collections import deque
class Solution:
def snakes_and_ladders(self, board):
n = len(board)
def cell(s):
r, c = divmod(s - 1, n)
if r % 2: c = n - 1 - c
return board[n - 1 - r][c]
queue = deque([(1, 0)]); seen = {1}
while queue:
s, moves = queue.popleft()
if s == n * n: return moves
for nxt in range(s + 1, min(s + 6, n * n) + 1):
dest = cell(nxt)
if dest != -1: nxt = dest
if nxt not in seen:
seen.add(nxt); queue.append((nxt, moves + 1))
return -1from collections import deque
class Solution:
def min_mutation(self, start, end, bank):
bank = set(bank)
queue = deque([(start, 0)]); seen = {start}
while queue:
gene, steps = queue.popleft()
if gene == end: return steps
for i in range(len(gene)):
for ch in "ACGT":
mut = gene[:i] + ch + gene[i+1:]
if mut in bank and mut not in seen:
seen.add(mut); queue.append((mut, steps + 1))
return -1from collections import deque
class Solution:
def ladder_length(self, begin, end, word_list):
words = set(word_list)
if end not in words: return 0
queue = deque([(begin, 1)]); seen = {begin}
while queue:
word, length = queue.popleft()
if word == end: return length
for i in range(len(word)):
for ch in "abcdefghijklmnopqrstuvwxyz":
nxt = word[:i] + ch + word[i+1:]
if nxt in words and nxt not in seen:
seen.add(nxt); queue.append((nxt, length + 1))
return 0class Trie:
def __init__(self): self.root = {}
def insert(self, word):
node = self.root
for c in word: node = node.setdefault(c, {})
node["$"] = True
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return "$" in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return Trueclass WordDictionary:
def __init__(self): self.root = {}
def addWord(self, word):
node = self.root
for c in word: node = node.setdefault(c, {})
node["$"] = True
def search(self, word):
def dfs(node, i):
if i == len(word): return "$" in node
c = word[i]
if c == ".":
return any(dfs(child, i+1) for k, child in node.items() if k != "$")
return c in node and dfs(node[c], i+1)
return dfs(self.root, 0)Put all words in a trie, then DFS the board once, pruning by trie paths.
class Solution:
def find_words(self, board, words):
trie = {}
for w in words:
node = trie
for c in w: node = node.setdefault(c, {})
node["$"] = w
res = []; rows, cols = len(board), len(board[0])
def dfs(r, c, node):
ch = board[r][c]
if ch not in node: return
nxt = node[ch]
if "$" in nxt: res.append(nxt.pop("$"))
board[r][c] = "#"
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
dfs(nr, nc, nxt)
board[r][c] = ch
for r in range(rows):
for c in range(cols):
dfs(r, c, trie)
return resclass Solution:
def letter_combinations(self, digits):
if not digits: return []
m = {"2":"abc","3":"def","4":"ghi","5":"jkl",
"6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
res = [""]
for d in digits:
res = [prefix + c for prefix in res for c in m[d]]
return resclass Solution:
def combine(self, n, k):
res = []
def backtrack(start, path):
if len(path) == k:
res.append(path[:]); return
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return resclass Solution:
def permute(self, nums):
res = []
def backtrack(path, remaining):
if not remaining:
res.append(path[:]); return
for i in range(len(remaining)):
backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
backtrack([], nums)
return resclass Solution:
def combination_sum(self, candidates, target):
res = []
def backtrack(start, path, remaining):
if remaining == 0:
res.append(path[:]); return
for i in range(start, len(candidates)):
if candidates[i] <= remaining:
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i: reuse allowed
path.pop()
backtrack(0, [], target)
return resclass Solution:
def total_n_queens(self, n):
cols = set(); diag1 = set(); diag2 = set()
def place(row):
if row == n: return 1
count = 0
for col in range(n):
if col in cols or (row+col) in diag1 or (row-col) in diag2: continue
cols.add(col); diag1.add(row+col); diag2.add(row-col)
count += place(row + 1)
cols.discard(col); diag1.discard(row+col); diag2.discard(row-col)
return count
return place(0)class Solution:
def generate_parenthesis(self, n):
res = []
def backtrack(s, open_n, close_n):
if len(s) == 2 * n:
res.append(s); return
if open_n < n: backtrack(s + "(", open_n + 1, close_n)
if close_n < open_n: backtrack(s + ")", open_n, close_n + 1)
backtrack("", 0, 0)
return resclass Solution:
def exist(self, board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word): return True
if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
return False
board[r][c] = "#"
found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
board[r][c] = word[i]
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))class Solution:
def sorted_array_to_bst(self, nums):
def build(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid])
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(nums) - 1)class Solution:
def sort_list(self, head):
if not head or not head.next: return head
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next; fast = fast.next.next
mid = slow.next; slow.next = None
left, right = self.sort_list(head), self.sort_list(mid)
dummy = tail = ListNode(0)
while left and right:
if left.val <= right.val: tail.next = left; left = left.next
else: tail.next = right; right = right.next
tail = tail.next
tail.next = left or right
return dummy.nextclass Solution:
def construct(self, grid):
def build(r, c, size):
if size == 1:
return Node(grid[r][c] == 1, True, None, None, None, None)
half = size // 2
tl = build(r, c, half); tr = build(r, c + half, half)
bl = build(r + half, c, half); br = build(r + half, c + half, half)
if (tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf
and tl.val == tr.val == bl.val == br.val):
return Node(tl.val, True, None, None, None, None)
return Node(True, False, tl, tr, bl, br)
return build(0, 0, len(grid))import heapq
class Solution:
def merge_k_lists(self, lists):
heap = []
for i, node in enumerate(lists):
if node: heapq.heappush(heap, (node.val, i, node))
dummy = tail = ListNode(0)
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node; tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextclass Solution:
def max_sub_array(self, nums):
best = cur = nums[0]
for n in nums[1:]:
cur = max(n, cur + n)
best = max(best, cur)
return bestAnswer is either a normal Kadane max, or total − (minimum subarray), whichever's bigger. Guard the all-negative case.
class Solution:
def max_subarray_circular(self, nums):
total = 0
cur_max = best_max = nums[0]
cur_min = best_min = nums[0]
for n in nums:
cur_max = max(n, cur_max + n); best_max = max(best_max, cur_max)
cur_min = min(n, cur_min + n); best_min = min(best_min, cur_min)
total += n
if best_max < 0: return best_max
return max(best_max, total - best_min)class Solution:
def search_insert(self, nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target: lo = mid + 1
else: hi = mid
return loTreat the matrix as one sorted array of length rows·cols. O(log(mn)).
class Solution:
def search_matrix(self, matrix, target):
rows, cols = len(matrix), len(matrix[0])
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
val = matrix[mid // cols][mid % cols]
if val == target: return True
if val < target: lo = mid + 1
else: hi = mid - 1
return Falseclass Solution:
def find_peak_element(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]: lo = mid + 1
else: hi = mid
return loOne half is always sorted — check which, then decide which side to keep. O(log n).
class Solution:
def search_rotated(self, nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]: lo = mid + 1
else: hi = mid - 1
return -1import bisect
class Solution:
def search_range(self, nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target: return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]class Solution:
def find_min(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]: lo = mid + 1
else: hi = mid
return nums[lo]Binary-search a partition of the smaller array so left halves ≤ right halves. O(log(min(m,n))).
class Solution:
def find_median_sorted_arrays(self, a, b):
if len(a) > len(b): a, b = b, a
m, n = len(a), len(b); half = (m + n + 1) // 2
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2; j = half - i
a_left = a[i-1] if i > 0 else float("-inf")
a_right = a[i] if i < m else float("inf")
b_left = b[j-1] if j > 0 else float("-inf")
b_right = b[j] if j < n else float("inf")
if a_left <= b_right and b_left <= a_right:
if (m + n) % 2: return max(a_left, b_left)
return (max(a_left, b_left) + min(a_right, b_right)) / 2
elif a_left > b_right: hi = i - 1
else: lo = i + 1import heapq
class Solution:
def find_kth_largest(self, nums, k):
return heapq.nlargest(k, nums)[-1]Greedy: among all affordable projects, always take the most profitable. Max-heap of profits. O(n log n).
import heapq
class Solution:
def find_maximized_capital(self, k, w, profits, capital):
projects = sorted(zip(capital, profits))
heap = []; i = 0
for _ in range(k):
while i < len(projects) and projects[i][0] <= w:
heapq.heappush(heap, -projects[i][1]); i += 1
if not heap: break
w -= heapq.heappop(heap)
return wimport heapq
class Solution:
def k_smallest_pairs(self, nums1, nums2, k):
if not nums1 or not nums2: return []
heap = []; res = []
for i in range(min(k, len(nums1))):
heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
while heap and len(res) < k:
_, i, j = heapq.heappop(heap)
res.append([nums1[i], nums2[j]])
if j + 1 < len(nums2):
heapq.heappush(heap, (nums1[i] + nums2[j+1], i, j+1))
return resTwo heaps: a max-heap for the lower half, a min-heap for the upper. Median is the top(s). O(log n) per add.
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (store negatives)
self.large = [] # min-heap
def addNum(self, num):
heapq.heappush(self.small, -num)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self):
if len(self.small) > len(self.large): return -self.small[0]
return (-self.small[0] + self.large[0]) / 2class Solution:
def add_binary(self, a, b):
return bin(int(a, 2) + int(b, 2))[2:]class Solution:
def reverse_bits(self, n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return resultclass Solution:
def hamming_weight(self, n):
count = 0
while n:
n &= n - 1 # clears the lowest set bit
count += 1
return countclass Solution:
def single_number(self, nums):
result = 0
for n in nums: result ^= n # pairs cancel via XOR
return resultclass Solution:
def single_number_ii(self, nums):
ones = twos = 0
for n in nums:
ones = (ones ^ n) & ~twos
twos = (twos ^ n) & ~ones
return onesThe result is the common binary prefix of left & right. Shift both right until equal. O(log n).
class Solution:
def range_bitwise_and(self, left, right):
shift = 0
while left < right:
left >>= 1; right >>= 1; shift += 1
return left << shiftclass Solution:
def is_palindrome_number(self, x):
if x < 0: return False
return str(x) == str(x)[::-1]class Solution:
def plus_one(self, digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1; return digits
digits[i] = 0
return [1] + digitsCount factors of 5 in n! (each pairs with a 2 to make a trailing zero). O(log n).
class Solution:
def trailing_zeroes(self, n):
count = 0
while n:
n //= 5; count += n
return countclass Solution:
def my_sqrt(self, x):
lo, hi = 0, x
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x: lo = mid + 1
else: hi = mid - 1
return hiclass Solution:
def my_pow(self, x, n):
if n < 0: x = 1 / x; n = -n
result = 1
while n:
if n & 1: result *= x
x *= x; n >>= 1
return resultfrom math import gcd
class Solution:
def max_points(self, points):
if len(points) <= 2: return len(points)
best = 0
for i in range(len(points)):
slopes = {}
for j in range(i + 1, len(points)):
dx = points[j][0] - points[i][0]
dy = points[j][1] - points[i][1]
g = gcd(dx, dy) or 1
slope = (dx // g, dy // g)
slopes[slope] = slopes.get(slope, 1) + 1
best = max(best, slopes[slope])
return bestclass Solution:
def climb_stairs(self, n):
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return aclass Solution:
def rob(self, nums):
prev = curr = 0
for n in nums:
prev, curr = curr, max(curr, prev + n)
return currclass Solution:
def word_break(self, s, word_dict):
words = set(word_dict); n = len(s)
dp = [False] * (n + 1); dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True; break
return dp[n]class Solution:
def coin_change(self, coins, amount):
dp = [0] + [float("inf")] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float("inf") else -1Patience sorting: keep the smallest tail for each length. O(n log n).
import bisect
class Solution:
def length_of_lis(self, nums):
tails = []
for n in nums:
i = bisect.bisect_left(tails, n)
if i == len(tails): tails.append(n)
else: tails[i] = n
return len(tails)class Solution:
def minimum_total(self, triangle):
dp = triangle[-1][:]
for row in range(len(triangle) - 2, -1, -1):
for i in range(len(triangle[row])):
dp[i] = triangle[row][i] + min(dp[i], dp[i + 1])
return dp[0]class Solution:
def min_path_sum(self, grid):
rows, cols = len(grid), len(grid[0])
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0: continue
up = grid[r-1][c] if r > 0 else float("inf")
left = grid[r][c-1] if c > 0 else float("inf")
grid[r][c] += min(up, left)
return grid[-1][-1]class Solution:
def unique_paths_with_obstacles(self, grid):
cols = len(grid[0])
dp = [0] * cols; dp[0] = 1
for row in grid:
for c in range(cols):
if row[c] == 1: dp[c] = 0
elif c > 0: dp[c] += dp[c - 1]
return dp[-1]Expand around each center (odd and even length). O(n²).
class Solution:
def longest_palindrome(self, s):
start = end = 0
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return l + 1, r - 1
for i in range(len(s)):
for l, r in (expand(i, i), expand(i, i + 1)):
if r - l > end - start: start, end = l, r
return s[start:end + 1]class Solution:
def is_interleave(self, s1, s2, s3):
if len(s1) + len(s2) != len(s3): return False
dp = [False] * (len(s2) + 1); dp[0] = True
for j in range(1, len(s2) + 1):
dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
for i in range(1, len(s1) + 1):
dp[0] = dp[0] and s1[i-1] == s3[i-1]
for j in range(1, len(s2) + 1):
dp[j] = ((dp[j] and s1[i-1] == s3[i+j-1]) or
(dp[j-1] and s2[j-1] == s3[i+j-1]))
return dp[-1]class Solution:
def min_distance(self, word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i
for j in range(n + 1): dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]class Solution:
def max_profit_iii(self, prices):
buy1 = buy2 = float("-inf"); sell1 = sell2 = 0
for p in prices:
buy1 = max(buy1, -p)
sell1 = max(sell1, buy1 + p)
buy2 = max(buy2, sell1 - p)
sell2 = max(sell2, buy2 + p)
return sell2class Solution:
def max_profit_iv(self, k, prices):
if not prices: return 0
if k >= len(prices) // 2: # unlimited → grab every rise
return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))
buy = [float("-inf")] * (k + 1); sell = [0] * (k + 1)
for p in prices:
for j in range(1, k + 1):
buy[j] = max(buy[j], sell[j-1] - p)
sell[j] = max(sell[j], buy[j] + p)
return sell[k]dp[r][c] = side of the largest all-1 square ending at (r,c) = 1 + min of its top/left/diagonal. O(m·n).
class Solution:
def maximal_square(self, matrix):
if not matrix: return 0
rows, cols = len(matrix), len(matrix[0])
dp = [[0] * (cols + 1) for _ in range(rows + 1)]
best = 0
for r in range(1, rows + 1):
for c in range(1, cols + 1):
if matrix[r-1][c-1] == "1":
dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])
best = max(best, dp[r][c])
return best * best