Pulled live from leetcode.com/problemset/?difficulty=Hard on 29 Aug 2026 (895 hard problems in the Algorithms list). "First 30" = the 30 lowest problem numbers. Everything below is Python 3.
How to use this
- Open the problem on LeetCode and make sure the language selector says Python3.
- Select all the text in the code editor and delete it.
- Paste the block below in its place — each block already contains the
class Solutionsignature LeetCode generated for that problem, plus any commented-outListNode/TreeNodeheader. - Press Submit.
Do not add import statements or redefine ListNode / TreeNode — LeetCode injects typing.List, typing.Optional, heapq, math.gcd and the node classes automatically. The blocks are written to rely on exactly that.
Verification
Every solution was executed locally against an independent brute-force reference on randomised and edge-case inputs (4,637 assertions, all passing), then stress-tested at each problem's documented maximum input size (31/31 within budget). Two real defects were found and fixed during that pass — see the notes on #127 and #149.
4. Median of Two Sorted Arrays
https://leetcode.com/problems/median-of-two-sorted-arrays/
Approach. Binary search on the cut position of the shorter array. O(log(min(m,n))), O(1) space.
Constraints (from the problem page). nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -10 6 <= nums1[i], nums2[i] <= 10 6
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# Binary search on the shorter array's cut position. O(log(min(m, n))).
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
lo, hi = 0, m
total = (m + n + 1) // 2
while lo <= hi:
i = (lo + hi) // 2 # take i elements from nums1
j = total - i # take j elements from nums2
l1 = nums1[i - 1] if i > 0 else float('-inf')
r1 = nums1[i] if i < m else float('inf')
l2 = nums2[j - 1] if j > 0 else float('-inf')
r2 = nums2[j] if j < n else float('inf')
if l1 <= r2 and l2 <= r1:
if (m + n) % 2:
return float(max(l1, l2))
return (max(l1, l2) + min(r1, r2)) / 2.0
elif l1 > r2:
hi = i - 1
else:
lo = i + 1
return 0.0
10. Regular Expression Matching
https://leetcode.com/problems/regular-expression-matching/
Approach. Bottom-up DP where dp[i][j] = "does s[i:] match p[j:]". Handles * by either skipping it or consuming one char and staying.
Constraints (from the problem page). 1 <= s.length <= 20 1 <= p.length <= 20 s contains only lowercase English letters. p contains only lowercase English letters, '.' , and '' . It is guaranteed for each appearance of the character '' , there will be a previous valid character to match.
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# Bottom-up DP. dp[i][j] = does s[i:] match p[j:]
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[m][n] = True
for i in range(m, -1, -1):
for j in range(n - 1, -1, -1):
first = i < m and (p[j] == '.' or p[j] == s[i])
if j + 1 < n and p[j + 1] == '*':
# use x* zero times, or consume one char and stay on x*
dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j])
else:
dp[i][j] = first and dp[i + 1][j + 1]
return dp[0][0]
23. Merge k Sorted Lists
https://leetcode.com/problems/merge-k-sorted-lists/
Approach. Min-heap keyed on (value, tie-breaker, node). O(N log k). The integer tie-breaker is required because ListNode is not orderable.
Constraints (from the problem page). k == lists.length 0 <= k <= 10 4 0 <= lists[i].length <= 500 -10 4 <= lists[i][j] <= 10 4 lists[i] is sorted in ascending order . The sum of lists[i].length will not exceed 10 4 .
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
# Min-heap of (value, tie-breaker index, node). O(N log k).
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
tail = dummy
counter = len(lists)
while heap:
val, _, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, counter, node.next))
counter += 1
tail.next = None
return dummy.next
25. Reverse Nodes in k-Group
https://leetcode.com/problems/reverse-nodes-in-k-group/
Approach. Iterative in-place group reversal with a group_prev anchor. O(n) time, O(1) extra space.
Constraints (from the problem page). The number of nodes in the list is n . 1 <= k <= n <= 5000 0 <= Node.val <= 1000 Follow-up: Can you solve the problem in O(1) extra memory space?
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
group_prev = dummy
while True:
# find the k-th node of this group
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next
group_next = kth.next
# reverse [group_prev.next .. kth]
prev, cur = group_next, group_prev.next
while cur is not group_next:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
tmp = group_prev.next
group_prev.next = kth
group_prev = tmp
30. Substring with Concatenation of All Words
https://leetcode.com/problems/substring-with-concatenation-of-all-words/
Approach. Sliding window run once per starting offset in 0..L-1, so the word counter is never rebuilt. O(L*n).
Constraints (from the problem page). 1 <= s.length <= 10 4 1 <= words.length <= 5000 1 <= words[i].length <= 30 s and words[i] consist of lowercase English letters.
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
# Sliding window per starting offset (0 .. L-1). O(L * n).
k = len(words)
L = len(words[0])
total = k * L
n = len(s)
if total > n:
return []
need = {}
for w in words:
need[w] = need.get(w, 0) + 1
res = []
for offset in range(L):
seen = {}
used = 0
left = offset
for j in range(offset, n - L + 1, L):
w = s[j:j + L]
if w in need:
seen[w] = seen.get(w, 0) + 1
used += 1
while seen[w] > need[w]:
seen[s[left:left + L]] -= 1
used -= 1
left += L
if used == k:
res.append(left)
seen[s[left:left + L]] -= 1
used -= 1
left += L
else:
seen.clear()
used = 0
left = j + L
return res
32. Longest Valid Parentheses
https://leetcode.com/problems/longest-valid-parentheses/
Approach. Two counting passes (left-to-right, then right-to-left). O(n) time, O(1) space.
Constraints (from the problem page). 0 <= s.length <= 3 * 10 4 s[i] is '(' , or ')' .
class Solution:
def longestValidParentheses(self, s: str) -> int:
# Two passes with counters, O(1) extra space.
left = right = ans = 0
for c in s:
if c == '(':
left += 1
else:
right += 1
if left == right:
ans = max(ans, 2 * right)
elif right > left:
left = right = 0
left = right = 0
for c in reversed(s):
if c == '(':
left += 1
else:
right += 1
if left == right:
ans = max(ans, 2 * left)
elif left > right:
left = right = 0
return ans
37. Sudoku Solver
https://leetcode.com/problems/sudoku-solver/
Approach. Backtracking with row/col/box bitmasks, always filling the cell with the fewest candidates first (MRV heuristic).
Constraints (from the problem page). board.length == 9 board[i].length == 9 board[i][j] is a digit or '.' . It is guaranteed that the input board has only one solution.
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# Backtracking with row/col/box bitmasks; cells ordered by fewest candidates.
rows = [0] * 9
cols = [0] * 9
boxes = [0] * 9
empties = []
for i in range(9):
for j in range(9):
c = board[i][j]
if c == '.':
empties.append((i, j))
else:
b = 1 << (int(c) - 1)
rows[i] |= b
cols[j] |= b
boxes[(i // 3) * 3 + j // 3] |= b
def solve():
if not empties:
return True
best = -1
best_cnt = 10
best_mask = 0
for idx, (i, j) in enumerate(empties):
used = rows[i] | cols[j] | boxes[(i // 3) * 3 + j // 3]
mask = (~used) & 0x1FF
cnt = bin(mask).count('1')
if cnt < best_cnt:
best_cnt, best, best_mask = cnt, idx, mask
if cnt <= 1:
break
if best_cnt == 0:
return False
i, j = empties.pop(best)
bi = (i // 3) * 3 + j // 3
m = best_mask
while m:
b = m & -m
m ^= b
rows[i] |= b
cols[j] |= b
boxes[bi] |= b
board[i][j] = chr(48 + (b.bit_length()))
if solve():
return True
rows[i] ^= b
cols[j] ^= b
boxes[bi] ^= b
board[i][j] = '.'
empties.insert(best, (i, j))
return False
solve()
41. First Missing Positive
https://leetcode.com/problems/first-missing-positive/
Approach. Cyclic sort: place value v at index v-1, then scan for the first mismatch. O(n) time, O(1) space.
Constraints (from the problem page). 1 <= nums.length <= 10 5 -2 31 <= nums[i] <= 2 31 - 1
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
# Cyclic sort: put value v at index v-1, then scan. O(n) time, O(1) space.
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
v = nums[i]
nums[i], nums[v - 1] = nums[v - 1], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
42. Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/
Approach. Two pointers tracking left_max/right_max. O(n) time, O(1) space.
Constraints (from the problem page). n == height.length 1 <= n <= 2 * 10 4 0 <= height[i] <= 10 5
class Solution:
def trap(self, height: List[int]) -> int:
# Two pointers. O(n) time, O(1) space.
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
44. Wildcard Matching
https://leetcode.com/problems/wildcard-matching/
Approach. Bottom-up DP with consecutive * collapsed first, which keeps the table small. O(m*n).
Constraints (from the problem page). 0 <= s.length, p.length <= 2000 s contains only lowercase English letters. p contains only lowercase English letters, '?' or '*' .
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# Bottom-up DP, dp[i][j] = s[i:] matches p[j:]. O(m*n).
m, n = len(s), len(p)
# collapse consecutive '*'
pp = []
for c in p:
if c == '*' and pp and pp[-1] == '*':
continue
pp.append(c)
p = ''.join(pp)
n = len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[m][n] = True
for j in range(n - 1, -1, -1):
if p[j] == '*':
dp[m][j] = dp[m][j + 1]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if p[j] == '*':
dp[i][j] = dp[i + 1][j] or dp[i][j + 1]
elif p[j] == '?' or p[j] == s[i]:
dp[i][j] = dp[i + 1][j + 1]
return dp[0][0]
51. N-Queens
https://leetcode.com/problems/n-queens/
Approach. Backtracking with column and both diagonal bitmasks; boards are materialised only at the leaves.
Constraints (from the problem page). 1 <= n <= 9
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# Backtracking with column / diagonal bitmasks.
res = []
queens = []
def place(row, cols, d1, d2):
if row == n:
res.append([''.join('.' * q + 'Q' + '.' * (n - q - 1)) for q in queens])
return
free = (~(cols | d1 | d2)) & ((1 << n) - 1)
while free:
b = free & -free
free ^= b
c = b.bit_length() - 1
queens.append(c)
place(row + 1, cols | b, (d1 | b) << 1, (d2 | b) >> 1)
queens.pop()
place(0, 0, 0, 0)
return res
52. N-Queens II
https://leetcode.com/problems/n-queens-ii/
Approach. Same bitmask backtracking, but counts instead of building boards.
Constraints (from the problem page). 1 <= n <= 9
class Solution:
def totalNQueens(self, n: int) -> int:
# Backtracking with column / diagonal bitmasks, counting only.
count = 0
full = (1 << n) - 1
def place(cols, d1, d2):
nonlocal count
if cols == full:
count += 1
return
free = (~(cols | d1 | d2)) & full
while free:
b = free & -free
free ^= b
place(cols | b, ((d1 | b) << 1) & full, (d2 | b) >> 1)
place(0, 0, 0)
return count
60. Permutation Sequence
https://leetcode.com/problems/permutation-sequence/
Approach. Factoradic (factorial number system): pick digit i as (k-1) // (n-1-i)!. O(n^2).
Constraints (from the problem page). 1 <= n <= 9 1 <= k <= n!
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# Factoradic: pick each digit by (k-1) // (n-1-i)!
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i
nums = list(range(1, n + 1))
k -= 1
out = []
for i in range(n, 0, -1):
idx = k // fact[i - 1]
k %= fact[i - 1]
out.append(str(nums.pop(idx)))
return ''.join(out)
65. Valid Number
https://leetcode.com/problems/valid-number/
Approach. Hand-rolled parser instead of a regex: optional sign, digits, optional fraction, optional exponent — requires at least one mantissa digit and at least one exponent digit.
Constraints (from the problem page). 1 <= s.length <= 20 s consists of only English letters (both uppercase and lowercase), digits ( 0-9 ), plus '+' , minus '-' , or dot '.' .
class Solution:
def isNumber(self, s: str) -> bool:
# Hand-rolled state machine (no regex). Accepts: [+-]?(digits[.digits]|[.]digits)([eE][+-]?digits)?
i, n = 0, len(s)
digits_before = digits_after = False
if i < n and (s[i] == '+' or s[i] == '-'):
i += 1
while i < n and s[i].isdigit():
digits_before = True
i += 1
if i < n and s[i] == '.':
i += 1
while i < n and s[i].isdigit():
digits_after = True
i += 1
if not (digits_before or digits_after):
return False
if i < n and (s[i] == 'e' or s[i] == 'E'):
i += 1
if i < n and (s[i] == '+' or s[i] == '-'):
i += 1
exp_digits = False
while i < n and s[i].isdigit():
exp_digits = True
i += 1
if not exp_digits:
return False
return i == n
68. Text Justification
https://leetcode.com/problems/text-justification/
Approach. Greedy line packing; interior gaps get divmod-distributed spaces, last line and single-word lines are left-padded.
Constraints (from the problem page). 1 <= words.length <= 300 1 <= words[i].length <= 20 words[i] consists of only English letters and symbols. 1 <= maxWidth <= 100 words[i].length <= maxWidth
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
res = []
n = len(words)
i = 0
while i < n:
j = i
line_len = len(words[i])
j += 1
while j < n and line_len + 1 + len(words[j]) <= maxWidth:
line_len += 1 + len(words[j])
j += 1
group = words[i:j]
if j == n or len(group) == 1:
# last line (or single word): left justified
line = ' '.join(group)
res.append(line + ' ' * (maxWidth - len(line)))
else:
total_chars = sum(len(w) for w in group)
spaces = maxWidth - total_chars
gaps = len(group) - 1
base, extra = divmod(spaces, gaps)
parts = []
for idx, w in enumerate(group):
parts.append(w)
if idx < gaps:
parts.append(' ' * (base + (1 if idx < extra else 0)))
res.append(''.join(parts))
i = j
return res
76. Minimum Window Substring
https://leetcode.com/problems/minimum-window-substring/
Approach. Sliding window with a formed counter that only ticks when a char hits its exact required count. O(m+n).
Constraints (from the problem page). m == s.length n == t.length 1 <= m, n <= 10 5 s and t consist of uppercase and lowercase English letters. Follow up: Could you find an algorithm that runs in O(m + n) time?
class Solution:
def minWindow(self, s: str, t: str) -> str:
# Sliding window with a "formed" counter. O(len(s) + len(t)).
if not t or not s:
return ""
need = {}
for c in t:
need[c] = need.get(c, 0) + 1
required = len(need)
window = {}
formed = 0
left = 0
best = (float('inf'), 0, 0)
for right, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = (right - left + 1, left, right + 1)
lc = s[left]
window[lc] -= 1
if lc in need and window[lc] < need[lc]:
formed -= 1
left += 1
return "" if best[0] == float('inf') else s[best[1]:best[2]]
84. Largest Rectangle in Histogram
https://leetcode.com/problems/largest-rectangle-in-histogram/
Approach. Monotonic increasing stack carrying each bar's effective start index. O(n).
Constraints (from the problem page). 1 <= heights.length <= 10 5 0 <= heights[i] <= 10 4
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# Monotonic increasing stack. O(n).
stack = []
best = 0
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] >= h:
si, sh = stack.pop()
best = max(best, sh * (i - si))
start = si
stack.append((start, h))
n = len(heights)
while stack:
si, sh = stack.pop()
best = max(best, sh * (n - si))
return best
85. Maximal Rectangle
https://leetcode.com/problems/maximal-rectangle/
Approach. Per-row histogram fed into the #84 monotonic stack. O(rows*cols).
Constraints (from the problem page). rows == matrix.length cols == matrix[i].length 1 <= rows, cols <= 200 matrix[i][j] is '0' or '1' .
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
# Row by row histogram + monotonic stack. O(rows * cols).
if not matrix or not matrix[0]:
return 0
cols = len(matrix[0])
heights = [0] * cols
best = 0
for row in matrix:
for j in range(cols):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
stack = []
for i in range(cols + 1):
h = heights[i] if i < cols else -1
start = i
while stack and stack[-1][1] >= h:
si, sh = stack.pop()
best = max(best, sh * (i - si))
start = si
stack.append((start, h))
return best
87. Scramble String
https://leetcode.com/problems/scramble-string/
Approach. Iterative interval DP over substring length (dp[len][i][j]), so there is no recursion-depth risk. O(n^4) with an early sorted-character prune.
Constraints (from the problem page). s1.length == s2.length 1 <= s1.length <= 30 s1 and s2 consist of lowercase English letters.
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
# Iterative interval DP over length. dp[l][i][j] = s1[i:i+l] scrambles to s2[j:j+l].
if len(s1) != len(s2):
return False
n = len(s1)
if sorted(s1) != sorted(s2):
return False
dp = [[[False] * n for _ in range(n)] for _ in range(n + 1)]
for i in range(n):
for j in range(n):
dp[1][i][j] = s1[i] == s2[j]
for l in range(2, n + 1):
for i in range(n - l + 1):
for j in range(n - l + 1):
ok = False
for k in range(1, l):
# no swap: first k with first k, rest with rest
if dp[k][i][j] and dp[l - k][i + k][j + k]:
ok = True
break
# swap: first k of s1 matches last k of s2
if dp[k][i][j + l - k] and dp[l - k][i + k][j]:
ok = True
break
dp[l][i][j] = ok
return dp[n][0][0]
115. Distinct Subsequences
https://leetcode.com/problems/distinct-subsequences/
Approach. 1-D DP over t, scanning s forwards; the j <= i+1 bound skips unreachable states.
Constraints (from the problem page). 1 <= s.length, t.length <= 1000 s and t consist of English letters.
class Solution:
def numDistinct(self, s: str, t: str) -> int:
# 1-D DP over t, scanning s forward. dp[j] = ways to form t[:j].
m, n = len(s), len(t)
if n == 0:
return 1
if m < n:
return 0
dp = [0] * (n + 1)
dp[0] = 1
for i in range(m):
c = s[i]
# j <= i+1 because we cannot form more chars than we have seen
hi = min(n, i + 1)
for j in range(hi, 0, -1):
if t[j - 1] == c:
dp[j] += dp[j - 1]
return dp[n]
123. Best Time to Buy and Sell Stock III
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
Approach. Four state machines (buy1/sell1/buy2/sell2) in a single pass. O(n) time, O(1) space.
Constraints (from the problem page). 1 <= prices.length <= 10 5 0 <= prices[i] <= 10 5
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Four state machines in one pass. O(n) time, O(1) space.
buy1 = buy2 = float('-inf')
sell1 = sell2 = 0
for p in prices:
buy1 = max(buy1, -p) # best after 1st buy
sell1 = max(sell1, buy1 + p) # best after 1st sell
buy2 = max(buy2, sell1 - p) # best after 2nd buy
sell2 = max(sell2, buy2 + p) # best after 2nd sell
return sell2
124. Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/
Approach. Iterative post-order using an explicit stack — LeetCode allows 3*10^4 nodes, and a skewed tree would blow Python's recursion limit. O(n).
Constraints (from the problem page). The number of nodes in the tree is in the range [1, 3 * 10 4 ] . -1000 <= Node.val <= 1000
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
# Iterative post-order (safe for very deep/skewed trees). O(n).
best = float('-inf')
gain = {}
stack = [(root, False)]
while stack:
node, seen = stack.pop()
if node is None:
continue
if not seen:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
else:
lg = max(gain.get(node.left, 0), 0)
rg = max(gain.get(node.right, 0), 0)
best = max(best, node.val + lg + rg)
gain[node] = node.val + max(lg, rg)
return best
126. Word Ladder II
https://leetcode.com/problems/word-ladder-ii/
Approach. Level-by-level BFS that builds a parent DAG, then DFS back from endWord to emit every shortest path.
Constraints (from the problem page). 1 <= beginWord.length <= 5 endWord.length == beginWord.length 1 <= wordList.length <= 500 wordList[i].length == beginWord.length beginWord , endWord , and wordList[i] consist of lowercase English letters. beginWord != endWord All the words in wordList are unique . The sum of all shortest transformation sequences does not exceed 10 5 .
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
# Level-by-level BFS to build a parent DAG, then DFS to emit every shortest path.
words = set(wordList)
if endWord not in words:
return []
from collections import defaultdict
parents = defaultdict(set)
frontier = {beginWord}
visited = {beginWord}
found = False
while frontier and not found:
words -= frontier
next_level = set()
for word in frontier:
arr = list(word)
for i in range(len(arr)):
orig = arr[i]
for c in 'abcdefghijklmnopqrstuvwxyz':
if c == orig:
continue
arr[i] = c
nxt = ''.join(arr)
if nxt in words:
parents[nxt].add(word)
next_level.add(nxt)
if nxt == endWord:
found = True
arr[i] = orig
visited |= next_level
frontier = next_level
res = []
path = [endWord]
def backtrack(word):
if word == beginWord:
res.append(path[::-1])
return
for p in parents[word]:
path.append(p)
backtrack(p)
path.pop()
if found:
backtrack(endWord)
return res
127. Word Ladder
https://leetcode.com/problems/word-ladder/
Approach. Bidirectional BFS, always expanding the smaller frontier. O(N * L * 26).
Constraints (from the problem page). 1 <= beginWord.length <= 10 endWord.length == beginWord.length 1 <= wordList.length <= 5000 wordList[i].length == beginWord.length beginWord , endWord , and wordList[i] consist of lowercase English letters. beginWord != endWord All the words in wordList are unique .
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# Bidirectional BFS over one-letter-away neighbours.
words = set(wordList)
if endWord not in words:
return 0
if beginWord == endWord:
return 1
front = {beginWord}
back = {endWord}
words.discard(beginWord)
words.discard(endWord)
steps = 1
while front and back:
if len(front) > len(back):
front, back = back, front
steps += 1
nxt = set()
for word in front:
arr = list(word)
for i in range(len(arr)):
orig = arr[i]
for c in 'abcdefghijklmnopqrstuvwxyz':
arr[i] = c
cand = ''.join(arr)
if cand in back:
return steps
if cand in words:
words.discard(cand)
nxt.add(cand)
arr[i] = orig
front = nxt
return 0
132. Palindrome Partitioning II
https://leetcode.com/problems/palindrome-partitioning-ii/
Approach. Palindrome table built by length, then an O(n^2) cut DP.
Constraints (from the problem page). 1 <= s.length <= 2000 s consists of lowercase English letters only.
class Solution:
def minCut(self, s: str) -> int:
# pal[i][j] via expanding DP, then O(n^2) cut DP.
n = len(s)
if n <= 1:
return 0
pal = [[False] * n for _ in range(n)]
for i in range(n):
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 pal[i + 1][j - 1]):
pal[i][j] = True
dp = [0] * n
for i in range(1, n):
if pal[0][i]:
dp[i] = 0
else:
best = i # cut every char
for j in range(1, i + 1):
if pal[j][i] and dp[j - 1] + 1 < best:
best = dp[j - 1] + 1
dp[i] = best
return dp[n - 1]
135. Candy
https://leetcode.com/problems/candy/
Approach. Two sweeps (left-to-right, then right-to-left), keeping the max. O(n) time, O(n) space.
Constraints (from the problem page). 1 <= n == ratings.length <= 5 * 10 4 0 <= ratings[i] <= 5 * 10 4
class Solution:
def candy(self, ratings: List[int]) -> int:
# Two sweeps: left-to-right then right-to-left, take the max.
n = len(ratings)
if n == 0:
return 0
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)
140. Word Break II
https://leetcode.com/problems/word-break-ii/
Approach. Memoised DFS, guarded by a backwards reachability DP so suffixes that cannot be segmented prune immediately.
Constraints (from the problem page). 1 <= s.length <= 20 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 10 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique . Input is generated in a way that the length of the answer doesn't exceed 10 5 .
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
# Memoised DFS guarded by a reachability DP so unreachable suffixes prune early.
words = set(wordDict)
n = len(s)
max_len = max((len(w) for w in words), default=0)
# can[i] = s[i:] can be fully segmented
can = [False] * (n + 1)
can[n] = True
for i in range(n - 1, -1, -1):
for l in range(1, min(max_len, n - i) + 1):
if s[i:i + l] in words and can[i + l]:
can[i] = True
break
memo = {}
def dfs(i):
if i == n:
return [""]
if i in memo:
return memo[i]
out = []
for l in range(1, min(max_len, n - i) + 1):
w = s[i:i + l]
if w in words and can[i + l]:
for rest in dfs(i + l):
out.append(w if rest == "" else w + " " + rest)
memo[i] = out
return out
return dfs(0) if can[0] else []
149. Max Points on a Line
https://leetcode.com/problems/max-points-on-a-line/
Approach. For each anchor, bucket other points by reduced (dx, dy). Points identical to the anchor get direction (0,0) and are added to the winning bucket — they lie on every line through it. O(n^2).
Constraints (from the problem page). 1 <= points.length <= 300 points[i].length == 2 -10 4 <= x i , y i <= 10 4 All the points are unique .
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
# For each anchor point, count identical slopes with reduced (dx, dy) keys.
# Points identical to the anchor get direction (0, 0); they lie on EVERY line
# through the anchor, so they must be added to whichever bucket wins.
n = len(points)
if n <= 2:
return n
best = 2
for i in range(n - 1):
if best >= n - i:
break
x1, y1 = points[i]
slopes = {}
same = 0
for j in range(i + 1, n):
x2, y2 = points[j]
dx = x2 - x1
dy = y2 - y1
if dx == 0 and dy == 0:
same += 1
continue
if dx == 0:
key = (0, 1)
elif dy == 0:
key = (1, 0)
else:
g = gcd(abs(dx), abs(dy))
dx //= g
dy //= g
if dx < 0:
dx, dy = -dx, -dy
key = (dx, dy)
slopes[key] = slopes.get(key, 0) + 1
cur = max(slopes.values(), default=0)
# +1 for the anchor itself, +same for the copies of the anchor
if cur + same + 1 > best:
best = cur + same + 1
return best
154. Find Minimum in Rotated Sorted Array II
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
Approach. Binary search; when nums[mid] == nums[hi] the only safe move is to shrink the right end by one.
Constraints (from the problem page). n == nums.length 1 <= n <= 5000 -5000 <= nums[i] <= 5000 nums is sorted and rotated between 1 and n times. Follow up: This problem is similar to Find Minimum in Rotated Sorted Array , but nums may contain duplicates . Would this affect the runtime complexity? How and why?
class Solution:
def findMin(self, nums: List[int]) -> int:
# Binary search; shrink the right end when nums[mid] == nums[hi].
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
elif nums[mid] < nums[hi]:
hi = mid
else:
hi -= 1
return nums[lo]
158. Read N Characters Given read4 II - Call Multiple Times
https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/
Approach. Keeps a leftover buffer between calls so the next read resumes where the previous one stopped.
Heads-up: this is a LeetCode Premium problem and its page returns no code stub, so unlike the other 29 I could not copy the signature from the site. The class/method shape below is the standard one, but confirm it against your editor before submitting.
read4is provided by LeetCode — do not define it.
# The read4 API is already defined for you, do not modify it.
# On LeetCode the helper is injected into your file automatically.
# (If you want to run this locally, uncomment the reference implementation below.)
# def read4(buf4: List[str]) -> int:
# ...
class Solution:
def __init__(self):
self._leftover = [] # chars already read but not yet handed to a caller
self._pos = 0
def read(self, buf: List[str], n: int) -> int:
written = 0
# 1) drain whatever the previous call left behind
while written < n and self._pos < len(self._leftover):
buf[written] = self._leftover[self._pos]
written += 1
self._pos += 1
if self._pos >= len(self._leftover):
self._leftover = []
self._pos = 0
# 2) keep pulling blocks of 4 until we are full or the file ends
while written < n:
tmp = [''] * 4
cnt = read4(tmp)
if cnt == 0:
break
take = min(cnt, n - written)
for i in range(take):
buf[written + i] = tmp[i]
written += take
if take < cnt:
self._leftover = tmp[take:cnt]
self._pos = 0
break
return written
Here is what you can follow next: the first 30, and then the next 30 LeetCode problems with solutions in Python code.
Thank you for reading so far. Share your thoughts in the comments.
