Unique Paths

📋

Problem

Imagine a robot starting at the top-left corner of a grid, trying to reach the bottom-right corner by only moving right or down. How many unique ways can it reach the destination?

Given two integers m and n representing the number of rows and columns of a grid, return the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1,n-1). You can only move either down or right at any point in time.

1 ≤ m, n ≤ 100The answer is guaranteed to fit in a 32-bit integer.

Edge cases: m = 1, n = 1 → 1 (only one cell, start is end)m = 1, n = 10 → 1 (only one row, only one path moving right)m = 10, n = 1 → 1 (only one column, only one path moving down)

</>

IDE

def uniquePaths(m: int, n: int) -> int:public int uniquePaths(int m, int n)int uniquePaths(int m, int n)function uniquePaths(m, n)

def uniquePaths(m, n):
    # Write your solution here
    pass

class Solution {
    public int uniquePaths(int m, int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    // Write your solution here
    return 0;
}

function uniquePaths(m, n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Greedy approach that always moves right or always moves down, missing other paths.✅ Use DP recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] to count all paths.

Wrong: 0Incorrect base case handling, returning 0 for single cell grid or invalid initialization.✅ Initialize dp[0][0] = 1 and return 1 if m=1 and n=1.

Wrong: Incorrect large numberOff-by-one errors in DP indexing causing wrong accumulation of paths.✅ Ensure loops and dp indices run from 0 to m-1 and 0 to n-1 correctly.

Wrong: TLEUsing brute force recursion without memoization or DP.✅ Implement DP with O(m*n) time complexity to avoid exponential time.

✓

Test Cases

Focus on handling smallest grids and initializing DP correctly.

Watch out for common algorithmic pitfalls like greedy traps and indexing errors.

Optimize your solution to run efficiently on large inputs using DP.

t1_01basic

Input{"m":3,"n":7}

Expected28

⏱ Performance - must finish in 2000ms

There are 28 unique paths from top-left to bottom-right moving only right or down in a 3x7 grid.

💡 Consider how many ways to reach each cell from the start.

💡 Use dynamic programming: dp[i][j] = dp[i-1][j] + dp[i][j-1].

💡 Initialize first row and column with 1s, then fill dp table accordingly.

Why it failed: Incorrect output means DP recurrence or base cases are wrong. Fix by ensuring dp[i][j] = dp[i-1][j] + dp[i][j-1] with dp[0][j] = 1 and dp[i][0] = 1. This is the canonical example test.

✓ Correctly computed unique paths for the canonical 3x7 grid.

t1_02basic

Input{"m":3,"n":3}

Expected6

⏱ Performance - must finish in 2000ms

In a 3x3 grid, there are 6 unique paths moving only right or down from top-left to bottom-right.

💡 Count paths by summing ways from top and left neighbors.

💡 Apply DP with dp[i][j] = dp[i-1][j] + dp[i][j-1].

💡 Remember edges have only one path, initialize dp accordingly.

Why it failed: If output is not 6, likely DP initialization or recurrence is incorrect. Ensure dp first row and column are set to 1 and recurrence sums top and left cells. This basic test checks core logic.

✓ Correctly computed unique paths for 3x3 grid.

t2_01edge

Input{"m":1,"n":1}

Expected1

⏱ Performance - must finish in 2000ms

Only one cell, start equals end, so exactly one unique path.

💡 Check base case when grid is 1x1.

💡 DP table should handle minimal dimensions correctly.

💡 Return 1 immediately or ensure dp[0][0] = 1.

Why it failed: Output not 1 means base case for single cell grid is mishandled. Fix by returning 1 if m==1 and n==1 or initializing dp[0][0] = 1 properly. This is the single element edge case.

✓ Correctly handled single cell grid base case.

t2_02edge

Input{"m":1,"n":10}

Expected1

⏱ Performance - must finish in 2000ms

Only one row, only one path moving right across all columns.

💡 When m=1, only horizontal moves possible.

💡 DP first row should be all 1s.

💡 Ensure dp initialization sets dp[0][j] = 1 for all j.

Why it failed: Output not 1 means first row initialization is incorrect. Fix by setting dp[0][j] = 1 for all columns j. This is the single row edge case.

✓ Correctly handled single row grid.

t2_03edge

Input{"m":10,"n":1}

Expected1

⏱ Performance - must finish in 2000ms

Only one column, only one path moving down across all rows.

💡 When n=1, only vertical moves possible.

💡 DP first column should be all 1s.

💡 Ensure dp initialization sets dp[i][0] = 1 for all i.

Why it failed: Output not 1 means first column initialization is incorrect. Fix by setting dp[i][0] = 1 for all rows i. This is the single column edge case.

✓ Correctly handled single column grid.

t3_01corner

Input{"m":2,"n":2}

Expected2

⏱ Performance - must finish in 2000ms

Two paths: right->down or down->right in a 2x2 grid.

💡 Check if your solution counts all possible paths, not just one.

💡 Avoid greedy approach that picks only one direction first.

💡 Use DP to sum paths from top and left neighbors for each cell.

Why it failed: Output less than 2 means greedy approach used, missing some paths. Fix by using DP recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1]. This is the greedy trap test.

✓ Correctly counted all unique paths, avoiding greedy trap.

t3_02corner

Input{"m":3,"n":4}

Expected10

⏱ Performance - must finish in 2000ms

In a 3x4 grid, there are 10 unique paths moving only right or down.

💡 Check if your solution handles boundaries correctly.

💡 Verify that dp table indices and loops cover all cells.

💡 Ensure no off-by-one errors in dp array indexing.

