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

Time Complexity: Unique Paths in Grid DP

O(m * n)

Understanding Time Complexity

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

Specifically, how does the number of steps change when the grid gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function uniquePaths(m: number, n: number): number {
  const dp: number[][] = Array(m).fill(0).map(() => Array(n).fill(1));
  for (let i = 1; i < m; i++) {
    for (let 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 the number of unique paths from the top-left to bottom-right of an m by n grid using dynamic programming.

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, roughly (m-1) * (n-1) times.

How Execution Grows With Input

As the grid size grows, the number of operations grows roughly with the total 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: Operations grow roughly as the product of m and n, so doubling grid size roughly quadruples work.

Final Time Complexity

Time Complexity: O(m * n)

This means the time needed grows proportionally with 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 store results, so it calculates each cell once, avoiding repeated work.

Interview Connect

Understanding this time complexity shows you can analyze how dynamic programming improves efficiency by avoiding repeated calculations.

Self-Check

"What if we added obstacles that block some cells? How would the time complexity change?"