Unique Paths in Grid DP in DSA Python - Time & Space Complexity

Time Complexity: Unique Paths in Grid DP

O(m * n)

Understanding Time Complexity

We want to know how the time needed to find unique paths in a grid changes as the grid size grows.

How does the number of steps grow when the grid gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

This code calculates the number of unique ways to move from the top-left to the bottom-right of an m by n grid, moving only down or right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops filling the dp table.
• How many times: The inner addition runs for each cell except the first row and column, about (m-1) * (n-1) times.

How Execution Grows With Input

As the grid size grows, the number of operations grows roughly with the number of cells.

Input Size (m x n)	Approx. Operations
10 x 10	81
100 x 100	9,801
1000 x 1000	998,001

Pattern observation: Operations grow roughly by the product of m and n, so doubling both dimensions roughly quadruples the work.

Final Time Complexity

Time Complexity: O(m * n)

This means the time needed grows proportionally to the total number of cells in the grid.

Common Mistake

[X] Wrong: "Because there are many paths, the time complexity is exponential."

[OK] Correct: The code uses dynamic programming to build solutions step-by-step, so it only calculates each cell once, avoiding repeated work.

Interview Connect

Understanding how dynamic programming reduces repeated calculations is a key skill that shows you can write efficient code for grid problems.

Self-Check

"What if we used recursion without memoization? How would the time complexity change?"

Practice

1. What does the problem "Unique Paths in Grid DP" ask you to find?
Unique Paths means:

easy

A. The maximum sum path from top-left to bottom-right in a grid

B. The shortest path length from top-left to bottom-right in a grid

C. The number of ways to move from top-left to bottom-right in a grid moving only right or down

D. The number of obstacles in the grid

Solution

1. Step 1: Understand the problem goal

   The problem asks for counting all possible ways to reach the bottom-right cell from the top-left cell by moving only right or down.

2. Step 2: Clarify movement constraints

   Only moves allowed are right or down, so paths are unique sequences of these moves.

3. Final Answer:

   The number of ways to move from top-left to bottom-right in a grid moving only right or down -> Option C

4. Quick Check:

   Unique Paths = Count of right/down moves sequences [OK]

Hint: Count paths by moving only right or down [OK]

Common Mistakes:

• Thinking about shortest path length instead of count
• Including diagonal moves
• Confusing with maximum sum path

2. Which of the following Python code snippets correctly initializes a 2D list dp of size m x n with all values set to 1?

easy

A. dp = [[1]*m for _ in range(n)]

B. dp = [[1]*n for _ in range(m)]

C. dp = [[1]*n]*m

D. dp = [1]*m*n

Solution

1. Step 1: Understand 2D list initialization

   We want a list with m rows and n columns, each cell initialized to 1.

2. Step 2: Check each option

   dp = [[1]*n for _ in range(m)] uses list comprehension correctly to create m lists each of length n. dp = [[1]*m for _ in range(n)] swaps m and n. dp = [[1]*n]*m creates shallow copies causing aliasing issues. dp = [1]*m*n creates a flat list, not 2D.

3. Final Answer:

   dp = [[1]*n for _ in range(m)] -> Option B

4. Quick Check:

   Correct 2D list init = dp = [[1]*n for _ in range(m)] [OK]

Hint: Use list comprehension for 2D lists to avoid aliasing [OK]

Common Mistakes:

• Using [[1]*n]*m causing all rows to reference same list
• Swapping m and n dimensions
• Creating flat list instead of 2D

3. What is the output of the following code?

def unique_paths(m, n):
    dp = [[1]*n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

print(unique_paths(3, 3))

medium

A. 6

B. 3

C. 9

D. 1

Solution

1. Step 1: Understand DP table filling

   dp[i][j] stores number of unique paths to cell (i,j). First row and column are 1 because only one way to reach them.

2. Step 2: Calculate dp values for 3x3 grid

   dp[1][1] = dp[0][1] + dp[1][0] = 1+1=2
   dp[1][2] = dp[0][2] + dp[1][1] = 1+2=3
   dp[2][1] = dp[1][1] + dp[2][0] = 2+1=3
   dp[2][2] = dp[1][2] + dp[2][1] = 3+3=6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Sum paths from top and left neighbors [OK]

Common Mistakes:

• Returning dp[m][n] instead of dp[m-1][n-1]
• Not initializing first row and column to 1
• Mixing up indices in loops

4. Find the error in the following code for unique paths and select the fix:

def unique_paths(m, n):
    dp = [[0]*n]*m
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

medium

A. Return dp[m][n] instead of dp[m-1][n-1]

B. Change loops to start from 0 instead of 1

C. Initialize dp with ones instead of zeros

D. Change dp initialization to dp = [[0]*n for _ in range(m)]

Solution

1. Step 1: Identify dp initialization problem

   Using dp = [[0]*n]*m creates shallow copies of the same row, so updating one row updates all rows.

2. Step 2: Fix dp initialization

   Use list comprehension dp = [[0]*n for _ in range(m)] to create independent rows.

3. Final Answer:

   Change dp initialization to dp = [[0]*n for _ in range(m)] -> Option D

4. Quick Check:

   Independent rows fix aliasing issue [OK]

Hint: Use list comprehension for 2D list to avoid shared references [OK]

Common Mistakes:

• Using [[0]*n]*m causing all rows to be same object
• Changing loop ranges unnecessarily
• Returning wrong dp index

5. Given a grid with obstacles represented by 1s and empty spaces by 0s, how would you modify the unique paths DP solution to count paths avoiding obstacles?
Choose the correct approach:

hard

A. Set dp[i][j] = 0 if grid[i][j] == 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1], initialize dp[0][0] = 1 if no obstacle

B. Ignore obstacles and run normal unique paths DP

C. Set dp[i][j] = 1 for obstacles and 0 otherwise

D. Use recursion without memoization to handle obstacles

Solution

1. Step 1: Handle obstacles in DP initialization

   If a cell has an obstacle (1), no paths can go through it, so dp[i][j] = 0.

2. Step 2: Update dp values considering obstacles

   For empty cells (0), dp[i][j] = sum of paths from top and left neighbors if they are not blocked.

3. Final Answer:

   Set dp[i][j] = 0 if grid[i][j] == 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1], initialize dp[0][0] = 1 if no obstacle -> Option A

4. Quick Check:

   Obstacles block paths, so dp = 0 there [OK]

Hint: Set dp to 0 at obstacles, sum neighbors otherwise [OK]

Common Mistakes:

• Ignoring obstacles in DP calculation
• Setting dp=1 at obstacle cells
• Using recursion without memo causing inefficiency