Why it failed: Output incorrect due to off-by-one indexing errors in DP loops. Fix by iterating dp from 0 to m-1 and 0 to n-1 correctly and initializing dp[0][0] = 1. This is the off-by-one indexing test.

✓ Correctly handled DP indexing and boundaries.

t3_03corner

Input{"m":4,"n":4}

Expected20

⏱ Performance - must finish in 2000ms

In a 4x4 grid, there are 20 unique paths moving only right or down.

💡 Avoid confusing this problem with unbounded knapsack or other DP types.

💡 Remember moves are restricted to right or down only.

💡 Use DP with two dimensions representing grid coordinates.

Why it failed: Output incorrect due to treating moves as unbounded or allowing invalid moves. Fix by restricting moves to only right or down and using dp[i][j] = dp[i-1][j] + dp[i][j-1]. This is the move restriction confusion test.

✓ Correctly implemented move restrictions and DP.

t4_01performance

Input{"m":100,"n":100}

Expected0

⏱ Performance - must finish in 2000ms

Grid size 100x100, DP solution O(m*n) = 10,000 operations must complete within 2 seconds.

💡 Brute force recursion is exponential and will time out here.

💡 Use bottom-up DP with O(m*n) time complexity.

💡 Optimize space by using a single array for DP if needed.

Why it failed: TLE occurs due to exponential brute force recursion. Fix by implementing DP with O(m*n) time complexity. This is the performance complexity test.

✓ Efficient DP solution runs within time limits.

Practice

1. What is the time complexity of the bottom-up DP solution for the Cherry Pickup problem on an n x n grid, where dp is a 3D array indexed by step and two row positions of the players?

medium

A. O(4^n) due to exploring all possible paths for two players

B. O(n^3) because there are O(n) steps and O(n^2) states for the two players' rows, each computed in constant time

C. O(n^4) since for each dp state, four previous states are checked

D. O(n^2) as the dp only tracks positions of two players without step dimension

Solution

1. Step 1: Identify number of states

   There are 2n-1 steps, and for each step, possible row positions for player 1 and player 2 are each O(n), so total states are O(n^3).

2. Step 2: Analyze transitions per state

   Each dp state checks up to 4 previous states in O(1) time, so total time is O(n^3).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   3D dp with O(n^3) states and constant transitions [OK]

Hint: Count states x transitions carefully [OK]

Common Mistakes:

• Confusing number of states with number of transitions
• Assuming exponential time due to recursion
• Ignoring that step dimension limits valid states

2. 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

A. O(m^3) because checking all squares requires nested loops

B. O(m * n * min(m,n)) because of checking all possible square sizes

C. O(m * n) because each cell is processed once with constant time updates

D. O(m + n) because only rows and columns are iterated separately

Solution

1. Step 1: Identify loops in the code

   Two nested loops iterate over rows and columns, each cell processed once.

2. Step 2: Understand DP update cost

   Each dp update is O(1), no nested checks for squares inside loops.

3. Final Answer:

   Option C -> Option C

4. Quick 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

3. What is the time and space complexity of the space-optimized bottom-up dynamic programming solution for the Minimum Path Sum problem on an m x n grid?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m*n), Space: O(m)

C. Time: O(2^(m+n)), Space: O(m+n)

D. Time: O(m*n), Space: O(n)

Solution

1. Step 1: Identify time complexity

   The algorithm iterates over each cell once, so time is O(m*n).

2. Step 2: Identify space complexity

   Space optimized DP uses a single 1D array of length n, so space is O(n), not O(m*n) or O(m).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single dp array of size n updated row by row [OK]

Hint: Space optimized DP uses one row array, not full matrix [OK]

Common Mistakes:

• Assuming space is O(m*n) due to 2D dp
• Confusing recursion stack space with DP space
• Mistaking m for n in space complexity

4. Identify the bug in the following code snippet for minimum score triangulation of a polygon:

medium

A. Line missing dp[i][j] = float('inf') before minimization

B. Line initializing dp array with zeros

C. Loop boundaries for k from i+1 to j-1

D. Return statement returning dp[0][n-1]

Solution

1. Step 1: Check dp initialization inside loops

   dp[i][j] must be set to infinity before checking for minimal cost; otherwise, dp[i][j] starts at 0 and may never update correctly.

2. Step 2: Confirm other lines are correct

   dp array initialization, loop boundaries, and return statement are correct and standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without dp[i][j] = float('inf'), minimal cost calculation is incorrect [OK]

Hint: Always initialize dp[i][j] before minimization [OK]

Common Mistakes:

• Forgetting dp initialization
• Off-by-one in loops
• Mixing indices i,j,k

5. Suppose the Cherry Pickup problem is modified so that players can revisit cells multiple times (i.e., cycles allowed), and cherries are replenished after being picked (can be collected multiple times). Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Use the same 3D DP with memoization but remove the check that prevents revisiting cells.

B. Apply a greedy approach that always moves players to the next cell with the highest cherry count.

C. Use a 4D DP tracking both players' full positions and number of visits per cell to avoid double counting.

D. Switch to a shortest path algorithm like Dijkstra on a state graph representing both players' positions and steps, allowing cycles.

Solution

1. Step 1: Understand the impact of allowing revisits and replenished cherries

   Cycles and replenished cherries mean the problem is no longer acyclic and DP assumptions break down.

2. Step 2: Identify suitable algorithm

   Modeling the problem as a shortest path on a state graph with both players' positions and steps allows handling cycles and repeated cherry collection correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP fails with cycles; shortest path algorithms handle repeated states [OK]

Hint: Cycles break DP; use graph shortest path [OK]

Common Mistakes:

• Removing DP constraints without changing algorithm
• Adding dimensions to DP without handling cycles
• Using greedy which ignores global optimality