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. Consider the following bottom-up DP code for the Strange Printer problem. What is the final returned value when the input string is "aba"?

easy

A. 3

B. 4

C. 1

D. 2

Solution

1. Step 1: Compress input string "aba"

   Compression does not change string since no consecutive duplicates: s = "aba", n=3.

2. Step 2: Trace dp table filling

   Base cases: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1. For length=2: - dp[0][1]: dp[0][0]+1=2, s[0]!=s[1], so dp[0][1]=2 - dp[1][2]: dp[1][1]+1=2, s[1]!=s[2], so dp[1][2]=2 For length=3: - dp[0][2]: dp[0][1]+1=3 Check k=0: s[0]==s[2] ('a'=='a'), dp[0][0]+dp[1][1]=1+1=2 < 3, so dp[0][2]=2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches known minimal turns for "aba" [OK]

Hint: Check dp merging when s[k] == s[j] reduces turns [OK]

Common Mistakes:

• Forgetting to merge intervals when characters match

2. What is the time complexity of the bottom-up DP solution for the Triangle minimum path sum problem with n rows, and why?

medium

A. O(n^2) because each element in the triangle is processed once

B. O(2^n) because of the exponential number of paths

C. O(n) because each row is processed once

D. O(n^3) because of nested loops over rows and columns

Solution

1. Step 1: Count total elements in triangle

   Triangle has 1 + 2 + ... + n = n(n+1)/2 elements, which is O(n^2).

2. Step 2: Analyze loops

   Outer loop runs n times, inner loop runs up to n times per iteration, total O(n^2) operations.

3. Final Answer:

   Option A -> Option A

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

3. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants

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

5. Suppose the problem changes so that you can move down to the same column or adjacent columns multiple times, but you want to find the minimum falling path sum where you can reuse rows multiple times (i.e., you can revisit rows). Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Use the original DP but memoize results to avoid recomputation

B. Use the same bottom-up DP but allow cycles by iterating until no dp changes occur

C. Switch to a shortest path algorithm like Bellman-Ford on a graph representing allowed moves

D. Apply greedy approach picking minimum adjacent values repeatedly

Solution

1. Step 1: Understand the variant with row reuse

   Allowing revisiting rows means cycles in the path graph, which breaks the acyclic assumption of DP.

2. Step 2: Identify suitable algorithm

   Model the problem as a graph with edges representing allowed moves and use Bellman-Ford to find shortest paths with possible cycles.

3. Step 3: Why other options fail

   Bottom-up DP assumes acyclic progression; greedy ignores global optimality; memoization doesn't handle cycles properly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Bellman-Ford handles negative cycles and repeated nodes [OK]

Hint: Cycles require graph shortest path algorithms, not DP [OK]

Common Mistakes:

• Trying to reuse DP without cycle handling
• Assuming memoization solves cycles