Question Banks
DSA Advanced 50 Pattern Problems
50 problems from NeetCode 150 and Striver SDE Sheet organized by pattern. Complete Python solutions with complexities and follow-ups.
Problems P26–P75 organized by algorithmic pattern. Covers NeetCode 150 and Striver SDE Sheet essentials. Each tagged with difficulty level for calibration.
Arrays & Hashing
P26: Contains Duplicate Easy · SDE1
Problem: Given integer array, return true if any value appears at least twice.
Approach: Hash set. If element already in set, return true.
def contains_duplicate(nums):
return len(nums) != len(set(nums))Complexity: O(n) time, O(n) space.
Follow-up: Contains Duplicate II within distance k? Use sliding window hash set of size k.
P27: Valid Anagram Easy · SDE1
Problem: Given two strings s and t, return true if t is an anagram of s.
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t)Complexity: O(n) time, O(1) space (26 chars max).
Follow-up: What if inputs contain Unicode? → Counter still works. What about streaming? → Single count array, increment/decrement.
P28: Group Anagrams Medium · SDE2
Problem: Given array of strings, group anagrams together.
Approach: Use sorted string as key in hash map.
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())Complexity: O(n · k log k) time where k = max string length.
Follow-up: Avoid sorting? → Use tuple of 26 char counts as key: O(n·k).
P29: Top K Frequent Elements Medium · SDE2
Problem: Given integer array and k, return the k most frequent elements.
Approach: Bucket sort by frequency. Index = frequency, value = elements with that frequency.
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
for num in buckets[i]:
result.append(num)
if len(result) == k:
return result
return resultComplexity: O(n) time, O(n) space.
Follow-up: Streaming data? → Min-heap of size k: O(n log k).
P30: Product of Array Except Self Medium · SDE2
Problem: Return array where answer[i] = product of all elements except nums[i]. No division.
Approach: Prefix products left-to-right, then suffix products right-to-left.
def product_except_self(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 resultComplexity: O(n) time, O(1) extra space (output not counted).
Follow-up: Handle zeros? → Count zeros. If >1 zero, all products are 0. If exactly 1, only that position is non-zero.
P31: Longest Consecutive Sequence Medium · SDE2
Problem: Given unsorted array, find length of longest consecutive elements sequence. Must be O(n).
Approach: Hash set. For each number, only start counting if num-1 is NOT in set (start of sequence).
def longest_consecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set: # start of sequence
length = 1
while num + length in num_set:
length += 1
longest = max(longest, length)
return longestComplexity: O(n) time, O(n) space.
Follow-up: Streaming data with deletions? → Union-Find approach.
Two Pointers
P32: Valid Palindrome Easy · SDE1
Problem: Check if string is palindrome considering only alphanumeric characters (case-insensitive).
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return TrueComplexity: O(n) time, O(1) space.
P33: 3Sum Medium · SDE2
Problem: Find all unique triplets that sum to zero.
Approach: Sort + fix one element + two-pointer on remainder.
def three_sum(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:
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
elif total < 0:
lo += 1
else:
hi -= 1
return resultComplexity: O(n²) time, O(1) extra space.
Follow-up: 3Sum Closest return sum nearest to target. Same pattern, track closest diff.
P34: Container With Most Water Medium · SDE2
Problem: Given heights array, find two lines that form container holding most water.
Approach: Two pointers from edges. Move the shorter side inward (greedy).
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
best = max(best, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return bestComplexity: O(n) time, O(1) space.
P35: Remove Duplicates from Sorted Array II Medium · SDE2
Problem: Allow at most 2 duplicates in-place. Return new length.
def remove_duplicates(nums):
if len(nums) <= 2:
return len(nums)
slow = 2
for fast in range(2, len(nums)):
if nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slowComplexity: O(n) time, O(1) space.
P36: 4Sum Medium · SDE3
Problem: Find all unique quadruplets summing to target.
Approach: Sort + fix two elements + two-pointer on rest. Skip duplicates at each level.
def four_sum(nums, target):
nums.sort()
result = []
n = len(nums)
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]: continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]: continue
lo, hi = j+1, n-1
while lo < hi:
total = nums[i] + nums[j] + nums[lo] + nums[hi]
if total == target:
result.append([nums[i], nums[j], 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
elif total < target: lo += 1
else: hi -= 1
return resultComplexity: O(n³) time.
Stack
P37: Valid Parentheses Easy · SDE1
Problem: Check if string of brackets is valid.
def is_valid(s):
stack = []
openers = "([" + chr(123)
closers = ")]" + chr(125)
for char in s:
if char in openers:
stack.append(char)
elif char in closers:
if not stack:
return False
idx = closers.index(char)
if stack[-1] != openers[idx]:
return False
stack.pop()
return not stackComplexity: O(n) time, O(n) space.
P38: Min Stack Medium · SDE1
Problem: Design stack supporting push, pop, top, and getMin all O(1).
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
self.min_stack.append(min(val, self.min_stack[-1] if self.min_stack else val))
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]Complexity: All operations O(1).
Follow-up: O(1) space? → Store difference from min. Negative diff means new min was set.
P39: Evaluate Reverse Polish Notation Medium · SDE2
Problem: Evaluate arithmetic expression in RPN (postfix).
def eval_rpn(tokens):
stack = []
for t in tokens:
if t in '+-*/':
b, a = stack.pop(), stack.pop()
if t == '+': stack.append(a + b)
elif t == '-': stack.append(a - b)
elif t == '*': stack.append(a * b)
else: stack.append(int(a / b)) # truncate toward zero
else:
stack.append(int(t))
return stack[0]Complexity: O(n) time, O(n) space.
P40: Daily Temperatures Medium · SDE2
Problem: Given temps array, return days until warmer temp for each day.
Approach: Monotonic decreasing stack storing indices.
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of decreasing temps
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
j = stack.pop()
result[j] = i - j
stack.append(i)
return resultComplexity: O(n) time, O(n) space.
P41: Largest Rectangle in Histogram Hard · SDE3
Problem: Find largest rectangular area in histogram.
Approach: Monotonic increasing stack. For each bar, find how far left/right it can extend.
def largest_rectangle(heights):
stack = [] # indices of increasing heights
max_area = 0
for i, h in enumerate(heights + [0]): # sentinel
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_areaComplexity: O(n) time, O(n) space.
Follow-up: Maximal Rectangle in 2D matrix? → Apply histogram approach per row.
Binary Search
P42: Search a 2D Matrix Medium · SDE1
Problem: Each row sorted, first element of each row > last of previous. Search target.
Approach: Treat as 1D sorted array. Binary search on virtual index.
def search_matrix(matrix, target):
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1
while lo <= hi:
mid = (lo + hi) // 2
val = matrix[mid // n][mid % n]
if val == target: return True
elif val < target: lo = mid + 1
else: hi = mid - 1
return FalseComplexity: O(log(m·n)) time.
P43: Koko Eating Bananas Medium · SDE2
Problem: Find minimum eating speed k to finish all piles within h hours.
Approach: Binary search on answer (speed). Check feasibility for each candidate.
import math
def min_eating_speed(piles, h):
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 loComplexity: O(n · log(max)) time.
P44: Find Minimum in Rotated Sorted Array Medium · SDE2
Problem: Find minimum element in a rotated sorted array (no duplicates).
def find_min(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]Complexity: O(log n) time.
P45: Median of Two Sorted Arrays Hard · SDE3+
Problem: Find median of two sorted arrays in O(log(min(m,n))).
Approach: Binary search on partition of smaller array. Ensure left halves ≤ right halves.
def find_median(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
left1 = nums1[i-1] if i > 0 else float('-inf')
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[j-1] if j > 0 else float('-inf')
right2 = nums2[j] if j < n else float('inf')
if left1 <= right2 and left2 <= right1:
if (m + n) % 2:
return max(left1, left2)
return (max(left1, left2) + min(right1, right2)) / 2
elif left1 > right2:
hi = i - 1
else:
lo = i + 1Complexity: O(log(min(m,n))) time, O(1) space.
P46: Split Array Largest Sum Hard · SDE3+
Problem: Split array into k subarrays minimizing the largest subarray sum.
Approach: Binary search on answer. Check if array can be split into ≤k parts with max sum ≤ mid.
def split_array(nums, k):
def can_split(max_sum):
parts, curr = 1, 0
for num in nums:
if curr + num > max_sum:
parts += 1
curr = num
else:
curr += num
return parts <= 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 loComplexity: O(n · log(sum - max)) time.
Linked List
P47: Reverse Linked List Easy · SDE1
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevComplexity: O(n) time, O(1) space.
Follow-up: Reverse between positions m and n? → Same 3-pointer trick with boundary bookmarks.
P48: Linked List Cycle (Floyd's) Easy · SDE1
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseComplexity: O(n) time, O(1) space.
Follow-up: Find the cycle start? → After detection, reset one pointer to head, advance both by 1. They meet at start.
P49: Merge Two Sorted Lists Easy · SDE1
def merge_two_lists(l1, l2):
dummy = curr = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.nextComplexity: O(m+n) time, O(1) space.
P50: Copy List with Random Pointer Medium · SDE2
Approach: Interleave cloned nodes, then set random pointers, then separate lists.
def copy_random_list(head):
if not head: return None
# Interleave: A->A'->B->B'->C->C'
curr = head
while curr:
clone = Node(curr.val, curr.next, None)
curr.next = clone
curr = clone.next
# Set random pointers
curr = head
while curr:
if curr.random:
curr.next.random = curr.random.next
curr = curr.next.next
# Separate lists
curr = head
clone_head = head.next
while curr:
clone = curr.next
curr.next = clone.next
clone.next = clone.next.next if clone.next else None
curr = curr.next
return clone_headComplexity: O(n) time, O(1) extra space.
P51: Reorder List Medium · SDE2
Problem: L0→L1→...→Ln becomes L0→Ln→L1→Ln-1→...
Approach: Find middle → reverse second half → merge alternating.
def reorder_list(head):
# Find middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow.next
slow.next = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Merge alternating
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2Complexity: O(n) time, O(1) space.
Trees
P52: Invert Binary Tree Easy · SDE1
def invert_tree(root):
if not root: return None
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return rootComplexity: O(n) time, O(h) space.
P53: Lowest Common Ancestor of BST Medium · SDE2
def lowest_common_ancestor(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return rootComplexity: O(h) time, O(1) space.
Follow-up: General binary tree (not BST)? → Post-order recursion checking both subtrees.
P54: Binary Tree Level Order Traversal Medium · SDE1
from collections import deque
def level_order(root):
if not root: return []
result, 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)
result.append(level)
return resultComplexity: O(n) time, O(n) space.
P55: Validate BST Medium · SDE2
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
if not root: return True
if root.val <= lo or root.val >= hi:
return False
return (is_valid_bst(root.left, lo, root.val) and
is_valid_bst(root.right, root.val, hi))Complexity: O(n) time, O(h) space.
P56: Diameter of Binary Tree Medium · SDE2
def diameter_of_tree(root):
diameter = 0
def height(node):
nonlocal diameter
if not node: return 0
left = height(node.left)
right = height(node.right)
diameter = max(diameter, left + right)
return 1 + max(left, right)
height(root)
return diameterComplexity: O(n) time, O(h) space.
P57: Construct Tree from Preorder + Inorder Medium · SDE3
def build_tree(preorder, inorder):
if not preorder: return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = build_tree(preorder[1:mid+1], inorder[:mid])
root.right = build_tree(preorder[mid+1:], inorder[mid+1:])
return rootComplexity: O(n²) naive. O(n) with inorder index hashmap.
Heap / Priority Queue
P58: Task Scheduler Medium · SDE2
Problem: Given tasks with cooldown n, find minimum intervals to complete all.
from collections import Counter
def least_interval(tasks, n):
counts = Counter(tasks)
max_freq = max(counts.values())
max_count = sum(1 for v in counts.values() if v == max_freq)
return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)Complexity: O(n) time, O(1) space (26 chars).
P59: Reorganize String Medium · SDE2
Problem: Rearrange string so no two adjacent characters are same.
import heapq
from collections import Counter
def reorganize_string(s):
counts = Counter(s)
max_heap = [(-cnt, ch) for ch, cnt in counts.items()]
heapq.heapify(max_heap)
result = []
prev = (0, '')
while max_heap:
cnt, ch = heapq.heappop(max_heap)
result.append(ch)
if prev[0] < 0:
heapq.heappush(max_heap, prev)
prev = (cnt + 1, ch)
return ''.join(result) if len(result) == len(s) else ""Complexity: O(n log k) time where k = unique chars.
P60: K Closest Points to Origin Medium · SDE2
import heapq
def k_closest(points, k):
return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)Complexity: O(n log k) with heap, or O(n) average with quickselect.
P61: Merge K Sorted Lists (Heap) Hard · SDE3
import heapq
def merge_k_lists(lists):
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst.val, i, lst))
dummy = curr = ListNode(0)
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextComplexity: O(N log k) time where N = total nodes.
P62: Sliding Window Median Hard · Staff
Problem: Return median of each sliding window of size k.
Approach: Two heaps (max + min) with lazy deletion of expired elements.
import heapq
from collections import defaultdict
def median_sliding_window(nums, k):
lo, hi = [], [] # max-heap (neg), min-heap
def balance():
while len(lo) > len(hi) + 1:
heapq.heappush(hi, -heapq.heappop(lo))
while len(hi) > len(lo):
heapq.heappush(lo, -heapq.heappop(hi))
def get_median():
if k % 2:
return -lo[0]
return (-lo[0] + hi[0]) / 2.0
result = []
for i in range(len(nums)):
heapq.heappush(lo, -nums[i])
heapq.heappush(hi, -heapq.heappop(lo))
balance()
if i >= k:
out = nums[i - k]
if out <= -lo[0]:
lo.remove(-out); heapq.heapify(lo)
else:
hi.remove(out); heapq.heapify(hi)
balance()
if i >= k - 1:
result.append(get_median())
return resultComplexity: O(nk) due to remove. Optimal: O(n log k) with lazy deletion + size tracking.
Backtracking
P63: Subsets Medium · SDE2
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resultComplexity: O(n · 2ⁿ) time and space.
P64: Combination Sum Medium · SDE2
Problem: Find all unique combinations that sum to target (can reuse elements).
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i])
path.pop()
candidates.sort()
backtrack(0, [], target)
return resultComplexity: O(2^(t/min)) where t=target, min=smallest candidate.
P65: Permutations Medium · SDE2
def permute(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.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 resultComplexity: O(n! · n) time.
P66: N-Queens Hard · SDE3
def solve_n_queens(n):
result = []
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def backtrack(row, board):
if row == n:
result.append([''.join(r) for r in board])
return
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)
board[row][col] = 'Q'
backtrack(row + 1, board)
board[row][col] = '.'
cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)
board = [['.' for _ in range(n)] for _ in range(n)]
backtrack(0, board)
return resultComplexity: O(n!) time.
P67: Sudoku Solver Hard · SDE3+
def solve_sudoku(board):
def is_valid(row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
box_r, box_c = 3 * (row // 3), 3 * (col // 3)
for i in range(box_r, box_r + 3):
for j in range(box_c, box_c + 3):
if board[i][j] == num:
return False
return True
def solve():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if is_valid(i, j, num):
board[i][j] = num
if solve():
return True
board[i][j] = '.'
return False
return True
solve()Complexity: O(9^(empty cells)) worst case, pruning makes it fast in practice.
Graphs
P68: Rotting Oranges Medium · SDE2
Problem: Multi-source BFS how many minutes until all oranges rot?
from collections import deque
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2: queue.append((r, c))
elif grid[r][c] == 1: fresh += 1
if fresh == 0: return 0
minutes = 0
while queue:
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
minutes += 1
return minutes - 1 if fresh == 0 else -1Complexity: O(m·n) time and space.
P69: Pacific Atlantic Water Flow Medium · SDE2
Approach: DFS from each ocean's border cells. Return intersection.
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
pacific, atlantic = set(), set()
def dfs(r, c, visited, prev_height):
if (r, c) in visited or r < 0 or c < 0 or r >= rows or c >= cols:
return
if heights[r][c] < prev_height:
return
visited.add((r, c))
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc, visited, heights[r][c])
for c in range(cols):
dfs(0, c, pacific, 0)
dfs(rows-1, c, atlantic, 0)
for r in range(rows):
dfs(r, 0, pacific, 0)
dfs(r, cols-1, atlantic, 0)
return list(pacific & atlantic)Complexity: O(m·n) time and space.
P70: Graph Valid Tree Medium · SDE2
Problem: Given n nodes and edges, check if it forms a valid tree (connected + no cycles).
def valid_tree(n, edges):
if len(edges) != n - 1:
return False # tree has exactly n-1 edges
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return False # cycle
parent[pu] = pv
return TrueComplexity: O(n · α(n)) ≈ O(n) time.
P71: Cheapest Flights Within K Stops Medium · SDE3
Approach: Modified Bellman-Ford limited to k+1 iterations.
def 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] != float('inf'):
temp[v] = min(temp[v], prices[u] + w)
prices = temp
return prices[dst] if prices[dst] != float('inf') else -1Complexity: O(k · E) time, O(n) space.
P72: Swim in Rising Water Hard · SDE3+
Problem: Find minimum time t to swim from (0,0) to (n-1,n-1). At time t, can visit cells with elevation ≤ t.
Approach: Dijkstra with max-elevation as cost.
import heapq
def swim_in_water(grid):
n = len(grid)
visited = set()
heap = [(grid[0][0], 0, 0)]
while heap:
t, r, c = heapq.heappop(heap)
if (r, c) in visited: continue
visited.add((r, c))
if r == n-1 and c == n-1:
return t
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < n and 0 <= nc < n and (nr,nc) not in visited:
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
return -1Complexity: O(n² log n) time.
Dynamic Programming
P73: Longest Common Subsequence Medium · SDE2
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[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[m][n]Complexity: O(mn) time, O(mn) space. Optimize to O(min(m,n)) with rolling array.
Follow-up: Print the actual LCS? → Backtrack from dp[m][n].
P74: Coin Change Medium · SDE2
Problem: Minimum coins to make amount. Return -1 if impossible.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1Complexity: O(amount · n) time, O(amount) space.
Follow-up: Count number of ways (not minimum)? → Change min to sum.
P75: Partition Equal Subset Sum Medium · SDE2
Problem: Can array be partitioned into two subsets with equal sum? (0/1 Knapsack)
def can_partition(nums):
total = sum(nums)
if total % 2: return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target]Complexity: O(n · target) time, O(target) space.
Follow-up: Minimize the difference between two subset sums? → Find largest reachable sum ≤ total/2.