LeetCode 75 · Medium · Part 2 of 2

Medium Problems — Part 2

Backtracking, greedy, stacks, linked lists, topological sort, DP, and more. These round out the complete medium-level interview pattern library.

Problems: 24
Difficulty: Medium
Topics: Stacks · Backtracking · Greedy · Linked Lists · Graphs
Pattern reminder: Many Medium problems combine two ideas — e.g. "sort + greedy" or "BFS + state tracking" or "DP + reconstruction". When stuck, ask: "What pattern would make the brute force fast here?"
M 26 Medium Arrays Greedy
Jump Game
Given an array nums where nums[i] is the maximum jump length from index i, return True if you can reach the last index starting from index 0.
Test Cases
canJump([2,3,1,1,4]) → True # jump 1 → index 1 → jump 3 to end canJump([3,2,1,0,4]) → False # always land on index 3 which has jump 0 canJump([0]) → True # already at end canJump([2,0,0]) → True # jump 2 straight to end
greedy max_reachsingle pass
Track the furthest index you can reach so far. At each index i, if i > max_reach, you're stuck there — return False. Otherwise update max_reach = max(max_reach, i + nums[i]).
Solution
from typing import List def canJump(nums: List[int]) -> bool: max_reach = 0 for i, jump in enumerate(nums): if i > max_reach: return False # can't reach this index max_reach = max(max_reach, i + jump) return True
Complexity
Time: O(n), Space: O(1).
Alternative Approach
Work backwards: Start from the last index as "goal". Walk left — if you can reach the goal from index i, update goal = i. Return goal == 0. Same complexity.
M 27 Medium Strings Greedy
Integer to Roman
Convert an integer (1 ≤ num ≤ 3999) to a Roman numeral string. Roman numerals: I=1, IV=4, V=5, IX=9, X=10, XL=40, L=50, XC=90, C=100, CD=400, D=500, CM=900, M=1000.
Test Cases
intToRoman(3) → "III" intToRoman(58) → "LVIII" # L=50, V=5, III=3 intToRoman(1994) → "MCMXCIV" # M=1000, CM=900, XC=90, IV=4
greedy subtractionvalue-symbol table
Keep a list of (value, symbol) pairs ordered from largest to smallest. Greedily subtract the largest symbol that fits into num, appending it to the result each time.
Solution
def intToRoman(num: int) -> str: 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'), ] result = "" for val, symbol in vals: while num >= val: result += symbol num -= val return result
Complexity
Time: O(1) — num is bounded (≤ 3999), so the number of iterations is bounded.
Space: O(1) — fixed size value table and output is bounded.
M 28 Medium Graphs Topological Sort
Course Schedule
Given numCourses and a list of prerequisites where [a, b] means you must take b before a, return True if you can finish all courses (i.e., no cycle exists).
Test Cases
canFinish(2, [[1,0]]) → True # take 0 then 1 canFinish(2, [[1,0],[0,1]]) → False # cycle: 0 requires 1 and 1 requires 0 canFinish(1, []) → True canFinish(3, [[1,0],[2,1]]) → True
topological sort (Kahn's)in-degree array BFS queue
Cycle detection in a directed graph = can we topologically sort it? Kahn's algorithm: start with nodes that have no prerequisites (in-degree 0). Remove them and reduce neighbors' in-degrees. If we process all nodes, no cycle. If some remain, there's a cycle.
Solution
from collections import defaultdict, deque from typing import List def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) in_degree = [0] * numCourses for course, prereq in prerequisites: graph[prereq].append(course) in_degree[course] += 1 # Start with all courses that have no prerequisites queue = deque(i for i in range(numCourses) if in_degree[i] == 0) taken = 0 while queue: course = queue.popleft() taken += 1 for next_course in graph[course]: in_degree[next_course] -= 1 if in_degree[next_course] == 0: queue.append(next_course) return taken == numCourses # if not all processed → cycle exists
Complexity
Time: O(V + E) — vertices (courses) + edges (prerequisites).
Space: O(V + E) — graph + in-degree array + queue.
Alternative Approach
DFS with 3-color marking: White (unvisited), Gray (in-progress), Black (done). If you visit a Gray node, there's a cycle. Same complexity.
M 29 Medium Arrays Two Pointers
Next Permutation
Find the next lexicographically greater permutation of the array of integers. If no such permutation exists (array is sorted descending), rearrange to the smallest permutation (sorted ascending). Do it in-place.
Test Cases
nextPermutation([1,2,3]) → [1,3,2] nextPermutation([3,2,1]) → [1,2,3] # no larger permutation, wrap to smallest nextPermutation([1,1,5]) → [1,5,1] nextPermutation([1,3,2]) → [2,1,3]
rightmost descentswap + reverse suffix in-place
3 steps: (1) Find the rightmost index i where nums[i] < nums[i+1] — this is the "pivot". (2) Find the smallest element to the right of i that's greater than nums[i], swap them. (3) Reverse the suffix after position i to get the smallest arrangement of those elements.
Solution
from typing import List def nextPermutation(nums: List[int]) -> None: n = len(nums) i = n - 2 # Step 1: find rightmost ascent (nums[i] < nums[i+1]) while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i >= 0: # Step 2: find the smallest element > nums[i] in the suffix j = n - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] # Step 3: reverse the suffix to make it smallest nums[i + 1:] = reversed(nums[i + 1:])
Complexity
Time: O(n) — at most two passes through the array.
Space: O(1) — in-place.
M 30 Medium Graphs Topological Sort
Course Schedule II
Same as Course Schedule, but return the order in which courses should be taken. Return an empty array if it's impossible (cycle exists).
Test Cases
findOrder(2, [[1,0]]) → [0,1] findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) → [0,1,2,3] or [0,2,1,3] findOrder(2, [[1,0],[0,1]]) → [] # cycle
Kahn's topological sortcollect order
Same as Course Schedule, but instead of just counting, collect the processed courses into an order list. If the order list length != numCourses, return [].
Solution
from collections import defaultdict, deque from typing import List def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]: graph = defaultdict(list) in_degree = [0] * numCourses for course, prereq in prerequisites: graph[prereq].append(course) in_degree[course] += 1 queue = deque(i for i in range(numCourses) if in_degree[i] == 0) order = [] while queue: course = queue.popleft() order.append(course) for nxt in graph[course]: in_degree[nxt] -= 1 if in_degree[nxt] == 0: queue.append(nxt) return order if len(order) == numCourses else []
Complexity
Time: O(V + E), Space: O(V + E). Same as Course Schedule I.
M 31 Medium Arrays Binary Search
Find Peak Element
A peak element is strictly greater than its neighbors. Given an array nums, find a peak element and return its index. Assume nums[-1] = nums[n] = -∞. Solve in O(log n).
Test Cases
findPeakElement([1,2,3,1]) → 2 # nums[2]=3 is peak findPeakElement([1,2,1,3,5,6,4]) → 5 # nums[5]=6 is one valid peak findPeakElement([1]) → 0
binary searchslope direction
If nums[mid] < nums[mid+1], the peak must be to the right (the slope is going up). Otherwise it must be at mid or to the left. This lets you binary search.
Solution
from typing import List def findPeakElement(nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[mid + 1]: right = mid # peak at mid or to the left else: left = mid + 1 # going uphill to the right — peak is right return left
Complexity
Time: O(log n), Space: O(1).
M 32 Medium Arrays Greedy
Best Time to Buy and Sell Stock II
Given prices array, you may complete as many transactions as you like (buy and sell multiple times), but must sell before buying again. Maximize total profit.
Test Cases
maxProfit([7,1,5,3,6,4]) → 7 # buy day2(1),sell day3(5) + buy day4(3),sell day5(6) maxProfit([1,2,3,4,5]) → 4 # buy day1,sell day5 (or sum daily gains) maxProfit([7,6,4,3,1]) → 0 # no profit possible
greedysum all upswings
If tomorrow's price is higher than today's, buy today and sell tomorrow (collect every positive daily gain). You don't need to simulate actual buy/sell days — just summing all positive price differences works.
Solution
from typing import List def maxProfit(prices: List[int]) -> int: profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] # collect every upward move return profit
Complexity
Time: O(n), Space: O(1).
M 33 Medium Arrays Backtracking
Subsets
Given an integer array nums with unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.
Test Cases
subsets([1,2,3]) → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] subsets([0]) → [[],[0]]
iterative expansionbit manipulation alternative 2^n subsets
Start with [[]] (just the empty set). For each number, create new subsets by adding that number to every existing subset. This doubles the result set each time.
Solution
from typing import List # --- Iterative approach (clean and fast) --- def subsets(nums: List[int]) -> List[List[int]]: result = [[]] for num in nums: # For each existing subset, add a new one with num appended result += [subset + [num] for subset in result] return result # --- Backtracking approach --- def subsetsBacktrack(nums: List[int]) -> List[List[int]]: result = [] def bt(start: int, path: List[int]) -> None: result.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) bt(i + 1, path) path.pop() bt(0, []) return result
Complexity
Time: O(n × 2ⁿ) — 2ⁿ subsets, each up to n elements.
Space: O(n × 2ⁿ) — storing all subsets.
M 34 Medium Arrays
Rotate Array
Given an integer array nums, rotate it to the right by k steps in-place.
Test Cases
rotate([1,2,3,4,5,6,7], k=3) → [5,6,7,1,2,3,4] rotate([-1,-100,3,99], k=2) → [3,99,-1,-100] rotate([1,2], k=3) → [2,1] # k > n, so k = k % n = 1
three reversalsk %= n in-place O(1) space
Trick: reverse the whole array, then reverse the first k elements, then reverse the rest. Three reversals = O(1) space.
Solution
from typing import List def rotate(nums: List[int], k: int) -> None: n = len(nums) k %= n # handle k > n def reverse(l: int, r: int) -> None: while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1; r -= 1 reverse(0, n - 1) # reverse whole array reverse(0, k - 1) # reverse first k elements reverse(k, n - 1) # reverse the rest
Complexity
Time: O(n), Space: O(1).
Alternative Approach
Slice: nums[:] = nums[-k:] + nums[:-k] — clean one-liner but O(n) space.
M 35 Medium Design Stacks
Min Stack
Design a stack that supports push, pop, top, and getMin. All operations must be O(1). getMin retrieves the minimum element in the stack.
Test Cases
stack = MinStack() stack.push(-2); stack.push(0); stack.push(-3) stack.getMin() → -3 stack.pop() stack.top() → 0 stack.getMin() → -2
auxiliary min stackO(1) getMin
Keep a parallel "min stack" alongside the main stack. When you push, also push to the min stack if the new value is ≤ current min. When you pop, if the popped value equals the min stack top, pop the min stack too.
Solution
class MinStack: def __init__(self): self.stack = [] self.min_stack = [] # tracks running minimum def push(self, val: int) -> None: self.stack.append(val) # Push to min_stack if it would be the new minimum if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self) -> None: val = self.stack.pop() if val == self.min_stack[-1]: self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]
Complexity
Time: O(1) for all operations.
Space: O(n) — min_stack holds at most n elements.
M 36 Medium Strings Dynamic Programming
Word Break
Given a string s and a dictionary wordDict, return True if s can be segmented into a space-separated sequence of dictionary words.
Test Cases
wordBreak("leetcode", ["leet","code"]) → True wordBreak("applepenapple", ["apple","pen"]) → True wordBreak("catsandog", ["cats","dog","sand","and","cat"]) → False
bottom-up DPdp[i] = can reach index i set lookup O(1)
dp[i] = True means the first i characters of s can be broken into dictionary words. For each i, check all j < i: if dp[j] is True AND s[j:i] is in the dictionary, then dp[i] = True.
Solution
from typing import List def wordBreak(s: str, wordDict: List[str]) -> bool: word_set = set(wordDict) # O(1) lookup n = len(s) dp = [False] * (n + 1) dp[0] = True # empty string is always breakable for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n]
Complexity
Time: O(n²) — two nested loops; each substring check is O(n) string hashing (amortized).
Space: O(n) — dp array.
M 37 Medium Arrays Backtracking
Word Search
Given an m×n board of characters and a string word, return True if the word exists in the grid. The word can be constructed from adjacent (horizontal/vertical) cells, each used at most once.
Test Cases
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] exist(board, "ABCCED") → True exist(board, "SEE") → True exist(board, "ABCB") → False # can't reuse B
DFS backtrackingmark visited by mutation 4-directional search
For each cell that matches word[0], try DFS. At each DFS step: mark the cell as visited (e.g., overwrite with '#'), recurse on all 4 neighbors for word[idx+1], then restore the cell.
Solution
from typing import List def exist(board: List[List[str]], word: str) -> bool: rows, cols = len(board), len(board[0]) def dfs(r: int, c: int, idx: int) -> bool: if idx == len(word): return True if r < 0 or r >= rows or c < 0 or c >= cols: return False if board[r][c] != word[idx]: return False temp = board[r][c] board[r][c] = '#' # mark visited to prevent reuse found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1) or dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1)) board[r][c] = temp # restore (backtrack) return found for r in range(rows): for c in range(cols): if dfs(r, c, 0): return True return False
Complexity
Time: O(m × n × 4^L) where L = word length. Each cell can branch into 4 directions for L levels.
Space: O(L) — recursion depth equals word length.
M 38 Medium Arrays Dynamic Programming Binary Search
Longest Increasing Subsequence (LIS)
Given an array nums, return the length of the longest strictly increasing subsequence.
Test Cases
lengthOfLIS([10,9,2,5,3,7,101,18]) → 4 # [2,3,7,101] lengthOfLIS([0,1,0,3,2,3]) → 4 # [0,1,2,3] lengthOfLIS([7,7,7,7]) → 1
patience sortingbisect_left tails array
The O(n²) DP solution: dp[i] = LIS ending at index i. But there's an O(n log n) approach using "patience sorting" — maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. For each new number, use binary search to find where it fits.
Solution
import bisect from typing import List # O(n log n) — patience sorting with binary search def lengthOfLIS(nums: List[int]) -> int: tails = [] # tails[i] = smallest tail of all IS of length i+1 for num in nums: pos = bisect.bisect_left(tails, num) if pos == len(tails): tails.append(num) # extends the longest IS else: tails[pos] = num # replace: maintain smallest possible tail return len(tails) # O(n²) DP — simpler to understand def lengthOfLIS_DP(nums: List[int]) -> int: dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)
Complexity
Patience sorting: Time O(n log n), Space O(n)
DP: Time O(n²), Space O(n) — simpler, good for understanding; mention both in interviews.
M 39 Medium Strings Greedy Heap
Reorganize String
Given a string s, rearrange the characters so no two adjacent characters are the same. Return any valid rearrangement, or "" if impossible.
Test Cases
reorganizeString("aab") → "aba" reorganizeString("aaab") → "" # impossible: 3 a's but only 2 b's reorganizeString("vvvlo") → "vlvov" (or similar valid arrangement)
max-heapalways pick 2 most frequent impossible check
Greedy: always pick the two most frequent characters and place them together. This prevents the most-frequent character from becoming adjacent to itself. Impossible if any character has count > (len+1)//2.
Solution
import heapq from collections import Counter def reorganizeString(s: str) -> str: count = Counter(s) # Max-heap (negate freq for Python's min-heap) heap = [(-freq, ch) for ch, freq in count.items()] heapq.heapify(heap) result = [] while len(heap) >= 2: freq1, ch1 = heapq.heappop(heap) freq2, ch2 = heapq.heappop(heap) result.extend([ch1, ch2]) if freq1 + 1 < 0: heapq.heappush(heap, (freq1 + 1, ch1)) if freq2 + 1 < 0: heapq.heappush(heap, (freq2 + 1, ch2)) if heap: freq, ch = heapq.heappop(heap) if -freq > 1: return "" # more than 1 remaining: impossible result.append(ch) return "".join(result)
Complexity
Time: O(n log k) where k = unique characters (≤ 26). Each of n characters does a heap op.
Space: O(k) — heap size is at most k.
M 40 Medium Arrays Strings
String Compression
Given a list of characters chars, compress it in-place using the following algorithm: for each group of consecutive identical characters, write the character and then the count (if count > 1). Return the new length.
Test Cases
chars = ['a','a','b','b','c','c','c'] compress(chars) → 6, chars = ['a','2','b','2','c','3'] chars = ['a'] compress(chars) → 1, chars = ['a'] chars = ['a','b','b','b','b','b','b','b','b','b','b','b','b'] compress(chars) → 4, chars = ['a','b','1','2']
read/write pointersrun-length encoding str(count) for multi-digit counts
Use a read pointer to scan the original and a write pointer to write the compressed version back. Count consecutive identical chars, then write the char and (if count > 1) the digits of the count.
Solution
from typing import List def compress(chars: List[str]) -> int: write = read = 0 while read < len(chars): char = chars[read] count = 0 # Count the run of identical characters while read < len(chars) and chars[read] == char: read += 1 count += 1 chars[write] = char write += 1 if count > 1: for c in str(count): # handles multi-digit counts like '12' chars[write] = c write += 1 return write
Complexity
Time: O(n) — read pointer visits each character once.
Space: O(1) — in-place modification.
M 41 Medium Arrays Two Pointers
Sort Colors (Dutch National Flag)
Given an array with only values 0, 1, 2 (representing red, white, blue), sort in-place so all 0s come first, then 1s, then 2s. Do it in one pass with O(1) space.
Test Cases
sortColors([2,0,2,1,1,0]) → [0,0,1,1,2,2] sortColors([2,0,1]) → [0,1,2] sortColors([0]) → [0]
Dutch National Flag (3-way partition) low/mid/high pointers
Dijkstra's Dutch National Flag: three pointers — low (0s boundary), mid (current), high (2s boundary). Process mid: if 0, swap with low and advance both. If 2, swap with high and retreat high. If 1, just advance mid.
Solution
from typing import List def sortColors(nums: List[int]) -> None: low, mid, high = 0, 0, len(nums) - 1 while mid <= high: if nums[mid] == 0: nums[low], nums[mid] = nums[mid], nums[low] low += 1; mid += 1 elif nums[mid] == 1: mid += 1 else: # nums[mid] == 2 nums[mid], nums[high] = nums[high], nums[mid] high -= 1 # don't advance mid — newly swapped value unchecked
Complexity
Time: O(n) — single pass.
Space: O(1) — in-place.
M 42 Medium Arrays Greedy
Jump Game II
Given an array nums, return the minimum number of jumps to reach the last index. Assume you can always reach the end.
Test Cases
jump([2,3,1,1,4]) → 2 # jump 1→index1, then jump 3→end jump([2,3,0,1,4]) → 2 jump([1]) → 0 # already at end
greedy BFS layerscurr_end/curr_max
Think in "layers" like BFS. curr_end is the furthest you can reach in the current jump. When you pass curr_end, you must take another jump. Track curr_max as the furthest reachable in the next jump.
Solution
from typing import List def jump(nums: List[int]) -> int: jumps = 0 curr_end = 0 # furthest reachable with current jumps curr_max = 0 # furthest reachable with one more jump for i in range(len(nums) - 1): curr_max = max(curr_max, i + nums[i]) if i == curr_end: jumps += 1 curr_end = curr_max return jumps
Complexity
Time: O(n), Space: O(1).
M 43 Medium Strings Stacks
Decode String
Given an encoded string, decode it. The encoding rule: k[encoded_string] means encoded_string repeated k times.
Test Cases
decodeString("3[a]2[bc]") → "aaabcbc" decodeString("3[a2[c]]") → "accaccacc" decodeString("2[abc]3[cd]ef") → "abcabccdcdcdef"
stack for nested bracketsmulti-digit numbers
When you see '[', push (current_string, current_number) onto the stack and reset both. When you see ']', pop and build: new_string = popped_string + num × current_string.
Solution
def decodeString(s: str) -> str: stack = [] curr_str = "" curr_num = 0 for ch in s: if ch.isdigit(): curr_num = curr_num * 10 + int(ch) # handle multi-digit: "12[a]" elif ch == '[': stack.append((curr_str, curr_num)) # save state curr_str, curr_num = "", 0 elif ch == ']': prev_str, num = stack.pop() curr_str = prev_str + num * curr_str # expand else: curr_str += ch return curr_str
Complexity
Time: O(output length) — bounded by the decoded string length, not input length.
Space: O(nesting depth) — stack depth equals max bracket nesting level.
M 44 Medium Linked Lists Hash Map
Copy List with Random Pointer
A linked list where each node has next and random (which can point to any node or None). Return a deep copy of the list.
Test Cases
head = [[7,None],[13,0],[11,4],[10,2],[1,0]] # Each entry is [val, random_index] # Returns a deep copy with same structure
hash map old→new nodetwo passes
Two-pass approach: Pass 1 — create all new nodes and map old→new in a dict. Pass 2 — set next and random pointers of new nodes using the map.
Solution
from typing import Optional class Node: def __init__(self, val: int, next=None, random=None): self.val = val; self.next = next; self.random = random def copyRandomList(head: Optional[Node]) -> Optional[Node]: if not head: return None node_map = {} # old node → new node curr = head while curr: node_map[curr] = Node(curr.val) curr = curr.next curr = head while curr: if curr.next: node_map[curr].next = node_map[curr.next] if curr.random: node_map[curr].random = node_map[curr.random] curr = curr.next return node_map[head]
Complexity
Time: O(n) — two passes through the list.
Space: O(n) — hash map stores n node mappings.
Alternative Approach
Interleave approach: Insert copy nodes in-between originals (no hash map needed) — O(n) time, O(1) extra space. More complex code.
M 45 Medium Arrays Hash Set
Valid Sudoku
Determine if a 9×9 Sudoku board is valid. Each row, column, and 3×3 sub-box must contain digits 1–9 without repetition. Empty cells are '.'.
Test Cases
Valid board: standard 9x9 with no repeated digits in rows/cols/boxes → True board[0][0] = board[0][1] = '5' → False (duplicate in row 0) board[0][0] = board[1][0] = '5' → False (duplicate in col 0) board[0][0] = board[1][1] = '5' → False (duplicate in box 0)
9 row sets + 9 col sets + 9 box sets box index: (r//3)*3 + c//3
Use 27 sets: 9 for rows, 9 for columns, 9 for 3×3 boxes. For each cell, check all three sets. The box index for cell (r, c) is (r//3)*3 + (c//3).
Solution
from typing import List def isValidSudoku(board: List[List[str]]) -> bool: rows = [set() for _ in range(9)] cols = [set() for _ in range(9)] boxes = [set() for _ in range(9)] for r in range(9): for c in range(9): val = board[r][c] if val == '.': continue box_idx = (r // 3) * 3 + (c // 3) if val in rows[r] or val in cols[c] or val in boxes[box_idx]: return False rows[r].add(val); cols[c].add(val); boxes[box_idx].add(val) return True
Complexity
Time: O(1) — fixed 81 cells; doesn't grow with input.
Space: O(1) — 27 sets, each max size 9.
M 46 Medium Strings Backtracking
Letter Combinations of a Phone Number
Given a string of digits (2–9), return all possible letter combinations a phone keypad could represent.
Test Cases
letterCombinations("23") → ["ad","ae","af","bd","be","bf","cd","ce","cf"] letterCombinations("") → [] letterCombinations("2") → ["a","b","c"]
backtrackingphone mapping dict
Recurse: for each digit, try all its letters and move to the next digit. Base case: path length == len(digits) → add to results.
Solution
from typing import List def letterCombinations(digits: str) -> List[str]: if not digits: return [] phone = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' } result = [] def backtrack(idx: int, path: str) -> None: if idx == len(digits): result.append(path) return for ch in phone[digits[idx]]: backtrack(idx + 1, path + ch) backtrack(0, "") return result
Complexity
Time: O(4ⁿ × n) where n = number of digits (4 because '7' and '9' have 4 letters).
Space: O(n) — recursion depth equals number of digits.
M 47 Medium Arrays Monotonic Stack
Daily Temperatures
Given a temperatures array, return an array answer where answer[i] is the number of days until a warmer temperature. If none exists, answer[i] = 0.
Test Cases
dailyTemperatures([73,74,75,71,69,72,76,73]) → [1,1,4,2,1,1,0,0] dailyTemperatures([30,40,50,60]) → [1,1,1,0] dailyTemperatures([30,60,90]) → [1,1,0]
monotonic stackstore indices next greater element pattern
Use a stack of indices. Walk forward — when the current temperature is warmer than the stack's top temperature, the top of the stack found its answer. Pop it and compute the difference in indices.
Solution
from typing import List def dailyTemperatures(temperatures: List[int]) -> List[int]: n = len(temperatures) result = [0] * n stack = [] # indices of days awaiting a warmer day for i, temp in enumerate(temperatures): while stack and temperatures[stack[-1]] < temp: idx = stack.pop() result[idx] = i - idx # days waited stack.append(i) return result
Complexity
Time: O(n) — each index pushed and popped at most once.
Space: O(n) — stack can hold all indices in worst case (descending temperatures).
M 48 Medium Recursion Binary Exponentiation
Pow(x, n)
Implement pow(x, n) — x raised to the power n. Handle negative n and n = 0.
Test Cases
myPow(2.0, 10) → 1024.0 myPow(2.1, 3) → 9.261000... myPow(2.0, -2) → 0.25 myPow(0.0, 0) → 1.0
fast exponentiationhalving the exponent negative n handling
x^n = (x^2)^(n//2) × (x if n is odd). This halves the exponent each step: O(log n) multiplications instead of O(n). Handle n < 0 by using 1/x with |n|.
Solution
def myPow(x: float, n: int) -> float: if n < 0: x, n = 1 / x, -n result = 1.0 while n: if n % 2 == 1: # odd exponent: multiply in one more x result *= x x *= x # square x n //= 2 # halve n return result
Complexity
Time: O(log n) — exponent halved each iteration.
Space: O(1) — iterative approach, no call stack.
M 49 Medium Strings Stacks
Simplify Path
Given an absolute Unix path, simplify it. . means current dir, .. means parent dir. Remove double slashes and trailing slashes.
Test Cases
simplifyPath("/home/") → "/home" simplifyPath("/../") → "/" # can't go above root simplifyPath("/home//foo/") → "/home/foo" simplifyPath("/a/./b/../../c/") → "/c"
split('/')stack for directory stack edge cases: '.', '..', empty parts
Split by '/'. Ignore empty strings and '.'. For '..', pop the stack (if non-empty). For any real directory name, push it. Join the stack with '/' at the end.
Solution
def simplifyPath(path: str) -> str: stack = [] for part in path.split('/'): if part == '..': if stack: stack.pop() # go up one directory elif part and part != '.': stack.append(part) # valid directory name # '' (double slash) and '.' are both ignored return '/' + '/'.join(stack)
Complexity
Time: O(n) where n is the path length.
Space: O(n) — stack can hold up to n/2 directory names.
← Medium Part 1 Hard Problems →