Minimum Path Sum in Grid in DSA Typescript - Time & Space Complexity

Time Complexity: Minimum Path Sum in Grid

O(m x n)

Understanding Time Complexity

We want to know how the time needed to find the minimum path sum 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.

function minPathSum(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
  dp[0][0] = grid[0][0];
  for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
  return dp[m - 1][n - 1];
}
    

This code finds the smallest sum path from the top-left to the bottom-right of a grid, moving only down or right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops that fill the dp table for each cell in the grid.
• How many times: The inner loop runs for each cell except the first row and column, so roughly m x n times.

How Execution Grows With Input

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

Input Size (m x n)	Approx. Operations
10 x 10	About 100 operations
100 x 100	About 10,000 operations
1000 x 1000	About 1,000,000 operations

Pattern observation: Operations grow roughly proportional to the total number of cells, so doubling rows and columns quadruples work.

Final Time Complexity

Time Complexity: O(m x n)

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

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity is O(m + n)."

[OK] Correct: The loops are nested, so each cell is processed once, making the total work multiply, not add.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming efficiently solves grid path problems, a common interview topic.

Self-Check

"What if we allowed moving diagonally as well? How would the time complexity change?"