Recommended
Practice
1. Consider the following Python code implementing the space-optimized DP solution for counting unique paths with obstacles. Given the input grid below, what is the value of the dp array after processing the second row (i=1)?
Input grid:
[[0,0,0],
[0,1,0],
[0,0,0]]
def uniquePathsWithObstacles(obstacleGrid):
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [0]*n
dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 1:
dp[j] = 0
else:
if j > 0:
dp[j] += dp[j-1]
return dp[-1]
easy
Solution
Step 1: Initialize dp after first row (i=0)
dp starts as [1,0,0]. After processing first row (all zeros), dp updates to [1,1,1].Step 2: Process second row (i=1)
At j=0, obstacleGrid[1][0]=0, dp[0] remains 1.
At j=1, obstacleGrid[1][1]=1 (obstacle), dp[1] set to 0.
At j=2, obstacleGrid[1][2]=0, dp[2] += dp[1] -> dp[2] = 1 + 0 = 1.
Resulting dp: [1, 0, 1]Final Answer:
Option D -> Option DQuick Check:
dp correctly zeroes obstacle cell and accumulates paths [OK]
Hint: Obstacles zero dp cells, dp[j] accumulates from dp[j-1] [OK]
Common Mistakes:
- Forgetting to zero dp[j] on obstacle
- Mis-updating dp[j] before dp[j-1]
- Confusing row and column indices
2. What is the time complexity of the space-optimized bottom-up DP solution for the Cheapest Flights Within K Stops problem, given n cities, E flights, and maximum K stops?
medium
Solution
Step 1: Identify loops in the algorithm
The outer loop runs K+1 times, and the inner loop iterates over all E flights to relax edges.Step 2: Calculate total complexity
Each iteration processes E edges, so total time is O(K * E). No nested loops over n^2 or log factors appear.Final Answer:
Option A -> Option AQuick Check:
Algorithm iterates over edges K+1 times [OK]
Hint: Outer loop K+1 times, inner loop over E edges [OK]
Common Mistakes:
- Confusing E with n^2
- Assuming Dijkstra complexity
- Counting recursion stack space
3. What is the time complexity of the space-optimized bottom-up DP solution for the Maximal Square problem on an m x n matrix, and why might some candidates incorrectly think it is higher?
medium
Solution
Step 1: Identify loops in the code
Two nested loops iterate over rows and columns, each cell processed once.Step 2: Understand DP update cost
Each dp update is O(1), no nested checks for squares inside loops.Final Answer:
Option C -> Option CQuick Check:
DP avoids checking all squares explicitly [OK]
Hint: DP processes each cell once with constant work [OK]
Common Mistakes:
- Confusing brute force with DP complexity
- Assuming nested loops check all squares
- Ignoring constant time DP updates
4. What is the time complexity of the bottom-up DP solution for the Triangle minimum path sum problem with n rows, and why?
medium
Solution
Step 1: Count total elements in triangle
Triangle has 1 + 2 + ... + n = n(n+1)/2 elements, which is O(n^2).Step 2: Analyze loops
Outer loop runs n times, inner loop runs up to n times per iteration, total O(n^2) operations.Final Answer:
Option A -> Option AQuick Check:
Each element processed once in nested loops [OK]
Hint: Sum of rows is O(n^2), so time is O(n^2) [OK]
Common Mistakes:
- Confusing number of rows with total elements
- Assuming exponential complexity due to recursion
- Overestimating complexity due to nested loops
5. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Unique Paths problem on an
m x n grid?medium
Solution
Step 1: Identify loops in the code
The solution uses two nested loops: outer loop runs m-1 times, inner loop runs n-1 times.Step 2: Calculate total operations
Total operations ≈ (m-1) * (n-1) -> O(m * n). No extra hidden loops or recursion stack.Final Answer:
Option D -> Option DQuick Check:
Nested loops over m and n -> O(m*n) [OK]
Hint: Nested loops over m and n -> O(m*n) [OK]
Common Mistakes:
- Confusing with recursion exponential time
- Forgetting loops multiply complexity