Practice
1. Consider the following code snippet for the Keys and Rooms problem:
def canVisitAllRooms(rooms):
n = len(rooms)
visited = [false] * n
count = 0
def dfs(room):
nonlocal count
if visited[room]:
return
visited[room] = true
count += 1
if count == n:
return
for key in rooms[room]:
dfs(key)
dfs(0)
return count == n
rooms = [[1], [2], [3], []]
print(canVisitAllRooms(rooms))count after the DFS call completes?easy
Solution
Step 1: Trace DFS calls starting from room 0
Visit room 0 (count=1), then room 1 (count=2), then room 2 (count=3), then room 3 (count=4).Step 2: Confirm all rooms visited
Since count equals total rooms (4), DFS stops early and returns true.Final Answer:
Option D -> Option DQuick Check:
All rooms reachable, count matches number of rooms [OK]
Hint: Count increments once per unique room visited [OK]
Common Mistakes:
- Off-by-one error counting rooms
- Assuming count stops at 3 instead of 4
- Confusing count with length of visited list
2. What is the time complexity of the Union-Find based algorithm to check if a graph with V vertices and E edges is bipartite?
medium
Solution
Step 1: Identify number of union-find operations
Each edge triggers at most one union operation, so total operations are O(E).Step 2: Analyze union-find operation complexity
Union-Find with path compression and union by rank has amortized time O(α(V)) per operation, where α is inverse Ackermann function.Final Answer:
Option C -> Option CQuick Check:
Union-Find complexity is near-linear, not quadratic or logarithmic [OK]
Hint: Union-Find operations are almost constant time amortized [OK]
Common Mistakes:
- Assuming union is linear time
- Confusing sorting necessity
- Ignoring inverse Ackermann function
3. The following BFS code attempts to find the max area of an island in a grid. Identify the line that contains a subtle bug that can cause incorrect area calculation or runtime errors.
from collections import deque
def maxAreaOfIsland(grid):
rows, cols = len(grid), len(grid[0])
visited = set()
max_area = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and (r, c) not in visited:
queue = deque([(r, c)])
area = 0
while queue:
row, col = queue.popleft()
# Bug: Missing visited check here
visited.add((row, col))
area += 1
for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
if grid[nr][nc] == 1 and (nr, nc) not in visited:
queue.append((nr, nc))
max_area = max(max_area, area)
return max_area
medium
Solution
Step 1: Check neighbor addition line
The code adds neighbors without verifying if nr, nc are within grid boundaries, risking index out of range errors.Step 2: Confirm other lines are correct
Visited check before adding to queue is present, queue initialization and max_area update are correct.Final Answer:
Option A -> Option AQuick Check:
Boundary checks missing cause runtime errors [OK]
Hint: Always check grid boundaries before accessing neighbors [OK]
Common Mistakes:
- Forgetting boundary checks
- Not checking visited before adding to queue
- Adding visited check after popping queue
4. What is the time complexity of the optimal BFS approach for the Surrounded Regions problem on an m x n board?
medium
Solution
Step 1: Analyze BFS traversal
Each cell is enqueued and dequeued at most once during BFS marking, so total operations are proportional to the number of cells, m*n.Step 2: Consider neighbor checks
Each cell checks up to 4 neighbors, but this is constant factor, so complexity remains O(m*n).Final Answer:
Option A -> Option AQuick Check:
Linear scan plus BFS over all cells is O(m*n) [OK]
Hint: BFS visits each cell once, so O(m*n) time [OK]
Common Mistakes:
- Confusing BFS with brute force approach leading to O(m*n*(m+n)).
- Counting neighbor checks as multiplicative rather than constant factor.
- Assuming only boundary cells matter for complexity.
5. Suppose the problem is modified so that water can flow uphill by at most 1 unit of height difference (i.e., from a cell to a neighbor if neighbor's height ≥ current height - 1). Which modification to the BFS approach correctly handles this variant?
hard
Solution
Step 1: Understand uphill flow constraint
Allowing uphill flow by 1 unit means edges have weights or costs, not uniform.Step 2: BFS is insufficient
Standard BFS assumes uniform edge cost; to handle varying constraints, Dijkstra's algorithm with a priority queue is needed.Step 3: Modify algorithm
Use priority queue BFS (Dijkstra) to explore cells with minimal cost respecting height difference constraints.Final Answer:
Option D -> Option DQuick Check:
Uphill flow requires weighted graph traversal -> Dijkstra [OK]
Hint: Uphill flow needs weighted BFS -> Dijkstra [OK]
Common Mistakes:
- Trying to fix with simple BFS condition change
- Running BFS from every cell causes TLE