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.).
Brand new, or just looking around? These 8 classics are completely free - full solutions, run them right in the terminal, no account or credits needed. Work top to bottom, then dip into the rest of the page for depth. (With Learn Premium, every section below works exactly like this one.)
Print 1-100, but "Fizz" for multiples of 3, "Buzz" for 5, "FizzBuzz" for both. The classic warm-up - check the most specific case (15) first.
for n in range(1, 101):
if n % 15 == 0: print("FizzBuzz")
elif n % 3 == 0: print("Fizz")
elif n % 5 == 0: print("Buzz")
else: print(n)Slicing does it in one line; the two-pointer version is what an interviewer wants to see you reason about.
def reverse(s):
return s[::-1] # Pythonic one-liner
def reverse_two_pointer(chars): # in-place, O(n)
lo, hi = 0, len(chars) - 1
while lo < hi:
chars[lo], chars[hi] = chars[hi], chars[lo]
lo += 1; hi -= 1
return charsA word that reads the same backwards. Compare the string to its reverse.
def is_palindrome(s):
s = s.lower()
return s == s[::-1] # "Racecar" -> TrueOne pass, tracking the biggest seen so far - the pattern behind countless harder problems.
def largest(nums):
biggest = nums[0]
for n in nums[1:]:
if n > biggest:
biggest = n
return biggest # (built-in shortcut: max(nums))Loop the characters and tally the ones in "aeiou" - a gentle intro to string scanning.
def count_vowels(s):
return sum(1 for c in s.lower() if c in "aeiou")The single most common interview opener: return the indices of the two numbers that add to target. A hash map turns O(n²) into O(n).
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
return None # no pair foundEach number is the sum of the two before it. The iterative version is O(n) and uses no recursion stack.
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # fib(10) -> 55On a sorted array, halve the search space each step - O(log n). Knowing this cold is non-negotiable.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
if arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1 # not foundBig-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: 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 topclass 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)def three_sum_classic(nums):
nums.sort()
result = []
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:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]:
lo += 1
while lo < hi and nums[hi] == nums[hi-1]:
hi -= 1
lo += 1
hi -= 1
return resultdef max_area_classic(height):
lo, hi = 0, len(height) - 1
best = 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 bestdef longest_consecutive_classic(nums):
num_set = set(nums)
best = 0
for n in num_set:
if n - 1 not in num_set:
length = 1
while n + length in num_set:
length += 1
best = max(best, length)
return bestdef subarray_sum_classic(nums, k):
from collections import defaultdict
prefix = defaultdict(int)
prefix[0] = 1
total = 0
count = 0
for n in nums:
total += n
count += prefix[total - k]
prefix[total] += 1
return countdef find_duplicates(nums):
result = []
for n in nums:
idx = abs(n) - 1
if nums[idx] < 0:
result.append(abs(n))
else:
nums[idx] = -nums[idx]
return resultdef majority_element_classic(nums):
count = 0
candidate = None
for n in nums:
if count == 0:
candidate = n
count += 1 if n == candidate else -1
return candidatedef is_valid_sudoku_classic(board):
seen = set()
for r in range(9):
for c in range(9):
val = board[r][c]
if val == '.':
continue
keys = [('row', r, val), ('col', c, val), ('box', r // 3, c // 3, val)]
for key in keys:
if key in seen:
return False
seen.add(key)
return Truedef game_of_life_classic(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 == 0 and dc == 0:
continue
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in (1, 2):
live += 1
if board[r][c] == 1 and (live < 2 or live > 3):
board[r][c] = 2
elif board[r][c] == 0 and live == 3:
board[r][c] = 3
for r in range(rows):
for c in range(cols):
board[r][c] %= 2
return boarddef insert_interval_classic(intervals, new_interval):
result = []
i = 0
n = len(intervals)
while i < n and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
start, end = new_interval
while i < n and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
result.append([start, end])
while i < n:
result.append(intervals[i])
i += 1
return resultdef h_index_classic(citations):
citations.sort(reverse=True)
h = 0
for i, c in enumerate(citations):
if c >= i + 1:
h = i + 1
else:
break
return hdef maximal_square_classic(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] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
best = max(best, dp[r][c])
return best * bestdef calculate_minimum_hp(dungeon):
rows, cols = len(dungeon), len(dungeon[0])
dp = [[float('inf')] * (cols + 1) for _ in range(rows + 1)]
dp[rows][cols-1] = dp[rows-1][cols] = 1
for r in range(rows - 1, -1, -1):
for c in range(cols - 1, -1, -1):
need = min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]
dp[r][c] = max(1, need)
return dp[0][0]def longest_increasing_path(matrix):
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
memo = {}
def dfs(r, c):
if (r, c) in memo:
return memo[(r, c)]
best = 1
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 matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[(r, c)] = best
return best
return max(dfs(r, c) for r in range(rows) for c in range(cols))def max_profit_iii_classic(prices):
buy1 = buy2 = float('-inf')
sell1 = sell2 = 0
for price in prices:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
return sell2def max_profit_iv_classic(k, prices):
if not prices or k == 0:
return 0
n = len(prices)
if k >= n // 2:
return sum(max(0, prices[i] - prices[i-1]) for i in range(1, n))
buy = [float('-inf')] * (k + 1)
sell = [0] * (k + 1)
for price in prices:
for j in range(1, k + 1):
buy[j] = max(buy[j], sell[j-1] - price)
sell[j] = max(sell[j], buy[j] + price)
return sell[k]def max_coins(nums):
balloons = [1] + nums + [1]
n = len(balloons)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for left in range(n - length):
right = left + length
for k in range(left + 1, right):
dp[left][right] = max(
dp[left][right],
balloons[left] * balloons[k] * balloons[right] + dp[left][k] + dp[k][right])
return dp[0][n-1]def max_envelopes(envelopes):
import bisect
envelopes.sort(key=lambda e: (e[0], -e[1]))
tails = []
for _, h in envelopes:
i = bisect.bisect_left(tails, h)
if i == len(tails):
tails.append(h)
else:
tails[i] = h
return len(tails)def min_window_subsequence(s, t):
m, n = len(s), len(t)
start = -1
min_len = float('inf')
i = 0
while i < m:
j = 0
while i < m:
if s[i] == t[j]:
j += 1
if j == n:
break
i += 1
if j != n:
break
end = i + 1
j = n - 1
while j >= 0:
if s[i] == t[j]:
j -= 1
i -= 1
i += 1
if end - i < min_len:
min_len = end - i
start = i
i += 1
return '' if start == -1 else s[start:start + min_len]def largest_number(nums):
from functools import cmp_to_key
strs = list(map(str, nums))
def compare(a, b):
if a + b > b + a:
return -1
elif a + b < b + a:
return 1
return 0
strs.sort(key=cmp_to_key(compare))
result = ''.join(strs)
return '0' if result[0] == '0' else resultdef max_points_classic(points):
from math import gcd
if len(points) <= 2:
return len(points)
best = 0
for i in range(len(points)):
slopes = {}
for j in range(len(points)):
if i == j:
continue
dx = points[j][0] - points[i][0]
dy = points[j][1] - points[i][1]
g = gcd(dx, dy)
if g != 0:
dx //= g
dy //= g
if dx < 0 or (dx == 0 and dy < 0):
dx, dy = -dx, -dy
slopes[(dx, dy)] = slopes.get((dx, dy), 0) + 1
best = max(best, slopes[(dx, dy)])
return best + 1Square 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 resMove 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 downfrom 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 Trueclass 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 bestdef running_sum(nums):
result = []
total = 0
for n in nums:
total += n
result.append(total)
return resultdef find_max_consecutive_ones(nums):
best = current = 0
for n in nums:
if n == 1:
current += 1
best = max(best, current)
else:
current = 0
return bestdef move_zeroes(nums):
a = list(nums)
insert = 0
for n in a:
if n != 0:
a[insert] = n
insert += 1
while insert < len(a):
a[insert] = 0
insert += 1
return adef two_sum_sorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
total = numbers[lo] + numbers[hi]
if total == target:
return [lo + 1, hi + 1]
if total < target:
lo += 1
else:
hi -= 1
return [-1, -1]def plus_one_arrays(digits):
a = list(digits)
for i in range(len(a) - 1, -1, -1):
if a[i] < 9:
a[i] += 1
return a
a[i] = 0
return [1] + adef single_number_arrays(nums):
result = 0
for n in nums:
result ^= n
return resultFind 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 pairEach 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 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 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)Jumping 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 candidatePair 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 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 bestRead 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 + 1Click 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 boardAll 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 resBiggest 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 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 bestWater 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))def trap_arrays(height):
if not height:
return 0
lo, hi = 0, len(height) - 1
left_max, right_max = height[lo], height[hi]
water = 0
while lo < hi:
if left_max < right_max:
lo += 1
left_max = max(left_max, height[lo])
water += left_max - height[lo]
else:
hi -= 1
right_max = max(right_max, height[hi])
water += right_max - height[hi]
return waterdef product_except_self_arrays(nums):
n = len(nums)
result = [1] * n
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return resultdef first_missing_positive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1def max_product(nums):
best = cur_max = cur_min = nums[0]
for n in nums[1:]:
candidates = (n, cur_max * n, cur_min * n)
cur_max = max(candidates)
cur_min = min(candidates)
best = max(best, cur_max)
return bestdef spiral_order_arrays(matrix):
if not matrix:
return []
result = []
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):
result.append(matrix[top][c])
top += 1
for r in range(top, bottom + 1):
result.append(matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
result.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
result.append(matrix[r][left])
left += 1
return resultdef rotate_image_arrays(matrix):
n = len(matrix)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
row.reverse()
return matrixdef set_zeroes_arrays(matrix):
rows, cols = len(matrix), len(matrix[0])
first_row = any(matrix[0][c] == 0 for c in range(cols))
first_col = any(matrix[r][0] == 0 for r in range(rows))
for r in range(1, rows):
for c in range(1, cols):
if matrix[r][c] == 0:
matrix[r][0] = 0
matrix[0][c] = 0
for r in range(1, rows):
for c in range(1, cols):
if matrix[r][0] == 0 or matrix[0][c] == 0:
matrix[r][c] = 0
if first_row:
for c in range(cols):
matrix[0][c] = 0
if first_col:
for r in range(rows):
matrix[r][0] = 0
return matrixclass 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"def reverse_words_strings(s):
return ' '.join(reversed(s.split()))def is_anagram_strings(s, t):
from collections import Counter
return Counter(s) == Counter(t)def first_uniq_char(s):
from collections import Counter
counts = Counter(s)
for i, c in enumerate(s):
if counts[c] == 1:
return i
return -1def capitalize_words(s):
return ' '.join(word[0].upper() + word[1:].lower() if word else word for word in s.split(' '))def remove_vowels(s):
return ''.join(c for c in s if c.lower() not in 'aeiou')def longest_common_prefix_strings(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 prefixdef is_palindrome_strings(s):
cleaned = [c.lower() for c in s if c.isalnum()]
return cleaned == cleaned[::-1]def reverse_only_letters(s):
chars = list(s)
lo, hi = 0, len(chars) - 1
while lo < hi:
if not chars[lo].isalpha():
lo += 1
elif not chars[hi].isalpha():
hi -= 1
else:
chars[lo], chars[hi] = chars[hi], chars[lo]
lo += 1
hi -= 1
return ''.join(chars)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 TruePick 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 bestdef group_anagrams_strings(strs):
from collections import defaultdict
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())def compress_string(s):
if not s:
return ''
result = []
count = 1
for i in range(1, len(s)):
if s[i] == s[i-1]:
count += 1
else:
result.append(s[i-1] + str(count))
count = 1
result.append(s[-1] + str(count))
return ''.join(result)def count_and_say(n):
result = '1'
for _ in range(n - 1):
next_term = []
i = 0
while i < len(result):
count = 1
while i + 1 < len(result) and result[i] == result[i+1]:
i += 1
count += 1
next_term.append(str(count) + result[i])
i += 1
result = ''.join(next_term)
return resultdef zigzag_convert(s, num_rows):
if num_rows == 1 or num_rows >= len(s):
return s
rows = [''] * num_rows
idx, step = 0, 1
for c in s:
rows[idx] += c
if idx == 0:
step = 1
elif idx == num_rows - 1:
step = -1
idx += step
return ''.join(rows)def multiply_strings(num1, num2):
if num1 == '0' or num2 == '0':
return '0'
m, n = len(num1), len(num2)
result = [0] * (m + n)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
mul = (ord(num1[i]) - 48) * (ord(num2[j]) - 48)
p1, p2 = i + j, i + j + 1
total = mul + result[p2]
result[p2] = total % 10
result[p1] += total // 10
result_str = ''.join(map(str, result)).lstrip('0')
return result_str or '0'def my_atoi(s):
s = s.lstrip()
if not s:
return 0
sign = 1
i = 0
if s[0] in '+-':
sign = -1 if s[0] == '-' else 1
i = 1
num = 0
while i < len(s) and s[i].isdigit():
num = num * 10 + (ord(s[i]) - 48)
i += 1
num *= sign
return max(-2**31, min(2**31 - 1, num))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]]Wrap 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]def is_match(s, p):
from functools import lru_cache
@lru_cache(None)
def dp(i, j):
if j == len(p):
return i == len(s)
first = i < len(s) and p[j] in (s[i], '.')
if j + 1 < len(p) and p[j+1] == '*':
return dp(i, j+2) or (first and dp(i+1, j))
return first and dp(i+1, j+1)
return dp(0, 0)def wildcard_match(s, p):
i = j = 0
star = -1
match = 0
while i < len(s):
if j < len(p) and p[j] in (s[i], '?'):
i += 1
j += 1
elif j < len(p) and p[j] == '*':
star = j
match = i
j += 1
elif star != -1:
j = star + 1
match += 1
i = match
else:
return False
while j < len(p) and p[j] == '*':
j += 1
return j == len(p)def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1))
for i in range(1, m + 1):
prev = dp[0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = prev
else:
dp[j] = 1 + min(prev, dp[j], dp[j-1])
prev = temp
return dp[n]def full_justify_strings(words, max_width):
result = []
line = []
length = 0
for word in words:
if length + len(line) + len(word) > max_width:
spaces = max_width - length
gaps = len(line) - 1
if gaps == 0:
result.append(line[0] + ' ' * spaces)
else:
for i in range(spaces):
line[i % gaps] += ' '
result.append(''.join(line))
line = []
length = 0
line.append(word)
length += len(word)
last = ' '.join(line)
result.append(last + ' ' * (max_width - len(last)))
return resultdef number_to_words(num):
if num == 0:
return 'Zero'
below_20 = ['','One','Two','Three','Four','Five','Six','Seven','Eight','Nine','Ten',
'Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']
tens = ['','','Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']
thousands = ['','Thousand','Million','Billion']
def helper(n):
if n == 0:
return []
if n < 20:
return [below_20[n]]
if n < 100:
return [tens[n // 10]] + helper(n % 10)
return [below_20[n // 100], 'Hundred'] + helper(n % 100)
words = []
group = 0
while num > 0:
if num % 1000 != 0:
words = helper(num % 1000) + ([thousands[group]] if thousands[group] else []) + words
num //= 1000
group += 1
return ' '.join(words)def num_distinct(s, t):
dp = [0] * (len(t) + 1)
dp[0] = 1
for c in s:
for j in range(len(t), 0, -1):
if c == t[j-1]:
dp[j] += dp[j-1]
return dp[len(t)]def shortest_palindrome(s):
if not s:
return s
combined = s + '#' + s[::-1]
lps = [0] * len(combined)
for i in range(1, len(combined)):
length = lps[i-1]
while length > 0 and combined[i] != combined[length]:
length = lps[length-1]
if combined[i] == combined[length]:
length += 1
lps[i] = length
return s[lps[-1]:][::-1] + sdef min_cut(s):
n = len(s)
is_pal = [[False] * n for _ in range(n)]
cuts = [0] * n
for i in range(n):
min_cuts = i
for j in range(i + 1):
if s[j] == s[i] and (i - j < 2 or is_pal[j+1][i-1]):
is_pal[j][i] = True
min_cuts = 0 if j == 0 else min(min_cuts, cuts[j-1] + 1)
cuts[i] = min_cuts
return cuts[n-1]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 -1def binary_search_searchsort(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1def bubble_sort_searchsort(nums):
a = list(nums)
for i in range(len(a) - 1):
swapped = False
for j in range(len(a) - 1 - i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
swapped = True
if not swapped:
break
return adef selection_sort(nums):
a = list(nums)
for i in range(len(a)):
min_idx = i
for j in range(i + 1, len(a)):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
return adef insertion_sort(nums):
a = list(nums)
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
j -= 1
a[j+1] = key
return adef first_occurrence(nums, target):
lo, hi = 0, len(nums) - 1
result = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
result = mid
hi = mid - 1
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return resultdef last_occurrence(nums, target):
lo, hi = 0, len(nums) - 1
result = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
result = mid
lo = mid + 1
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return resultdef search_insert_searchsort(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 lodef is_sorted(nums):
return all(nums[i] <= nums[i+1] for i in range(len(nums) - 1))def count_occurrences_searchsort(nums, target):
import bisect
return bisect.bisect_right(nums, target) - bisect.bisect_left(nums, target)def int_sqrt(x):
if x < 2:
return x
lo, hi = 1, x
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid - 1
return hiFirst 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)]Rows & 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]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:]def search_rotated_searchsort(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]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1def find_min_rotated(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]def find_peak(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 lodef merge_sort(nums):
if len(nums) <= 1:
return list(nums)
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
merged = []
i = j = 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
merged.extend(left[i:])
merged.extend(right[j:])
return mergeddef quick_sort_searchsort(nums):
a = list(nums)
def sort(lo, hi):
if lo >= hi:
return
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
sort(lo, i - 1)
sort(i + 1, hi)
sort(0, len(a) - 1)
return adef find_kth_largest_searchsort(nums, k):
import random
target = len(nums) - k
a = list(nums)
lo, hi = 0, len(a) - 1
while lo <= hi:
pivot = a[random.randint(lo, hi)]
left, mid, right = [], [], []
for x in a[lo:hi+1]:
if x < pivot:
left.append(x)
elif x > pivot:
right.append(x)
else:
mid.append(x)
a[lo:hi+1] = left + mid + right
if target < lo + len(left):
hi = lo + len(left) - 1
elif target >= lo + len(left) + len(mid):
lo = lo + len(left) + len(mid)
else:
return a[target]
return a[target]def sort_colors(nums):
a = list(nums)
lo, mid, hi = 0, 0, len(a) - 1
while mid <= hi:
if a[mid] == 0:
a[lo], a[mid] = a[mid], a[lo]
lo += 1; mid += 1
elif a[mid] == 1:
mid += 1
else:
a[mid], a[hi] = a[hi], a[mid]
hi -= 1
return adef first_bad_version(n, first_bad):
def is_bad(v):
return v >= first_bad
lo, hi = 1, n
while lo < hi:
mid = (lo + hi) // 2
if is_bad(mid):
hi = mid
else:
lo = mid + 1
return lodef search_matrix_searchsort(matrix, target):
if not matrix or not matrix[0]:
return False
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 FalseBinary 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 -1Like 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 - 1Non-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]def find_median_sorted_arrays_searchsort(a, b):
if len(a) > len(b):
a, b = b, a
m, n = len(a), len(b)
lo, hi, half = 0, m, (m + n + 1) // 2
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 float(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 + 1
return 0.0def search_matrix_ii(matrix, target):
if not matrix or not matrix[0]:
return False
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
val = matrix[row][col]
if val == target:
return True
if val > target:
col -= 1
else:
row += 1
return Falsedef smallest_distance_pair(nums, k):
nums.sort()
lo, hi = 0, nums[-1] - nums[0]
while lo < hi:
mid = (lo + hi) // 2
count = 0
left = 0
for right in range(len(nums)):
while nums[right] - nums[left] > mid:
left += 1
count += right - left
if count >= k:
hi = mid
else:
lo = mid + 1
return lodef split_array(nums, k):
def can_split(limit):
pieces = 1
total = 0
for n in nums:
if total + n > limit:
pieces += 1
total = n
else:
total += n
return pieces <= k
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
if can_split(mid):
hi = mid
else:
lo = mid + 1
return lodef count_smaller(nums):
counts = [0] * len(nums)
indexed = list(enumerate(nums))
def sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = sort(arr[:mid])
right = sort(arr[mid:])
merged = []
i = j = 0
while i < len(left) or j < len(right):
if j >= len(right) or (i < len(left) and left[i][1] <= right[j][1]):
counts[left[i][0]] += j
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
return merged
sort(indexed)
return countsdef min_eating_speed(piles, h):
import math
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum(math.ceil(p / mid) for p in piles)
if hours <= h:
hi = mid
else:
lo = mid + 1
return lodef ship_within_days(weights, days):
def needed(cap):
d = 1
total = 0
for w in weights:
if total + w > cap:
d += 1
total = 0
total += w
return d
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if needed(mid) <= days:
hi = mid
else:
lo = mid + 1
return lodef max_sum_subarray_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return bestdef min_sum_subarray_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = min(best, window)
return bestdef average_of_subarrays_k(nums, k):
out, window = [], sum(nums[:k])
out.append(window / k)
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
out.append(window / k)
return outdef max_vowels_in_window(s, k):
vowels = set("aeiou")
count = sum(1 for c in s[:k] if c in vowels)
best = count
for i in range(k, len(s)):
count += (s[i] in vowels) - (s[i - k] in vowels)
best = max(best, count)
return bestdef contains_nearby_duplicate_window(nums, k):
window = set()
for i, n in enumerate(nums):
if n in window:
return True
window.add(n)
if len(window) > k:
window.discard(nums[i - k])
return Falsedef first_negative_each_window(nums, k):
from collections import deque
neg, out = deque(), []
for i, n in enumerate(nums):
if n < 0:
neg.append(i)
if i >= k - 1:
while neg and neg[0] <= i - k:
neg.popleft()
out.append(nums[neg[0]] if neg else 0)
return outdef count_windows_sum_at_least(nums, k, target):
window = sum(nums[:k])
count = 1 if window >= target else 0
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
if window >= target:
count += 1
return countdef max_ones_in_window(nums, k):
ones = sum(nums[:k])
best = ones
for i in range(k, len(nums)):
ones += nums[i] - nums[i - k]
best = max(best, ones)
return bestdef best_window_start_index(nums, k):
window = sum(nums[:k])
best, best_i = window, 0
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
if window > best:
best, best_i = window, i - k + 1
return best_idef window_exists_with_sum(nums, k, target):
window = sum(nums[:k])
if window == target:
return True
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
if window == target:
return True
return Falsek 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 bestdef length_of_longest_substring_window(s):
seen, left, best = {}, 0, 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 bestdef longest_substring_k_distinct(s, k):
from collections import defaultdict
count, left, best = defaultdict(int), 0, 0
for right, c in enumerate(s):
count[c] += 1
while len(count) > k:
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
best = max(best, right - left + 1)
return bestdef min_subarray_len_window(target, nums):
left, total, best = 0, 0, float('inf')
for right, n in enumerate(nums):
total += n
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float('inf') else bestdef longest_ones(nums, k):
left, zeros, best = 0, 0, 0
for right, n in enumerate(nums):
if n == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
best = max(best, right - left + 1)
return bestdef character_replacement(s, k):
from collections import defaultdict
count, left, maxf, best = defaultdict(int), 0, 0, 0
for right, c in enumerate(s):
count[c] += 1
maxf = max(maxf, count[c])
while (right - left + 1) - maxf > k:
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestdef check_inclusion(s1, s2):
from collections import Counter
if len(s1) > len(s2):
return False
need = Counter(s1)
window = Counter(s2[:len(s1)])
if window == need:
return True
for i in range(len(s1), len(s2)):
window[s2[i]] += 1
window[s2[i - len(s1)]] -= 1
if window[s2[i - len(s1)]] == 0:
del window[s2[i - len(s1)]]
if window == need:
return True
return Falsedef find_anagrams(s, p):
from collections import Counter
if len(p) > len(s):
return []
need, window, out = Counter(p), Counter(s[:len(p)]), []
if window == need:
out.append(0)
for i in range(len(p), len(s)):
window[s[i]] += 1
window[s[i - len(p)]] -= 1
if window[s[i - len(p)]] == 0:
del window[s[i - len(p)]]
if window == need:
out.append(i - len(p) + 1)
return outdef total_fruit(fruits):
from collections import defaultdict
count, left, best = defaultdict(int), 0, 0
for right, f in enumerate(fruits):
count[f] += 1
while len(count) > 2:
count[fruits[left]] -= 1
if count[fruits[left]] == 0:
del count[fruits[left]]
left += 1
best = max(best, right - left + 1)
return bestdef num_subarray_product_less_than_k(nums, k):
if k <= 1:
return 0
left, prod, count = 0, 1, 0
for right, n in enumerate(nums):
prod *= n
while prod >= k:
prod //= nums[left]
left += 1
count += right - left + 1
return countdef max_frequency(nums, k):
nums.sort()
left, total, best = 0, 0, 1
for right in range(len(nums)):
total += nums[right]
while nums[right] * (right - left + 1) - total > k:
total -= nums[left]
left += 1
best = max(best, right - left + 1)
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 bestdef min_window_window(s, t):
from collections import Counter
if not t or not s:
return ""
need = Counter(t)
missing = len(t)
left = start = end = 0
for right, c in enumerate(s, 1):
if need[c] > 0:
missing -= 1
need[c] -= 1
if missing == 0:
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if end == 0 or right - left < end - start:
start, end = left, right
need[s[left]] += 1
missing += 1
left += 1
return s[start:end]def max_sliding_window(nums, k):
from collections import deque
dq, out = deque(), []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return outdef subarrays_with_k_distinct(nums, k):
from collections import defaultdict
def at_most(m):
count, left, total = defaultdict(int), 0, 0
for right, n in enumerate(nums):
count[n] += 1
while len(count) > m:
count[nums[left]] -= 1
if count[nums[left]] == 0:
del count[nums[left]]
left += 1
total += right - left + 1
return total
return at_most(k) - at_most(k - 1)def shortest_subarray_at_least_k(nums, k):
from collections import deque
n = len(nums)
prefix = [0] * (n + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
dq, best = deque(), n + 1
for i, cur in enumerate(prefix):
while dq and cur - prefix[dq[0]] >= k:
best = min(best, i - dq.popleft())
while dq and prefix[dq[-1]] >= cur:
dq.pop()
dq.append(i)
return best if best <= n else -1def longest_subarray_limit(nums, limit):
from collections import deque
maxd, mind, left, best = deque(), deque(), 0, 0
for right, n in enumerate(nums):
while maxd and nums[maxd[-1]] <= n:
maxd.pop()
while mind and nums[mind[-1]] >= n:
mind.pop()
maxd.append(right)
mind.append(right)
while nums[maxd[0]] - nums[mind[0]] > limit:
left += 1
if maxd[0] < left:
maxd.popleft()
if mind[0] < left:
mind.popleft()
best = max(best, right - left + 1)
return bestdef num_subarrays_with_sum(nums, goal):
def at_most(s):
if s < 0:
return 0
left, total, count = 0, 0, 0
for right, n in enumerate(nums):
total += n
while total > s:
total -= nums[left]
left += 1
count += right - left + 1
return count
return at_most(goal) - at_most(goal - 1)def count_nice_subarrays(nums, k):
def at_most(m):
if m < 0:
return 0
left, odd, count = 0, 0, 0
for right, n in enumerate(nums):
odd += n % 2
while odd > m:
odd -= nums[left] % 2
left += 1
count += right - left + 1
return count
return at_most(k) - at_most(k - 1)def max_score_cards(cards, k):
n = len(cards)
total = sum(cards)
win = n - k
if win == 0:
return total
cur = sum(cards[:win])
min_mid = cur
for i in range(win, n):
cur += cards[i] - cards[i - win]
min_mid = min(min_mid, cur)
return total - min_middef min_operations(nums, x):
target = sum(nums) - x
if target < 0:
return -1
if target == 0:
return len(nums)
left, total, best = 0, 0, -1
for right, n in enumerate(nums):
total += n
while total > target and left <= right:
total -= nums[left]
left += 1
if total == target:
best = max(best, right - left + 1)
return len(nums) - best if best != -1 else -1def longest_subarray_ones(nums):
left, zeros, best = 0, 0, 0
for right, n in enumerate(nums):
if n == 0:
zeros += 1
while zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
best = max(best, right - left)
return bestclass 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.nextclass 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 headdef reverse_linked_list(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev = head
head = nxt
return prevdef middle_value(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.valdef list_length(head):
n = 0
while head:
n += 1
head = head.next
return ndef sum_list(head):
total = 0
while head:
total += head.val
head = head.next
return totaldef max_list(head):
best = head.val
while head:
best = max(best, head.val)
head = head.next
return bestdef nth_from_end_linked(head, n):
fast = head
for _ in range(n):
fast = fast.next
slow = head
while fast:
fast = fast.next
slow = slow.next
return slow.valdef delete_value(head, target):
dummy = _L(0, head)
cur = dummy
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.nextdef count_occurrences(head, target):
count = 0
while head:
if head.val == target:
count += 1
head = head.next
return countdef search_list(head, target):
while head:
if head.val == target:
return True
head = head.next
return Falsedef remove_duplicates_sorted(head):
cur = head
while cur and cur.next:
if cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.next
return headPattern: 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 headTwo 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 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.nextDetect 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 startsdef remove_nth_from_end_linked(head, n):
dummy = _L(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.nextdef merge_sorted_lists(a, b):
dummy = tail = _L(0)
while a and b:
if a.val <= b.val:
tail.next = a; a = a.next
else:
tail.next = b; b = b.next
tail = tail.next
tail.next = a or b
return dummy.nextdef is_palindrome_list_linked(head):
vals = []
while head:
vals.append(head.val)
head = head.next
return vals == vals[::-1]def odd_even_list(head):
if not head:
return head
odd = head
even = even_head = head.next
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return headdef swap_pairs_linked(head):
dummy = _L(0, head)
prev = dummy
while prev.next and prev.next.next:
first = prev.next
second = first.next
first.next = second.next
second.next = first
prev.next = second
prev = first
return dummy.nextdef rotate_right_linked(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
steps = n - k
new_tail = head
for _ in range(steps - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_headdef partition_list(head, x):
less = lt = _L(0)
greater = gt = _L(0)
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.nextdef remove_all_duplicates(head):
dummy = _L(0, head)
prev = dummy
cur = head
while cur:
if cur.next and cur.next.val == cur.val:
v = cur.val
while cur and cur.val == v:
cur = cur.next
prev.next = cur
else:
prev = cur
cur = cur.next
return dummy.nextdef add_two_numbers_linked(l1, l2):
dummy = cur = _L(0)
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 = _L(digit)
cur = cur.next
return dummy.nextdef reorder_list(head):
if not head or not head.next:
return 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:
nxt = second.next
second.next = prev
prev = second
second = nxt
first = head
while prev:
n1, n2 = first.next, prev.next
first.next = prev
prev.next = n1
first = n1
prev = n2
return headFind 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 headdef reverse_in_k_groups(head, k):
node = head
count = 0
while node and count < k:
node = node.next
count += 1
if count < k:
return head
prev = reverse_in_k_groups(node, k)
cur = head
for _ in range(k):
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prevdef merge_k_linked(lists):
import heapq
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = tail = _L(0)
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextdef sort_list_linked(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 = sort_list_linked(head)
right = sort_list_linked(mid)
dummy = tail = _L(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.nextdef reverse_sublist(head, left, right):
dummy = _L(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.nextdef remove_zero_sum(head):
dummy = _L(0, head)
prefix = 0
seen = {0: dummy}
cur = dummy
while cur:
prefix += cur.val
seen[prefix] = cur
cur = cur.next
prefix = 0
cur = dummy
while cur:
prefix += cur.val
cur.next = seen[prefix].next
cur = cur.next
return dummy.nextdef split_list_parts(head, k):
n = 0
node = head
while node:
n += 1
node = node.next
size, extra = divmod(n, k)
parts = []
cur = head
for i in range(k):
part_head = cur
part_size = size + (1 if i < extra else 0)
prev = None
for _ in range(part_size):
prev = cur
cur = cur.next
if prev:
prev.next = None
parts.append(part_head if part_size else None)
return partsdef add_two_numbers_forward(l1, l2):
s1, s2 = [], []
while l1: s1.append(l1.val); l1 = l1.next
while l2: s2.append(l2.val); l2 = l2.next
carry = 0
head = None
while s1 or s2 or carry:
total = carry
if s1: total += s1.pop()
if s2: total += s2.pop()
carry, digit = divmod(total, 10)
head = _L(digit, head)
return headdef swap_kth_nodes(head, k):
first = head
for _ in range(k - 1):
first = first.next
second = head
runner = first
while runner.next:
runner = runner.next
second = second.next
first.val, second.val = second.val, first.val
return headdef next_greater_nodes(head):
vals = []
while head:
vals.append(head.val)
head = head.next
res = [0] * len(vals)
stack = []
for i, v in enumerate(vals):
while stack and vals[stack[-1]] < v:
res[stack.pop()] = v
stack.append(i)
return resdef plus_one_list(head):
def helper(node):
if not node:
return 1
carry = helper(node.next)
total = node.val + carry
node.val = total % 10
return total // 10
carry = helper(head)
if carry:
return _L(1, head)
return headdef valid_parentheses(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 stackdef reverse_with_stack(s):
stack = list(s)
out = []
while stack:
out.append(stack.pop())
return ''.join(out)def baseball_game(ops):
stack = []
for op in ops:
if op == '+':
stack.append(stack[-1] + stack[-2])
elif op == 'D':
stack.append(stack[-1] * 2)
elif op == 'C':
stack.pop()
else:
stack.append(int(op))
return sum(stack)def remove_adjacent_duplicates(s):
stack = []
for c in s:
if stack and stack[-1] == c:
stack.pop()
else:
stack.append(c)
return ''.join(stack)def min_add_to_make_valid(s):
open_needed = 0
close_needed = 0
for c in s:
if c == '(':
close_needed += 1
elif close_needed > 0:
close_needed -= 1
else:
open_needed += 1
return open_needed + close_neededdef backspace_compare(s, t):
def build(string):
stack = []
for c in string:
if c == '#':
if stack:
stack.pop()
else:
stack.append(c)
return stack
return build(s) == build(t)def make_good(s):
stack = []
for c in s:
if stack and stack[-1] != c and stack[-1].lower() == c.lower():
stack.pop()
else:
stack.append(c)
return ''.join(stack)def remove_outer_parentheses(s):
out = []
depth = 0
for c in s:
if c == '(':
if depth > 0:
out.append(c)
depth += 1
else:
depth -= 1
if depth > 0:
out.append(c)
return ''.join(out)def max_depth_stacks(s):
depth = best = 0
for c in s:
if c == '(':
depth += 1
best = max(best, depth)
elif c == ')':
depth -= 1
return bestdef build_array(target, n):
ops = []
cur = 1
for want in target:
while cur < want:
ops.append('Push')
ops.append('Pop')
cur += 1
ops.append('Push')
cur += 1
return opsAre 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)A 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]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 freedef next_greater_circular(nums):
n = len(nums)
res = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
res[stack.pop()] = nums[i % n]
if i < n:
stack.append(i)
return resdef daily_temperatures(temps):
res = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
res[j] = i - j
stack.append(i)
return resdef eval_rpn_stacks(tokens):
stack = []
for tok in tokens:
if tok in '+-*/':
b = stack.pop(); a = stack.pop()
if tok == '+': stack.append(a + b)
elif tok == '-': stack.append(a - b)
elif tok == '*': stack.append(a * b)
else: stack.append(int(a / b))
else:
stack.append(int(tok))
return stack[0]def decode_string(s):
stack = []
cur = ''
num = 0
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c == '[':
stack.append((cur, num))
cur = ''; num = 0
elif c == ']':
prev, k = stack.pop()
cur = prev + cur * k
else:
cur += c
return curdef asteroid_collision(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 stackdef validate_stack_sequences(pushed, popped):
stack = []
i = 0
for x in pushed:
stack.append(x)
while stack and i < len(popped) and stack[-1] == popped[i]:
stack.pop()
i += 1
return not stackdef simplify_path_stacks(path):
stack = []
for part in path.split('/'):
if part == '' or part == '.':
continue
if part == '..':
if stack:
stack.pop()
else:
stack.append(part)
return '/' + '/'.join(stack)def next_greater_element(nums1, nums2):
greater = {}
stack = []
for n in nums2:
while stack and stack[-1] < n:
greater[stack.pop()] = n
stack.append(n)
return [greater.get(n, -1) for n in nums1]def score_parentheses(s):
stack = [0]
for c in s:
if c == '(':
stack.append(0)
else:
v = stack.pop()
stack[-1] += max(2 * v, 1)
return stack[0]def min_remove_valid(s):
s = list(s)
stack = []
for i, c in enumerate(s):
if c == '(':
stack.append(i)
elif c == ')':
if stack:
stack.pop()
else:
s[i] = ''
for i in stack:
s[i] = ''
return ''.join(s)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)def largest_rectangle_stacks(heights):
stack = []
best = 0
for i, h in enumerate(heights + [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 bestdef maximal_rectangle(matrix):
if not matrix:
return 0
heights = [0] * len(matrix[0])
best = 0
for row in matrix:
for i, v in enumerate(row):
heights[i] = heights[i] + 1 if v == 1 else 0
stack = []
for i, h in enumerate(heights + [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 bestdef trap_rain_water(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = height[stack.pop()]
if not stack:
break
width = i - stack[-1] - 1
bounded = min(height[stack[-1]], h) - bottom
water += width * bounded
stack.append(i)
return waterdef calculate_stacks(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 *= stack.pop()
result += stack.pop()
return result + sign * numdef calculate_ii(s):
stack = []
num = 0
op = '+'
s = s + '+'
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c in '+-*/':
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
else:
stack.append(int(stack.pop() / num))
op = c
num = 0
return sum(stack)def remove_duplicate_letters(s):
last = {c: i for i, c in enumerate(s)}
stack = []
seen = set()
for i, c in enumerate(s):
if c in seen:
continue
while stack and stack[-1] > c and last[stack[-1]] > i:
seen.discard(stack.pop())
stack.append(c)
seen.add(c)
return ''.join(stack)def sum_subarray_mins(arr):
MOD = 10**9 + 7
n = len(arr)
stack = []
total = 0
arr = arr + [float('-inf')]
for i in range(n + 1):
while stack and arr[stack[-1]] >= arr[i]:
mid = stack.pop()
left = stack[-1] if stack else -1
total += arr[mid] * (mid - left) * (i - mid)
stack.append(i)
return total % MODdef longest_valid_parentheses(s):
stack = [-1]
best = 0
for i, c in enumerate(s):
if c == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
best = max(best, i - stack[-1])
return bestdef exclusive_time(n, logs):
res = [0] * n
stack = []
prev = 0
for log in logs:
fid, typ, ts = log.split(':')
fid, ts = int(fid), int(ts)
if typ == 'start':
if stack:
res[stack[-1]] += ts - prev
stack.append(fid)
prev = ts
else:
res[stack.pop()] += ts - prev + 1
prev = ts + 1
return resdef find_132_pattern(nums):
stack = []
third = float('-inf')
for n in reversed(nums):
if n < third:
return True
while stack and stack[-1] < n:
third = stack.pop()
stack.append(n)
return Falseclass 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 closestLeaves 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 * rightdef max_depth_trees(root):
if not root:
return 0
return 1 + max(max_depth_trees(root.left), max_depth_trees(root.right))def min_depth(root):
if not root:
return 0
if not root.left:
return 1 + min_depth(root.right)
if not root.right:
return 1 + min_depth(root.left)
return 1 + min(min_depth(root.left), min_depth(root.right))def count_nodes_trees(root):
if not root:
return 0
return 1 + count_nodes_trees(root.left) + count_nodes_trees(root.right)def sum_tree(root):
if not root:
return 0
return root.val + sum_tree(root.left) + sum_tree(root.right)def invert_tree_trees(root):
if not root:
return None
root.left, root.right = invert_tree_trees(root.right), invert_tree_trees(root.left)
return rootdef is_same_tree_trees(p, q):
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return is_same_tree_trees(p.left, q.left) and is_same_tree_trees(p.right, q.right)def find_max_value(root):
if not root:
return float('-inf')
return max(root.val, find_max_value(root.left), find_max_value(root.right))def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaves(root.left) + count_leaves(root.right)def bst_contains(root, target):
while root:
if root.val == target:
return True
root = root.left if target < root.val else root.right
return Falsedef range_sum_bst(root, low, high):
if not root:
return 0
if root.val < low:
return range_sum_bst(root.right, low, high)
if root.val > high:
return range_sum_bst(root.left, low, high)
return root.val + range_sum_bst(root.left, low, high) + range_sum_bst(root.right, low, high)DFS (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)class 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)Lowest 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 resclass 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 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 rootBuild 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 t1Largest 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]Sum 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)How 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]Do 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 resdef max_path_sum_trees(root):
best = float('-inf')
def gain(node):
nonlocal best
if not node:
return 0
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
best = max(best, node.val + left + right)
return node.val + max(left, right)
gain(root)
return bestdef lowest_common_ancestor_trees(root, p, q):
def helper(node):
if not node:
return None
if node.val == p or node.val == q:
return node
left = helper(node.left)
right = helper(node.right)
if left and right:
return node
return left or right
return helper(root).valdef path_sum_count(root, target):
from collections import defaultdict
prefix = defaultdict(int)
prefix[0] = 1
def dfs(node, current):
if not node:
return 0
current += node.val
count = prefix[current - target]
prefix[current] += 1
count += dfs(node.left, current) + dfs(node.right, current)
prefix[current] -= 1
return count
return dfs(root, 0)def vertical_order(root):
from collections import defaultdict
columns = defaultdict(list)
def dfs(node, row, col):
if not node:
return
columns[col].append((row, node.val))
dfs(node.left, row + 1, col - 1)
dfs(node.right, row + 1, col + 1)
dfs(root, 0, 0)
result = []
for col in sorted(columns):
result.append([val for row, val in sorted(columns[col])])
return resultdef max_width(root):
if not root:
return 0
from collections import deque
best = 0
queue = deque([(root, 0)])
while queue:
n = len(queue)
_, first = queue[0]
last = first
for _ in range(n):
node, idx = queue.popleft()
last = idx
if node.left:
queue.append((node.left, 2 * idx))
if node.right:
queue.append((node.right, 2 * idx + 1))
best = max(best, last - first + 1)
return bestdef distribute_coins(root):
moves = 0
def dfs(node):
nonlocal moves
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
moves += abs(left) + abs(right)
return node.val + left + right - 1
dfs(root)
return movesdef build_adjacency_list(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
return adjdef node_degree(adj, node):
return len(adj[node])def count_edges(adj):
total = sum(len(neighbors) for neighbors in adj)
return total // 2def has_edge(adj, u, v):
return v in adj[u]def bfs_order(adj, start):
from collections import deque
visited = [False] * len(adj)
order = []
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
order.append(node)
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return orderdef dfs_order(adj, start):
visited = [False] * len(adj)
order = []
def dfs(node):
visited[node] = True
order.append(node)
for neighbor in adj[node]:
if not visited[neighbor]:
dfs(neighbor)
dfs(start)
return orderdef count_reachable(adj, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for neighbor in adj[node]:
if neighbor not in visited:
stack.append(neighbor)
return len(visited)def get_neighbors(adj, node):
return sorted(adj[node])def path_exists(adj, source, dest):
visited = set()
stack = [source]
while stack:
node = stack.pop()
if node == dest:
return True
if node in visited:
continue
visited.add(node)
stack.extend(adj[node])
return dest in visiteddef count_components(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
count = 0
for i in range(n):
if not visited[i]:
count += 1
stack = [i]
while stack:
node = stack.pop()
if visited[node]:
continue
visited[node] = True
stack.extend(adj[node])
return countDetect 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 matrixSizes 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 sizesTrack 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)Can 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 Truefrom 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))def num_islands_graphs(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def sink(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
return
grid[r][c] = 0
sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
count += 1
sink(r, c)
return countdef max_area_of_island(grid):
rows, cols = len(grid), len(grid[0])
def area(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
return 0
grid[r][c] = 0
return 1 + area(r+1, c) + area(r-1, c) + area(r, c+1) + area(r, c-1)
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
best = max(best, area(r, c))
return bestdef flood_fill(image, sr, sc, new_color):
old = image[sr][sc]
if old == new_color:
return image
rows, cols = len(image), len(image[0])
def fill(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
return
image[r][c] = new_color
fill(r+1, c); fill(r-1, c); fill(r, c+1); fill(r, c-1)
fill(sr, sc)
return imagedef is_bipartite(graph):
color = {}
for start in range(len(graph)):
if start in color:
continue
color[start] = 0
stack = [start]
while stack:
node = stack.pop()
for neighbor in graph[node]:
if neighbor not in color:
color[neighbor] = color[node] ^ 1
stack.append(neighbor)
elif color[neighbor] == color[node]:
return False
return Truedef can_finish_graphs(num_courses, prerequisites):
from collections import deque
adj = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for a, b in prerequisites:
adj[b].append(a)
indegree[a] += 1
queue = deque(i for i in range(num_courses) if indegree[i] == 0)
taken = 0
while queue:
node = queue.popleft()
taken += 1
for nxt in adj[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return taken == num_coursesOrder 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]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)Like 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 FalseCheapest 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 totaldef find_order_graphs(num_courses, prerequisites):
from collections import deque
adj = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for a, b in prerequisites:
adj[b].append(a)
indegree[a] += 1
queue = deque(i for i in range(num_courses) if indegree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in adj[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == num_courses else []def network_delay_time(times, n, k):
import heapq
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
dist = {}
heap = [(0, k)]
while heap:
d, node = heapq.heappop(heap)
if node in dist:
continue
dist[node] = d
for neighbor, weight in graph[node]:
if neighbor not in dist:
heapq.heappush(heap, (d + weight, neighbor))
return max(dist.values()) if len(dist) == n else -1def ladder_length_graphs(begin_word, end_word, word_list):
from collections import deque
words = set(word_list)
if end_word not in words:
return 0
queue = deque([(begin_word, 1)])
while queue:
word, steps = queue.popleft()
if word == end_word:
return steps
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
candidate = word[:i] + c + word[i+1:]
if candidate in words:
words.remove(candidate)
queue.append((candidate, steps + 1))
return 0def find_cheapest_price(n, flights, src, dst, k):
prices = [float('inf')] * n
prices[src] = 0
for _ in range(k + 1):
temp = prices[:]
for u, v, w in flights:
if prices[u] + w < temp[v]:
temp[v] = prices[u] + w
prices = temp
return prices[dst] if prices[dst] != float('inf') else -1def kth_largest_element(nums, k):
import heapq
return heapq.nlargest(k, nums)[-1]def kth_smallest_element(nums, k):
import heapq
return heapq.nsmallest(k, nums)[-1]def k_smallest(nums, k):
import heapq
return sorted(heapq.nsmallest(k, nums))def k_largest(nums, k):
import heapq
return sorted(heapq.nlargest(k, nums), reverse=True)def last_stone_weight(stones):
import heapq
heap = [-s for s in stones]
heapq.heapify(heap)
while len(heap) > 1:
a = -heapq.heappop(heap)
b = -heapq.heappop(heap)
if a != b:
heapq.heappush(heap, -(a - b))
return -heap[0] if heap else 0def heap_sort_heaps(nums):
import heapq
heap = list(nums)
heapq.heapify(heap)
return [heapq.heappop(heap) for _ in range(len(heap))]def is_min_heap(arr):
n = len(arr)
for i in range(n):
l, r = 2 * i + 1, 2 * i + 2
if l < n and arr[i] > arr[l]:
return False
if r < n and arr[i] > arr[r]:
return False
return Truedef sum_k_smallest(nums, k):
import heapq
return sum(heapq.nsmallest(k, nums))def sum_k_largest(nums, k):
import heapq
return sum(heapq.nlargest(k, nums))def connect_ropes(ropes):
import heapq
heapq.heapify(ropes)
total = 0
while len(ropes) > 1:
a = heapq.heappop(ropes)
b = heapq.heappop(ropes)
total += a + b
heapq.heappush(ropes, a + b)
return totaldef top_k_frequent(nums, k):
import heapq
from collections import Counter
freq = Counter(nums)
return heapq.nlargest(k, freq.keys(), key=freq.get)def k_closest_points(points, k):
import heapq
return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)def kth_largest_stream(k, initial, adds):
import heapq
heap = initial[:]
heapq.heapify(heap)
while len(heap) > k:
heapq.heappop(heap)
out = []
for x in adds:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
out.append(heap[0])
return outdef frequency_sort(s):
import heapq
from collections import Counter
freq = Counter(s)
heap = [(-c, ch) for ch, c in freq.items()]
heapq.heapify(heap)
out = []
while heap:
c, ch = heapq.heappop(heap)
out.append(ch * (-c))
return ''.join(out)def k_smallest_pairs_heaps(nums1, nums2, k):
import heapq
if not nums1 or not nums2:
return []
heap = [(nums1[i] + nums2[0], i, 0) for i in range(min(k, len(nums1)))]
heapq.heapify(heap)
out = []
while heap and len(out) < k:
_, i, j = heapq.heappop(heap)
out.append([nums1[i], nums2[j]])
if j + 1 < len(nums2):
heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
return outdef min_meeting_rooms(intervals):
import heapq
if not intervals:
return 0
intervals.sort()
heap = []
for s, e in intervals:
if heap and heap[0] <= s:
heapq.heappop(heap)
heapq.heappush(heap, e)
return len(heap)def furthest_building(heights, bricks, ladders):
import heapq
heap = []
for i in range(len(heights) - 1):
diff = heights[i + 1] - heights[i]
if diff > 0:
heapq.heappush(heap, diff)
if len(heap) > ladders:
bricks -= heapq.heappop(heap)
if bricks < 0:
return i
return len(heights) - 1def min_set_size(arr):
import heapq
from collections import Counter
counts = [-c for c in Counter(arr).values()]
heapq.heapify(counts)
removed = 0
ops = 0
while removed < len(arr) // 2:
removed += -heapq.heappop(counts)
ops += 1
return opsdef max_score_k_ops(nums, k):
import heapq, math
heap = [-n for n in nums]
heapq.heapify(heap)
score = 0
for _ in range(k):
x = -heapq.heappop(heap)
score += x
heapq.heappush(heap, -math.ceil(x / 3))
return scoredef take_gifts(gifts, k):
import heapq, math
heap = [-g for g in gifts]
heapq.heapify(heap)
for _ in range(k):
x = -heapq.heappop(heap)
heapq.heappush(heap, -math.isqrt(x))
return -sum(heap)Median 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 + 1def running_median(nums):
import heapq
low, high, out = [], [], []
for n in nums:
heapq.heappush(low, -n)
heapq.heappush(high, -heapq.heappop(low))
if len(high) > len(low):
heapq.heappush(low, -heapq.heappop(high))
if len(low) > len(high):
out.append(float(-low[0]))
else:
out.append((-low[0] + high[0]) / 2)
return outdef merge_k_sorted(lists):
import heapq
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
out = []
while heap:
val, i, j = heapq.heappop(heap)
out.append(val)
if j + 1 < len(lists[i]):
heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
return outdef kth_smallest_matrix(matrix, k):
import heapq
n = len(matrix)
heap = [(matrix[r][0], r, 0) for r in range(n)]
heapq.heapify(heap)
val = None
for _ in range(k):
val, r, c = heapq.heappop(heap)
if c + 1 < len(matrix[r]):
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
return valdef smallest_range(nums):
import heapq
heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
heapq.heapify(heap)
cur_max = max(lst[0] for lst in nums)
best = [heap[0][0], cur_max]
while True:
val, i, j = heapq.heappop(heap)
if cur_max - val < best[1] - best[0]:
best = [val, cur_max]
if j + 1 == len(nums[i]):
break
nxt = nums[i][j + 1]
cur_max = max(cur_max, nxt)
heapq.heappush(heap, (nxt, i, j + 1))
return bestdef median_sliding_window(nums, k):
import bisect
window = sorted(nums[:k])
out = []
for i in range(k, len(nums) + 1):
if k % 2:
out.append(float(window[k // 2]))
else:
out.append((window[k // 2 - 1] + window[k // 2]) / 2)
if i < len(nums):
window.pop(bisect.bisect_left(window, nums[i - k]))
bisect.insort(window, nums[i])
return outdef min_cost_hire(quality, wage, k):
import heapq
workers = sorted(zip(wage, quality), key=lambda w: w[0] / w[1])
heap = []
total_q = 0
best = float('inf')
for w, q in workers:
heapq.heappush(heap, -q)
total_q += q
if len(heap) > k:
total_q += heapq.heappop(heap)
if len(heap) == k:
best = min(best, total_q * (w / q))
return round(best, 5)def get_task_order(tasks):
import heapq
indexed = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
heap = []
order = []
time = 0
i = 0
while i < len(indexed) or heap:
if not heap and time < tasks[indexed[i]][0]:
time = tasks[indexed[i]][0]
while i < len(indexed) and tasks[indexed[i]][0] <= time:
idx = indexed[i]
heapq.heappush(heap, (tasks[idx][1], idx))
i += 1
proc, idx = heapq.heappop(heap)
time += proc
order.append(idx)
return orderdef max_performance(n, speed, efficiency, k):
import heapq
workers = sorted(zip(efficiency, speed), reverse=True)
heap = []
speed_sum = 0
best = 0
for eff, spd in workers:
heapq.heappush(heap, spd)
speed_sum += spd
if len(heap) > k:
speed_sum -= heapq.heappop(heap)
best = max(best, speed_sum * eff)
return best % (10**9 + 7)def minimum_deviation(nums):
import heapq
heap = [-(n * 2 if n % 2 else n) for n in nums]
heapq.heapify(heap)
low = -max(heap)
best = float('inf')
while True:
x = -heapq.heappop(heap)
best = min(best, x - low)
if x % 2:
break
x //= 2
low = min(low, x)
heapq.heappush(heap, -x)
return bestdef rearrange_k_distance(s, k):
import heapq
from collections import Counter, deque
if k <= 1:
return s
heap = [(-c, ch) for ch, c in Counter(s).items()]
heapq.heapify(heap)
wait = deque()
out = []
while heap:
c, ch = heapq.heappop(heap)
out.append(ch)
wait.append((c + 1, ch))
if len(wait) >= k:
cnt, chr_ = wait.popleft()
if cnt < 0:
heapq.heappush(heap, (cnt, chr_))
return ''.join(out) if len(out) == len(s) else ''def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]def sum_to_n(n):
if n <= 0:
return 0
return n + sum_to_n(n - 1)def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)def reverse_string(s):
if len(s) <= 1:
return s
return reverse_string(s[1:]) + s[0]def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)def count_digits(n):
if n < 10:
return 1
return 1 + count_digits(n // 10)def sum_of_digits(n):
if n < 10:
return n
return n % 10 + sum_of_digits(n // 10)def is_palindrome_recursion(s):
if len(s) <= 1:
return True
if s[0] != s[-1]:
return False
return is_palindrome_recursion(s[1:-1])def array_sum_recursion(nums, i=0):
if i == len(nums):
return 0
return nums[i] + array_sum_recursion(nums, i + 1)class 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]All 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 resdef subsets(nums):
res = []
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resdef permutations_recursion(nums):
res = []
def backtrack(path, remaining):
if not remaining:
res.append(path[:])
return
for i in range(len(remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], nums)
return resdef combine_recursion(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 resdef combination_sum_recursion(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])
path.pop()
backtrack(0, [], target)
return resdef generate_parentheses(n):
res = []
def backtrack(s, open_count, close_count):
if len(s) == 2 * n:
res.append(s)
return
if open_count < n:
backtrack(s + '(', open_count + 1, close_count)
if close_count < open_count:
backtrack(s + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return resdef letter_combinations_recursion(digits):
if not digits:
return []
mapping = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
res = []
def backtrack(i, path):
if i == len(digits):
res.append(path)
return
for c in mapping[digits[i]]:
backtrack(i + 1, path + c)
backtrack(0, '')
return resdef subsets_with_dup(nums):
nums.sort()
res = []
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resdef permute_unique(nums):
nums.sort()
res = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]):
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return resdef combination_sum2(candidates, target):
candidates.sort()
res = []
def backtrack(start, path, remaining):
if remaining == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]:
continue
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i])
path.pop()
backtrack(0, [], target)
return resdef restore_ip_addresses(s):
res = []
def backtrack(start, parts):
if len(parts) == 4:
if start == len(s):
res.append('.'.join(parts))
return
for length in range(1, 4):
if start + length > len(s):
break
part = s[start:start+length]
if (part[0] == '0' and len(part) > 1) or int(part) > 255:
continue
backtrack(start + length, parts + [part])
backtrack(0, [])
return resFill 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 boardPlace 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)def total_n_queens_recursion(n):
cols = set()
diag1 = set()
diag2 = set()
def backtrack(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 += backtrack(row + 1)
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
return count
return backtrack(0)def word_search(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
return False
tmp = board[r][c]
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] = tmp
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return Falsedef palindrome_partition(s):
res = []
def is_pal(sub):
return sub == sub[::-1]
def backtrack(start, path):
if start == len(s):
res.append(path[:])
return
for end in range(start + 1, len(s) + 1):
sub = s[start:end]
if is_pal(sub):
path.append(sub)
backtrack(end, path)
path.pop()
backtrack(0, [])
return resdef combination_sum3(k, n):
res = []
def backtrack(start, path, remaining):
if len(path) == k:
if remaining == 0:
res.append(path[:])
return
for i in range(start, 10):
if i > remaining:
break
path.append(i)
backtrack(i + 1, path, remaining - i)
path.pop()
backtrack(1, [], n)
return resdef get_permutation(n, k):
import math
numbers = list(range(1, n + 1))
k -= 1
result = []
for i in range(n, 0, -1):
fact = math.factorial(i - 1)
idx = k // fact
result.append(str(numbers.pop(idx)))
k %= fact
return ''.join(result)def gray_code(n):
res = [0]
for i in range(n):
res += [x | (1 << i) for x in reversed(res)]
return resdef count_arrangement(n):
used = [False] * (n + 1)
def backtrack(pos):
if pos > n:
return 1
count = 0
for num in range(1, n + 1):
if not used[num] and (num % pos == 0 or pos % num == 0):
used[num] = True
count += backtrack(pos + 1)
used[num] = False
return count
return backtrack(1)def can_partition_k_subsets(nums, k):
total = sum(nums)
if total % k != 0:
return False
target = total // k
nums.sort(reverse=True)
if nums[0] > target:
return False
used = [False] * len(nums)
def backtrack(count, current, start):
if count == k:
return True
if current == target:
return backtrack(count + 1, 0, 0)
for i in range(start, len(nums)):
if used[i] or current + nums[i] > target:
continue
used[i] = True
if backtrack(count, current + nums[i], i + 1):
return True
used[i] = False
return False
return backtrack(0, 0, 0)def makesquare(matchsticks):
total = sum(matchsticks)
if total % 4 != 0:
return False
side = total // 4
matchsticks.sort(reverse=True)
if matchsticks[0] > side:
return False
sides = [0] * 4
def backtrack(i):
if i == len(matchsticks):
return True
for j in range(4):
if sides[j] + matchsticks[i] <= side:
sides[j] += matchsticks[i]
if backtrack(i + 1):
return True
sides[j] -= matchsticks[i]
if sides[j] == 0:
break
return False
return backtrack(0)def letter_case_permutation(s):
res = []
def backtrack(i, path):
if i == len(s):
res.append(path)
return
if s[i].isalpha():
backtrack(i + 1, path + s[i].lower())
backtrack(i + 1, path + s[i].upper())
else:
backtrack(i + 1, path + s[i])
backtrack(0, '')
return resdef climbing_stairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return bdef fib_dp(n):
if n < 2:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bdef tribonacci(n):
if n == 0:
return 0
if n <= 2:
return 1
a, b, c = 0, 1, 1
for _ in range(3, n + 1):
a, b, c = b, c, a + b + c
return cdef min_cost_climbing_stairs(cost):
a, b = 0, 0
for i in range(2, len(cost) + 1):
a, b = b, min(b + cost[i-1], a + cost[i-2])
return bdef house_robber(nums):
prev, curr = 0, 0
for n in nums:
prev, curr = curr, max(curr, prev + n)
return currdef is_subsequence_dp(s, t):
i = 0
for c in t:
if i < len(s) and s[i] == c:
i += 1
return i == len(s)def pascal_row(row_index):
row = [1]
for _ in range(row_index):
row = [1] + [row[i] + row[i+1] for i in range(len(row)-1)] + [1]
return rowdef unique_paths(m, n):
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[-1]def min_path_sum_dp(grid):
rows, cols = len(grid), len(grid[0])
dp = [float('inf')] * cols
dp[0] = 0
for r in range(rows):
dp[0] += grid[r][0]
for c in range(1, cols):
dp[c] = min(dp[c], dp[c-1]) + grid[r][c]
return dp[-1]def max_subarray_dp(nums):
best = current = nums[0]
for n in nums[1:]:
current = max(n, current + n)
best = max(best, current)
return bestPattern: 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]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 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]def change_dp(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]
return dp[amount]def word_break_dp(s, word_dict):
words = set(word_dict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[len(s)]def num_decodings(s):
if not s or s[0] == '0':
return 0
prev, curr = 1, 1
for i in range(1, len(s)):
temp = 0
if s[i] != '0':
temp += curr
if 10 <= int(s[i-1:i+1]) <= 26:
temp += prev
prev, curr = curr, temp
return currdef longest_palindrome_dp(s):
if not s:
return ''
start, end = 0, 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
for i in range(len(s)):
l1, r1 = expand(i, i)
l2, r2 = expand(i, i + 1)
if r1 - l1 > end - start:
start, end = l1, r1
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end + 1]Fewest 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 resultclass 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]Is 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]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]def array_pair_sum(nums):
nums.sort()
return sum(nums[::2])def maximum_units(boxes, truck_size):
boxes.sort(key=lambda b: -b[1])
total = 0
for count, units in boxes:
take = min(count, truck_size)
total += take * units
truck_size -= take
if truck_size == 0:
break
return totaldef largest_perimeter(nums):
nums.sort(reverse=True)
for i in range(len(nums) - 2):
if nums[i] < nums[i + 1] + nums[i + 2]:
return nums[i] + nums[i + 1] + nums[i + 2]
return 0def can_place_flowers(bed, n):
bed = [0] + bed + [0]
for i in range(1, len(bed) - 1):
if bed[i - 1] == 0 and bed[i] == 0 and bed[i + 1] == 0:
bed[i] = 1
n -= 1
return n <= 0def lemonade_change(bills):
five = ten = 0
for b in bills:
if b == 5:
five += 1
elif b == 10:
if five == 0:
return False
five -= 1; ten += 1
else:
if ten and five:
ten -= 1; five -= 1
elif five >= 3:
five -= 3
else:
return False
return Truedef distribute_candies(candy_type):
return min(len(set(candy_type)), len(candy_type) // 2)def max_profit_greedy(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profitdef find_content_children(greed, sizes):
greed.sort(); sizes.sort()
i = j = 0
while i < len(greed) and j < len(sizes):
if sizes[j] >= greed[i]:
i += 1
j += 1
return idef largest_sum_after_k_negations(nums, k):
nums.sort()
i = 0
while k > 0 and i < len(nums) and nums[i] < 0:
nums[i] = -nums[i]
i += 1; k -= 1
if k % 2 == 1:
nums.sort()
nums[0] = -nums[0]
return sum(nums)def balanced_string_split(s):
balance = count = 0
for c in s:
balance += 1 if c == 'R' else -1
if balance == 0:
count += 1
return countclass 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))def can_jump_greedy(nums):
reach = 0
for i, n in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + n)
return Truedef jump_greedy(nums):
jumps = cur_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = farthest
return jumpsdef can_complete_circuit_greedy(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 startdef least_interval(tasks, n):
from collections import Counter
freq = Counter(tasks)
max_f = max(freq.values())
max_count = sum(1 for v in freq.values() if v == max_f)
return max(len(tasks), (max_f - 1) * (n + 1) + max_count)def partition_labels(s):
last = {c: i for i, c in enumerate(s)}
out, start, end = [], 0, 0
for i, c in enumerate(s):
end = max(end, last[c])
if i == end:
out.append(i - start + 1)
start = i + 1
return outdef erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1])
end = float('-inf')
removed = 0
for s, e in intervals:
if s >= end:
end = e
else:
removed += 1
return removeddef find_min_arrows(points):
if not points:
return 0
points.sort(key=lambda x: x[1])
arrows = 1
end = points[0][1]
for s, e in points[1:]:
if s > end:
arrows += 1
end = e
return arrowsdef merge_intervals_greedy(intervals):
intervals.sort()
out = []
for s, e in intervals:
if out and s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return outdef is_n_straight_hand(hand, group_size):
from collections import Counter
if len(hand) % group_size != 0:
return False
count = Counter(hand)
for card in sorted(count):
if count[card] > 0:
need = count[card]
for k in range(card, card + group_size):
if count[k] < need:
return False
count[k] -= need
return Truedef min_increment_for_unique(nums):
nums.sort()
moves = 0
for i in range(1, len(nums)):
if nums[i] <= nums[i - 1]:
need = nums[i - 1] + 1
moves += need - nums[i]
nums[i] = need
return movesdef candy_greedy(ratings):
n = len(ratings)
give = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
give[i] = give[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
give[i] = max(give[i], give[i + 1] + 1)
return sum(give)def remove_k_digits(num, k):
stack = []
for d in num:
while k and stack and stack[-1] > d:
stack.pop(); k -= 1
stack.append(d)
stack = stack[:len(stack) - k] if k else stack
return ''.join(stack).lstrip('0') or '0'def reorganize_string(s):
import heapq
from collections import Counter
heap = [(-c, ch) for ch, c in Counter(s).items()]
heapq.heapify(heap)
prev = None
out = []
while heap:
cnt, ch = heapq.heappop(heap)
out.append(ch)
if prev and prev[0] < 0:
heapq.heappush(heap, prev)
prev = (cnt + 1, ch)
result = ''.join(out)
return result if len(result) == len(s) else ''def find_maximized_capital_greedy(k, w, profits, capital):
import heapq
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 wdef min_taps(n, ranges):
reach = [0] * (n + 1)
for i, r in enumerate(ranges):
left = max(0, i - r)
reach[left] = max(reach[left], i + r)
taps = end = farthest = 0
for i in range(n):
farthest = max(farthest, reach[i])
if i == end:
if farthest <= i:
return -1
taps += 1
end = farthest
return tapsdef video_stitching(clips, time):
reach = [0] * (time + 1)
for s, e in clips:
if s <= time:
reach[s] = max(reach[s], e)
count = end = farthest = 0
for i in range(time):
farthest = max(farthest, reach[i])
if i == end:
if farthest <= i:
return -1
count += 1
end = farthest
return countdef two_city_sched_cost(costs):
costs.sort(key=lambda c: c[0] - c[1])
n = len(costs) // 2
return sum(c[0] for c in costs[:n]) + sum(c[1] for c in costs[n:])def connect_sticks(sticks):
import heapq
heapq.heapify(sticks)
total = 0
while len(sticks) > 1:
a = heapq.heappop(sticks)
b = heapq.heappop(sticks)
total += a + b
heapq.heappush(sticks, a + b)
return totaldef car_fleet(target, position, speed):
pairs = sorted(zip(position, speed), reverse=True)
fleets = 0
cur = 0.0
for pos, spd in pairs:
time = (target - pos) / spd
if time > cur:
fleets += 1
cur = time
return fleetsdef bag_of_tokens_score(tokens, power):
tokens.sort()
lo, hi = 0, len(tokens) - 1
score = best = 0
while lo <= hi:
if power >= tokens[lo]:
power -= tokens[lo]
score += 1
best = max(best, score)
lo += 1
elif score > 0:
power += tokens[hi]
score -= 1
hi -= 1
else:
break
return bestclass MinStack:
def __init__(self):
self.stack = []
self.mins = []
def push(self, x):
self.stack.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop()
return self.stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.mins[-1]
def min_stack_ops(ops):
obj = MinStack()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('top', 'getMin') else None)
return outclass MyQueue:
def __init__(self):
self.a = []
self.b = []
def push(self, x):
self.a.append(x)
def _shift(self):
if not self.b:
while self.a:
self.b.append(self.a.pop())
def pop(self):
self._shift()
return self.b.pop()
def peek(self):
self._shift()
return self.b[-1]
def empty(self):
return not self.a and not self.b
def queue_using_stacks(ops):
obj = MyQueue()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('pop', 'peek', 'empty') else None)
return outfrom collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return not self.q
def stack_using_queues(ops):
obj = MyStack()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('pop', 'top', 'empty') else None)
return outfrom collections import deque
def moving_average(size, values):
window = deque()
total = 0
out = []
for v in values:
window.append(v)
total += v
if len(window) > size:
total -= window.popleft()
out.append(total / len(window))
return outclass MyHashSet:
def __init__(self):
self.buckets = [[] for _ in range(769)]
def _b(self, key):
return self.buckets[key % 769]
def add(self, key):
b = self._b(key)
if key not in b:
b.append(key)
def remove(self, key):
b = self._b(key)
if key in b:
b.remove(key)
def contains(self, key):
return key in self._b(key)
def design_hashset(ops):
obj = MyHashSet()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'contains' else None)
return outclass MyHashMap:
def __init__(self):
self.buckets = [[] for _ in range(769)]
def _b(self, key):
return self.buckets[key % 769]
def put(self, key, value):
b = self._b(key)
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, value)
return
b.append((key, value))
def get(self, key):
for k, v in self._b(key):
if k == key:
return v
return -1
def remove(self, key):
b = self._b(key)
for i, (k, v) in enumerate(b):
if k == key:
b.pop(i)
return
def design_hashmap(ops):
obj = MyHashMap()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'get' else None)
return outdef logger_rate_limiter(logs):
last = {}
out = []
for ts, msg in logs:
if msg not in last or ts - last[msg] >= 10:
last[msg] = ts
out.append(True)
else:
out.append(False)
return outdef range_sum_immutable(nums, queries):
prefix = [0]
for n in nums:
prefix.append(prefix[-1] + n)
return [prefix[j + 1] - prefix[i] for i, j in queries]def parking_system(slots, cars):
remaining = {1: slots[0], 2: slots[1], 3: slots[2]}
out = []
for car in cars:
if remaining[car] > 0:
remaining[car] -= 1
out.append(True)
else:
out.append(False)
return outfrom collections import deque
def recent_counter(pings):
window = deque()
out = []
for t in pings:
window.append(t)
while window[0] < t - 3000:
window.popleft()
out.append(len(window))
return outclass 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 valueclass 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 nodefrom 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)
def lru_cache_ops(capacity, ops):
obj = LRUCache(capacity)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'get' else None)
return outclass MyCircularQueue:
def __init__(self, k):
self.q = [0] * k
self.head = 0
self.count = 0
self.cap = k
def enQueue(self, v):
if self.count == self.cap:
return False
self.q[(self.head + self.count) % self.cap] = v
self.count += 1
return True
def deQueue(self):
if self.count == 0:
return False
self.head = (self.head + 1) % self.cap
self.count -= 1
return True
def Front(self):
return -1 if self.count == 0 else self.q[self.head]
def Rear(self):
return -1 if self.count == 0 else self.q[(self.head + self.count - 1) % self.cap]
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.cap
def circular_queue_ops(k, ops):
obj = MyCircularQueue(k)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r)
return outimport bisect
class TimeMap:
def __init__(self):
self.store = {}
def set(self, key, value, timestamp):
self.store.setdefault(key, []).append((timestamp, value))
def get(self, key, timestamp):
arr = self.store.get(key, [])
i = bisect.bisect_right(arr, (timestamp, chr(127)))
return arr[i - 1][1] if i else ''
def time_map_ops(ops):
obj = TimeMap()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'get' else None)
return outclass UndergroundSystem:
def __init__(self):
self.checkins = {}
self.totals = {}
def checkIn(self, uid, station, t):
self.checkins[uid] = (station, t)
def checkOut(self, uid, station, t):
start, t0 = self.checkins.pop(uid)
key = (start, station)
total, count = self.totals.get(key, (0, 0))
self.totals[key] = (total + (t - t0), count + 1)
def getAverageTime(self, start, end):
total, count = self.totals[(start, end)]
return total / count
def underground_system(ops):
obj = UndergroundSystem()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'getAverageTime' else None)
return outclass BrowserHistory:
def __init__(self, homepage):
self.history = [homepage]
self.cur = 0
def visit(self, url):
del self.history[self.cur + 1:]
self.history.append(url)
self.cur += 1
def back(self, steps):
self.cur = max(0, self.cur - steps)
return self.history[self.cur]
def forward(self, steps):
self.cur = min(len(self.history) - 1, self.cur + steps)
return self.history[self.cur]
def browser_history(homepage, ops):
obj = BrowserHistory(homepage)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('back', 'forward') else None)
return outdef stock_spanner(prices):
stack = []
out = []
for price in prices:
span = 1
while stack and stack[-1][0] <= price:
span += stack.pop()[1]
stack.append((price, span))
out.append(span)
return outfrom collections import deque
class FrontMiddleBack:
def __init__(self):
self.left = deque()
self.right = deque()
def _balance(self):
if len(self.left) > len(self.right):
self.right.appendleft(self.left.pop())
elif len(self.right) > len(self.left) + 1:
self.left.append(self.right.popleft())
def pushFront(self, val):
self.left.appendleft(val); self._balance()
def pushMiddle(self, val):
if len(self.left) < len(self.right):
self.left.append(val)
else:
self.right.appendleft(val)
self._balance()
def pushBack(self, val):
self.right.append(val); self._balance()
def popFront(self):
if not self.left and not self.right:
return -1
val = self.left.popleft() if self.left else self.right.popleft()
self._balance()
return val
def popMiddle(self):
if not self.left and not self.right:
return -1
if len(self.left) == len(self.right):
val = self.left.pop()
else:
val = self.right.popleft()
self._balance()
return val
def popBack(self):
if not self.right and not self.left:
return -1
val = self.right.pop() if self.right else self.left.pop()
self._balance()
return val
def front_middle_back_ops(ops):
obj = FrontMiddleBack()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0].startswith('pop') else None)
return outdef my_calendar(bookings):
booked = []
out = []
for start, end in bookings:
ok = all(end <= s or start >= e for s, e in booked)
if ok:
booked.append((start, end))
out.append(ok)
return outclass NumArray:
def __init__(self, nums):
self.n = len(nums)
self.tree = [0] * (self.n + 1)
self.nums = [0] * self.n
for i, v in enumerate(nums):
self.update(i, v)
def update(self, i, val):
delta = val - self.nums[i]
self.nums[i] = val
i += 1
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def _prefix(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
def sumRange(self, i, j):
return self._prefix(j + 1) - self._prefix(i)
def range_sum_mutable(nums, ops):
obj = NumArray(nums)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'sumRange' else None)
return outclass MyCircularDeque:
def __init__(self, k):
self.q = [0] * k
self.head = 0
self.count = 0
self.cap = k
def insertFront(self, v):
if self.count == self.cap:
return False
self.head = (self.head - 1) % self.cap
self.q[self.head] = v
self.count += 1
return True
def insertLast(self, v):
if self.count == self.cap:
return False
self.q[(self.head + self.count) % self.cap] = v
self.count += 1
return True
def deleteFront(self):
if self.count == 0:
return False
self.head = (self.head + 1) % self.cap
self.count -= 1
return True
def deleteLast(self):
if self.count == 0:
return False
self.count -= 1
return True
def getFront(self):
return -1 if self.count == 0 else self.q[self.head]
def getRear(self):
return -1 if self.count == 0 else self.q[(self.head + self.count - 1) % self.cap]
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.cap
def circular_deque_ops(k, ops):
obj = MyCircularDeque(k)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r)
return outGet/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-usedFind 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 -1from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.cap = capacity
self.vals = {}
self.freq = {}
self.groups = defaultdict(OrderedDict)
self.min_freq = 0
def _bump(self, key):
f = self.freq[key]
del self.groups[f][key]
if not self.groups[f]:
del self.groups[f]
if self.min_freq == f:
self.min_freq += 1
self.freq[key] = f + 1
self.groups[f + 1][key] = None
def get(self, key):
if key not in self.vals:
return -1
self._bump(key)
return self.vals[key]
def put(self, key, value):
if self.cap == 0:
return
if key in self.vals:
self.vals[key] = value
self._bump(key)
return
if len(self.vals) >= self.cap:
evict, _ = self.groups[self.min_freq].popitem(last=False)
del self.vals[evict]
del self.freq[evict]
self.vals[key] = value
self.freq[key] = 1
self.groups[1][key] = None
self.min_freq = 1
def lfu_cache_ops(capacity, ops):
obj = LFUCache(capacity)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'get' else None)
return outimport heapq
class MedianFinder:
def __init__(self):
self.low = []
self.high = []
def addNum(self, num):
heapq.heappush(self.low, -num)
heapq.heappush(self.high, -heapq.heappop(self.low))
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def findMedian(self):
if len(self.low) > len(self.high):
return float(-self.low[0])
return (-self.low[0] + self.high[0]) / 2
def median_finder_ops(ops):
obj = MedianFinder()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'findMedian' else None)
return outclass 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)
def word_dictionary_ops(ops):
obj = WordDictionary()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'search' else None)
return outdef my_calendar_ii(bookings):
booked = []
overlaps = []
out = []
for start, end in bookings:
if any(start < e and s < end for s, e in overlaps):
out.append(False)
continue
for s, e in booked:
if start < e and s < end:
overlaps.append((max(start, s), min(end, e)))
booked.append((start, end))
out.append(True)
return outfrom collections import defaultdict
def my_calendar_iii(bookings):
delta = defaultdict(int)
out = []
for start, end in bookings:
delta[start] += 1
delta[end] -= 1
active = 0
best = 0
for t in sorted(delta):
active += delta[t]
best = max(best, active)
out.append(best)
return outimport bisect
class SnapshotArray:
def __init__(self, length):
self.snap_id = 0
self.history = [[(-1, 0)] for _ in range(length)]
def set(self, index, val):
self.history[index].append((self.snap_id, val))
def snap(self):
self.snap_id += 1
return self.snap_id - 1
def get(self, index, snap_id):
arr = self.history[index]
i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
return arr[i][1]
def snapshot_array_ops(length, ops):
obj = SnapshotArray(length)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('snap', 'get') else None)
return outimport heapq
class StockPrice:
def __init__(self):
self.prices = {}
self.latest = 0
self.max_heap = []
self.min_heap = []
def update(self, timestamp, price):
self.prices[timestamp] = price
self.latest = max(self.latest, timestamp)
heapq.heappush(self.max_heap, (-price, timestamp))
heapq.heappush(self.min_heap, (price, timestamp))
def current(self):
return self.prices[self.latest]
def maximum(self):
while -self.max_heap[0][0] != self.prices[self.max_heap[0][1]]:
heapq.heappop(self.max_heap)
return -self.max_heap[0][0]
def minimum(self):
while self.min_heap[0][0] != self.prices[self.min_heap[0][1]]:
heapq.heappop(self.min_heap)
return self.min_heap[0][0]
def stock_price_ops(ops):
obj = StockPrice()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('current', 'maximum', 'minimum') else None)
return outimport bisect
class RangeModule:
def __init__(self):
self.ranges = []
def addRange(self, left, right):
i = bisect.bisect_left(self.ranges, left)
j = bisect.bisect_right(self.ranges, right)
merged = []
if i % 2 == 0:
merged.append(left)
if j % 2 == 0:
merged.append(right)
self.ranges[i:j] = merged
def queryRange(self, left, right):
i = bisect.bisect_right(self.ranges, left)
j = bisect.bisect_left(self.ranges, right)
return i == j and i % 2 == 1
def removeRange(self, left, right):
i = bisect.bisect_left(self.ranges, left)
j = bisect.bisect_right(self.ranges, right)
merged = []
if i % 2 == 1:
merged.append(left)
if j % 2 == 1:
merged.append(right)
self.ranges[i:j] = merged
def range_module_ops(ops):
obj = RangeModule()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'queryRange' else None)
return outfrom collections import defaultdict
class FreqStack:
def __init__(self):
self.freq = defaultdict(int)
self.groups = defaultdict(list)
self.max_freq = 0
def push(self, val):
self.freq[val] += 1
f = self.freq[val]
self.max_freq = max(self.max_freq, f)
self.groups[f].append(val)
def pop(self):
val = self.groups[self.max_freq].pop()
self.freq[val] -= 1
if not self.groups[self.max_freq]:
self.max_freq -= 1
return val
def freq_stack_ops(ops):
obj = FreqStack()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'pop' else None)
return outclass AuthenticationManager:
def __init__(self, ttl):
self.ttl = ttl
self.tokens = {}
def generate(self, token_id, current_time):
self.tokens[token_id] = current_time + self.ttl
def renew(self, token_id, current_time):
if token_id in self.tokens and self.tokens[token_id] > current_time:
self.tokens[token_id] = current_time + self.ttl
def countUnexpiredTokens(self, current_time):
return sum(1 for exp in self.tokens.values() if exp > current_time)
def authentication_manager_ops(ttl, ops):
obj = AuthenticationManager(ttl)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'countUnexpiredTokens' else None)
return outIterative binary search with the overflow-safe midpoint. O(log n) time, O(1) space.
public static int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids (lo+hi) overflow
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // not found
} static void reverse(int[] a) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
lo++; hi--;
}
} static List<String> fizzBuzz(int n) {
List<String> res = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) res.add("FizzBuzz");
else if (i % 3 == 0) res.add("Fizz");
else if (i % 5 == 0) res.add("Buzz");
else res.add(String.valueOf(i));
}
return res;
} static int findMax(int[] a) {
int max = a[0];
for (int x : a) max = Math.max(max, x);
return max;
} static long arraySum(int[] a) {
long sum = 0;
for (int x : a) sum += x;
return sum;
} static boolean isPalindrome(String s) {
int lo = 0, hi = s.length() - 1;
while (lo < hi) {
if (s.charAt(lo) != s.charAt(hi)) return false;
lo++; hi--;
}
return true;
} static int countVowels(String s) {
int count = 0;
String vowels = "aeiouAEIOU";
for (char c : s.toCharArray())
if (vowels.indexOf(c) >= 0) count++;
return count;
} static long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) result *= i;
return result;
} static int gcd(int a, int b) {
while (b != 0) {
int tmp = b;
b = a % b;
a = tmp;
}
return a;
} static int linearSearch(int[] a, int target) {
for (int i = 0; i < a.length; i++)
if (a[i] == target) return i;
return -1;
} static void bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
boolean swapped = false;
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) break;
}
}Queue-based BFS over an adjacency map. Mark nodes seen at enqueue time so cycles can't loop. O(V+E).
import java.util.*;
public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
List<Integer> order = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(start); seen.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int next : graph.getOrDefault(node, List.of())) {
if (!seen.contains(next)) { // seen-before-enqueue stops cycles
seen.add(next);
queue.add(next);
}
}
}
return order;
}Bottom-up DP - the plagiarism-detector algorithm in Java. O(n·m) time and space.
public static int lcs(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
} static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(nums[i], i);
}
return new int[]{-1, -1};
} static int[] merge(int[] a, int[] b) {
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
res[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
while (i < a.length) res[k++] = a[i++];
while (j < b.length) res[k++] = b[j++];
return res;
} static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
} else {
stack.push(c);
}
}
return stack.isEmpty();
} static int firstUniqChar(String s) {
Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray())
count.merge(c, 1, Integer::sum);
for (int i = 0; i < s.length(); i++)
if (count.get(s.charAt(i)) == 1) return i;
return -1;
} static void moveZeroes(int[] nums) {
int insert = 0;
for (int n : nums)
if (n != 0) nums[insert++] = n;
while (insert < nums.length) nums[insert++] = 0;
} static void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
static void reverse(int[] a, int lo, int hi) {
while (lo < hi) {
int tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
lo++; hi--;
}
} static int maxSubArray(int[] nums) {
int best = nums[0], current = nums[0];
for (int i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
} static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
} static void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++) {
if (a[j] < pivot) {
int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
i++;
}
}
int tmp = a[i]; a[i] = a[hi]; a[hi] = tmp;
quickSort(a, lo, i - 1);
quickSort(a, i + 1, hi);
} static int[] mergeSort(int[] a) {
if (a.length <= 1) return a;
int mid = a.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
int[] res = new int[a.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length)
res[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
while (i < left.length) res[k++] = left[i++];
while (j < right.length) res[k++] = right[j++];
return res;
}Levenshtein distance, bottom-up. O(n·m).
public static int editDistance(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) dp[i][0] = i; // delete all of a[:i]
for (int j = 0; j <= m; j++) dp[0][j] = j; // insert all of b[:j]
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
return dp[n][m];
}The same design as the Python version, in idiomatic Java with a HashMap collection.
import java.util.*;
class Book {
int id; String title; List<String> content; int lastPage = 0;
Book(int id, String title, List<String> content) {
this.id = id; this.title = title; this.content = content;
}
String displayPage() { return content.get(lastPage); }
String turnPage() {
if (lastPage < content.size() - 1) lastPage++;
return displayPage();
}
}
class Library {
private Map<Integer, Book> collection = new HashMap<>();
private Integer activeId = null;
private int nextId = 0;
int addBook(String title, List<String> content) {
Book b = new Book(nextId++, title, content);
collection.put(b.id, b);
return b.id;
}
void removeBook(int id) {
collection.remove(id);
if (activeId != null && activeId == id) activeId = null;
}
void setActive(int id) { if (collection.containsKey(id)) activeId = id; }
String displayPage() { return activeId == null ? null : collection.get(activeId).displayPage(); }
String turnPage() { return activeId == null ? null : collection.get(activeId).turnPage(); }
} static int[] dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
boolean[] done = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[]{src, 0});
while (!pq.isEmpty()) {
int u = pq.poll()[0];
if (done[u]) continue;
done[u] = true;
for (int v = 0; v < n; v++) {
if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pq.add(new int[]{v, dist[v]});
}
}
}
return dist;
} static class LRUCache {
private final int cap;
private final LinkedHashMap<Integer, Integer> map;
LRUCache(int capacity) {
cap = capacity;
map = new LinkedHashMap<>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
return size() > cap;
}
};
}
int get(int key) { return map.getOrDefault(key, -1); }
void put(int key, int value) { map.put(key, value); }
} static class Trie {
private final Trie[] children = new Trie[26];
private boolean isEnd;
void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) node.children[i] = new Trie();
node = node.children[i];
}
node.isEnd = true;
}
boolean search(String word) {
Trie node = find(word);
return node != null && node.isEnd;
}
boolean startsWith(String prefix) { return find(prefix) != null; }
private Trie find(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) return null;
node = node.children[i];
}
return node;
}
} static int[] topologicalSort(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indegree = new int[n];
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
indegree[e[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.add(i);
int[] order = new int[n];
int idx = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
order[idx++] = u;
for (int v : adj.get(u))
if (--indegree[v] == 0) queue.add(v);
}
return order;
} static int knapsack(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++)
for (int w = capacity; w >= weights[i]; w--)
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
return dp[capacity];
} static int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int x : nums) {
int lo = 0, hi = tails.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails.get(mid) < x) lo = mid + 1;
else hi = mid;
}
if (lo == tails.size()) tails.add(x);
else tails.set(lo, x);
}
return tails.size();
} static double findMedianSortedArrays(int[] A, int[] B) {
if (A.length > B.length) { int[] t = A; A = B; B = t; }
int m = A.length, n = B.length, lo = 0, hi = m, half = (m + n + 1) / 2;
while (lo <= hi) {
int i = (lo + hi) / 2, j = half - i;
int aL = i == 0 ? Integer.MIN_VALUE : A[i - 1];
int aR = i == m ? Integer.MAX_VALUE : A[i];
int bL = j == 0 ? Integer.MIN_VALUE : B[j - 1];
int bR = j == n ? Integer.MAX_VALUE : B[j];
if (aL <= bR && bL <= aR) {
if (((m + n) & 1) == 1) return Math.max(aL, bL);
return (Math.max(aL, bL) + Math.min(aR, bR)) / 2.0;
} else if (aL > bR) hi = i - 1;
else lo = i + 1;
}
return 0.0;
} static int totalNQueens(int n) {
return solve(0, 0, 0, 0, n);
}
static int solve(int row, int cols, int d1, int d2, int n) {
if (row == n) return 1;
int count = 0;
int available = ((1 << n) - 1) & ~(cols | d1 | d2);
while (available != 0) {
int p = available & (-available);
available -= p;
count += solve(row + 1, cols | p, (d1 | p) << 1, (d2 | p) >> 1, n);
}
return count;
} static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int c : coins)
for (int a = c; a <= amount; a++)
dp[a] = Math.min(dp[a], dp[a - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
} static class UnionFind {
private final int[] parent, rank;
private int count;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = n;
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
count--;
}
int count() { return count; }
}Integration roles live on this: call a REST endpoint that returns a JSON list of orders and aggregate revenue per product, highest first. Standard library only - no external packages.
import json, urllib.request
from collections import defaultdict
def revenue_by_product(url):
with urllib.request.urlopen(url, timeout=10) as resp:
orders = json.load(resp) # [{"product": "...", "price": 9.99, "qty": 2}, ...]
totals = defaultdict(float)
for o in orders:
totals[o["product"]] += o["price"] * o["qty"]
# highest-grossing first
return sorted(totals.items(), key=lambda kv: kv[1], reverse=True)From Orders(id, customer_id, amount), list customers with more than 3 orders plus their total spend, biggest spenders first. Tests GROUP BY / HAVING / ORDER BY.
SELECT customer_id,
COUNT(*) AS order_count,
SUM(amount) AS total_spent
FROM Orders
GROUP BY customer_id
HAVING COUNT(*) > 3
ORDER BY total_spent DESC;Every listing wants tests, code reviews and Agile. Given is_valid_email, write tests that cover the happy path and the edge cases (missing @, empty, double @). Interviewers love when you test before you trust the code.
import unittest
def is_valid_email(s):
return s.count("@") == 1 and "." in s.split("@")[1]
class TestEmail(unittest.TestCase):
def test_valid(self): self.assertTrue(is_valid_email("[email protected]"))
def test_no_at(self): self.assertFalse(is_valid_email("abc.com"))
def test_empty(self): self.assertFalse(is_valid_email(""))
def test_two_ats(self): self.assertFalse(is_valid_email("a@@b.com"))
if __name__ == "__main__":
unittest.main()def parse_query_string(qs):
result = {}
if not qs:
return result
for pair in qs.split('&'):
if '=' in pair:
key, value = pair.split('=', 1)
result[key] = value
else:
result[pair] = ''
return resultdef to_snake_case(s):
result = []
for c in s:
if c.isupper():
result.append('_')
result.append(c.lower())
else:
result.append(c)
return ''.join(result)def to_camel_case(s):
parts = s.split('_')
return parts[0] + ''.join(word.capitalize() for word in parts[1:])def format_currency(cents):
dollars = cents / 100
return '${:,.2f}'.format(dollars)def truncate_text(text, max_len):
if len(text) <= max_len:
return text
return text[:max_len] + '...'def slugify(title):
out = []
for c in title.lower():
if c.isalnum():
out.append(c)
elif c in ' -_':
out.append('-')
slug = ''.join(out)
while '--' in slug:
slug = slug.replace('--', '-')
return slug.strip('-')def count_words(text):
return len(text.split())def validate_email(email):
if email.count('@') != 1:
return False
local, domain = email.split('@')
if not local or not domain:
return False
return '.' in domain and not domain.startswith('.') and not domain.endswith('.')def mask_credit_card(number):
digits = number.replace(' ', '').replace('-', '')
if len(digits) <= 4:
return digits
return '*' * (len(digits) - 4) + digits[-4:]def celsius_to_fahrenheit(c):
return round(c * 9 / 5 + 32, 1)To flag plagiarism between two stories, find the length of their longest shared subsequence of characters (same order, but gaps allowed). The naive "try every substring" approach is exponential; memoized recursion is O(n·m). Then run it over every pair of books to surface the most-likely match.
from functools import lru_cache
def longest_common_subsequence(a, b):
@lru_cache(maxsize=None)
def lcs(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + lcs(i + 1, j + 1) # match -> advance both
return max(lcs(i + 1, j), lcs(i, j + 1)) # else skip one side
return lcs(0, 0)
def most_likely_plagiarism(books): # books: list[(title, text)]
best = (0, None, None)
for i in range(len(books)):
for j in range(i + 1, len(books)):
score = longest_common_subsequence(books[i][1], books[j][1])
if score > best[0]:
best = (score, books[i][0], books[j][0])
return best # (shared_chars, titleA, titleB)SQL was the single most-requested hard skill across the listings. From Employee(id, name, salary), return the second-highest distinct salary (return NULL if there isn't one). Know both the sub-query and the window-function answer.
-- Classic sub-query
SELECT MAX(salary) AS second_highest
FROM Employee
WHERE salary < (SELECT MAX(salary) FROM Employee);
-- Modern, scales to "Nth highest" (window function)
SELECT DISTINCT salary AS second_highest
FROM (
SELECT salary,
DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
FROM Employee
) ranked
WHERE rnk = 2;Join + correlated sub-query, a daily-driver pattern for data roles. List each department and the employee(s) earning the most within that department.
SELECT d.name AS department,
e.name AS employee,
e.salary
FROM Employee e
JOIN Department d ON e.dept_id = d.id
WHERE e.salary = (
SELECT MAX(e2.salary)
FROM Employee e2
WHERE e2.dept_id = e.dept_id
)
ORDER BY d.name;def parse_csv_line(line):
fields = []
current = []
in_quotes = False
for c in line:
if c == '"':
in_quotes = not in_quotes
elif c == ',' and not in_quotes:
fields.append(''.join(current))
current = []
else:
current.append(c)
fields.append(''.join(current))
return fieldsdef group_by_key(records, key):
groups = {}
for record in records:
groups.setdefault(record[key], []).append(record)
return groupsdef flatten_dict(d, prefix=''):
result = {}
for key, value in d.items():
full = prefix + key if not prefix else prefix + '.' + key
if isinstance(value, dict):
result.update(flatten_dict(value, full))
else:
result[full] = value
return resultdef deep_merge(a, b):
result = dict(a)
for key, value in b.items():
if key in result and isinstance(result[key], dict) and isinstance(value, dict):
result[key] = deep_merge(result[key], value)
else:
result[key] = value
return resultdef rate_limit_ok(timestamps, now, limit, window):
recent = [t for t in timestamps if t > now - window]
return len(recent) < limitdef paginate(items, page, per_page):
start = (page - 1) * per_page
return items[start:start + per_page]def parse_duration(s):
units = {'h': 3600, 'm': 60, 's': 1}
total = 0
num = ''
for c in s:
if c.isdigit():
num += c
elif c in units:
total += int(num) * units[c]
num = ''
return totaldef dedupe(items):
seen = set()
result = []
for item in items:
if item not in seen:
seen.add(item)
result.append(item)
return resultdef backoff_delays(attempts, base, max_delay):
delays = []
for i in range(attempts):
delay = min(base * (2 ** i), max_delay)
delays.append(delay)
return delaysdef top_n_by_count(items, n):
from collections import Counter
counts = Counter(items)
return counts.most_common(n)Design the core classes for an online cloud reading app (think Kindle, but for indie short stories). Requirements: a user has a library of books they can add to / remove from; they can set one book active; the app remembers where they left off in each book; and it shows one page at a time of the active book. Keep the Book and Library responsibilities separate so the storage format can change later.
class Book:
"""One story. content = list of page-strings; remembers the reader's spot."""
def __init__(self, book_id, title, content):
self.id = book_id
self.title = title
self.content = content # list[str], one entry per page
self.last_page = 0 # index into content
def display_page(self):
return self.content[self.last_page]
def turn_page(self):
if self.last_page < len(self.content) - 1:
self.last_page += 1
return self.display_page()
class Library:
"""A reader's collection of books + which one is open right now."""
def __init__(self):
self.collection = {} # id -> Book (dict = O(1) lookup)
self.active_id = None
self._next_id = 0 # simple unique-id generator
def add_book(self, title, content):
book = Book(self._next_id, title, content)
self.collection[book.id] = book
self._next_id += 1
return book.id
def remove_book(self, book_id):
self.collection.pop(book_id, None)
if self.active_id == book_id:
self.active_id = None
def set_active(self, book_id):
if book_id in self.collection:
self.active_id = book_id
def display_page(self):
if self.active_id is None: return None
return self.collection[self.active_id].display_page()
def turn_page(self):
if self.active_id is None: return None
return self.collection[self.active_id].turn_page()
# Follow-ups the interviewer will ask:
# • Bigger font? Store content as ONE string + a Display class that computes
# chars_per_page from font_size, then page n = content[n*cpp : (n+1)*cpp].
# • Many users sharing books? Store each Book ONCE (e.g. a SQL table keyed by a
# global id); keep per-user state (active_id, last_page) in a separate UserState.The other DP every fuzzy-matching/plagiarism system uses: minimum single-character insert / delete / replace edits to turn string a into b. Bottom-up table, O(n·m).
def edit_distance(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1): dp[i][0] = i # delete all of a[:i]
for j in range(m + 1): dp[0][j] = j # insert all of b[:j]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] # chars match -> free
else:
dp[i][j] = 1 + min(dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1]) # replace
return dp[n][m]def compare_versions(a, b):
pa = [int(x) for x in a.split('.')]
pb = [int(x) for x in b.split('.')]
length = max(len(pa), len(pb))
pa += [0] * (length - len(pa))
pb += [0] * (length - len(pb))
for x, y in zip(pa, pb):
if x < y:
return -1
if x > y:
return 1
return 0def csv_to_records_realworld(text):
lines = [line for line in text.strip().split('\n') if line]
if not lines:
return []
headers = lines[0].split(',')
records = []
for line in lines[1:]:
values = line.split(',')
records.append(dict(zip(headers, values)))
return recordsdef get_by_path(obj, path):
current = obj
for part in path.split('.'):
if isinstance(current, dict):
if part not in current:
return None
current = current[part]
elif isinstance(current, list):
idx = int(part)
if idx < 0 or idx >= len(current):
return None
current = current[idx]
else:
return None
return currentdef validate_password(pw):
failures = []
if len(pw) < 8:
failures.append('too_short')
if not any(c.isupper() for c in pw):
failures.append('no_upper')
if not any(c.islower() for c in pw):
failures.append('no_lower')
if not any(c.isdigit() for c in pw):
failures.append('no_digit')
if not any(not c.isalnum() for c in pw):
failures.append('no_special')
return failuresdef diff_lists(old, new):
old_set = set(old)
new_set = set(new)
added = [x for x in new if x not in old_set]
removed = [x for x in old if x not in new_set]
return {'added': added, 'removed': removed}def parse_ini_realworld(text):
config = {}
section = None
for line in text.split('\n'):
line = line.strip()
if not line or line.startswith(';'):
continue
if line.startswith('[') and line.endswith(']'):
section = line[1:-1]
config[section] = {}
elif '=' in line and section is not None:
key, value = line.split('=', 1)
config[section][key.strip()] = value.strip()
return configdef expand_ranges(s):
result = []
for part in s.split(','):
part = part.strip()
if '-' in part:
start, end = part.split('-')
result.extend(range(int(start), int(end) + 1))
else:
result.append(int(part))
return resultdef format_table(rows):
if not rows:
return ''
cols = len(rows[0])
widths = [max(len(row[c]) for row in rows) for c in range(cols)]
lines = []
for row in rows:
lines.append(' '.join(cell.ljust(widths[c]) for c, cell in enumerate(row)))
return '\n'.join(line.rstrip() for line in lines)def normalize_path(path):
parts = path.split('/')
stack = []
for part in parts:
if part == '' or part == '.':
continue
if part == '..':
if stack:
stack.pop()
else:
stack.append(part)
return '/' + '/'.join(stack)def parse_log_line(line):
import re
pattern = r'(\S+) \S+ \S+ \[[^\]]+\] "(\S+) (\S+) [^"]*" (\d+) (\d+)'
m = re.match(pattern, line)
if not m:
return None
return {
'ip': m.group(1),
'method': m.group(2),
'path': m.group(3),
'status': int(m.group(4)),
'size': int(m.group(5)),
}Pulled straight from what 2026 job listings actually ask for - across data, finance, cloud and full-stack roles the recurring hard skills are SQL, OOP/system design, dynamic programming, APIs/JSON and unit testing. These are worked end-to-end, the way a real 45-minute interview runs (design first, then an algorithm). The two headline problems below are the exact format of a full-length mock interview: an open-ended OOP design, then a DP algorithm.
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 profitMin 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))Can 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 0Where 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 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]Does 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 outLongest 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]An 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 FalseMax 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 bestclass 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]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 = NoneChance 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 connectedHow 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 * bestCoding is only half the interview. A typical CS interview runs intro → resume/projects → coding → behavioral → your questions. These parts are free here because they win (or lose) you offers just as often as the algorithm does.
Situation → Task → Action → Result. Set the scene in a sentence, say what you were responsible for, explain what you specifically did, then finish with a concrete (ideally measurable) result. Aim for ~90 seconds.
"What does success look like in the first 90 days?" · "How does the team handle code review and testing?" · "What's the biggest technical challenge the team is facing right now?" · "How do you support growth for early-career engineers?" Asking nothing signals low interest - always ask at least two.
Crisp, correct answers to the conceptual questions that come up constantly (languages, OOP, memory/OS, databases, architecture & process). Free to read - tap any question.
InputStream/OutputStream vs Reader/Writer.free() manually (Java, Python, C#). The GC tracks references and frees unreachable objects; the trade-off is occasional pauses and less control. In manual languages (C/C++) you allocate (malloc/new) and must deallocate (free/delete) yourself, or you leak memory.JOIN tables when you need the combined view.(distance, node), repeatedly pop the closest unvisited node and relax its edges (update neighbor distances). O((V+E) log V). For graphs with negative weights use Bellman-Ford; for an unweighted graph plain BFS already gives the shortest path. (Dijkstra skeleton is in the Code templates section.)