Unique Paths in Grid DP in DSA Java - 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.

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

This code calculates how many unique ways there are 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: Filling each cell in the dp table once.
• How many times: The nested loops run for (m-1) * (n-1) times, covering all cells except the first row and column.

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 (9*9)
100 x 100	~9,801 (99*99)
1000 x 1000	~998,001 (999*999)

Pattern observation: The operations grow roughly with 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 number of cells in the grid.

Common Mistake

[X] Wrong: "Since there are many paths, the time must be exponential."

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

Interview Connect

Understanding how nested loops over a grid affect time helps you explain and optimize many grid-based problems confidently.

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 obstacles in the grid

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

Solution

1. Step 1: Understand the problem statement

   The problem asks for counting all possible paths from the top-left corner to the bottom-right corner of a grid, moving only right or down.

2. Step 2: Identify the correct interpretation

   Among the options, only counting the number of ways to move right or down matches the problem description.

3. Final Answer:

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

4. Quick Check:

   Unique Paths = Counting ways moving right/down [OK]

Hint: Unique Paths count moves right/down only [OK]

Common Mistakes:

• Confusing unique paths with shortest path
• Thinking about obstacles instead of paths
• Mixing path count with path sum

2. Which of the following Java code snippets correctly initializes a 2D DP array dp for a grid of size m x n?

easy

A. int[][] dp = new int[m][n];

B. int dp[][] = new int[n][m];

C. int dp = new int[m][n];

D. int[][] dp = new int[m];

Solution

1. Step 1: Recall Java 2D array syntax

   In Java, a 2D array is declared as int[][] dp = new int[m][n]; where m is rows and n is columns.

2. Step 2: Check each option

   int[][] dp = new int[m][n]; matches correct syntax. int dp[][] = new int[n][m]; swaps dimensions. int dp = new int[m][n]; uses wrong type. int[][] dp = new int[m]; misses second dimension.

3. Final Answer:

   int[][] dp = new int[m][n]; -> Option A

4. Quick Check:

   Java 2D array = int[][] dp = new int[m][n] [OK]

Hint: Use int[][] dp = new int[m][n] for 2D arrays [OK]

Common Mistakes:

• Swapping row and column sizes
• Missing second dimension in array creation
• Using single brackets for 2D arrays

3. What is the output of the following Java code snippet for m = 3 and n = 3?

int m = 3, n = 3;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
  }
}
System.out.println(dp[m-1][n-1]);

medium

A. 3

B. 10

C. 6

D. 1

Solution

1. Step 1: Initialize first row and column

   First row and first column are set to 1, representing only one way to reach those cells.

2. Step 2: Fill dp table using sum of top and left cells

   Calculate 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. Step 3: Recalculate final cell

   dp[2][2] = 6 is incorrect for 3x3 grid unique paths. The correct number of unique paths in a 3x3 grid is 6, but let's verify carefully:
   Actually, the number of unique paths from top-left to bottom-right in a 3x3 grid moving only right or down is 6.
   Let's trace the dp table:
   Row 0: [1,1,1]
   Row 1: [1,2,3]
   Row 2: [1,3,6]
   So dp[2][2] = 6 is correct.

4. Final Answer:

   6 -> Option C

5. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Sum ways from top and left cells to fill dp [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Adding dp[i][j-1] and dp[i-1][j] incorrectly
• Off-by-one errors in loops

4. Identify the bug in the following Java code for computing unique paths in an m x n grid:

int[][] dp = new int[m][n];
for (int i = 0; i <= m; i++) dp[i][0] = 1;
for (int j = 0; j <= n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
  }
}

medium

A. Loops use <= causing ArrayIndexOutOfBoundsException

B. dp array is not initialized

C. Sum formula is incorrect

D. No bug, code is correct

Solution

1. Step 1: Check loop boundaries for dp array

   Arrays in Java are 0-indexed, so valid indices are 0 to m-1 and 0 to n-1. Using <= m or <= n causes index out of bounds.

2. Step 2: Identify the error cause

   Loops with condition i <= m and j <= n try to access dp[m][0] or dp[0][n], which do not exist.

3. Final Answer:

   Loops use <= causing ArrayIndexOutOfBoundsException -> Option A

4. Quick Check:

   Array indices must be less than size [OK]

Hint: Use < not <= for array indices in loops [OK]

Common Mistakes:

• Using <= instead of < in loops
• Ignoring zero-based indexing
• Assuming array size includes upper bound 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. Use recursion without memoization to handle obstacles

B. 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, Handle first row and column carefully considering obstacles

C. Set dp[i][j] = 1 if grid[i][j] == 1; else 0, Sum all dp values at the end

D. Ignore obstacles and calculate paths normally, Obstacles don't affect path count

Solution

1. Step 1: Understand obstacle effect on paths

   If a cell has an obstacle, no path can go through it, so dp value must be 0.

2. Step 2: Modify DP formula and initialization

   Set dp[i][j] = 0 if obstacle; else sum of dp from top and left. Initialize dp[0][0] = 1 only if no obstacle. First row and column must consider obstacles to stop paths beyond them.

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, Handle first row and column carefully considering obstacles -> Option B

4. Quick Check:

   Obstacles block paths, dp=0 there [OK]

Hint: Set dp=0 for obstacles, sum neighbors otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Not initializing dp[0][0] correctly
• Not stopping path count after obstacle in first row/column