Minimum Path Sum in Grid in DSA C - 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.

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    for (int i = 1; i < m; i++)
        grid[i][0] += grid[i-1][0];
    for (int j = 1; j < n; j++)
        grid[0][j] += grid[0][j-1];
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] += (grid[i-1][j] < grid[i][j-1]) ? grid[i-1][j] : grid[i][j-1];
        }
    }
    return grid[m-1][n-1];
}
    

This code calculates the minimum 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 traversing the grid cells.
• How many times: Outer loop runs m-1 times, inner loop runs n-1 times, so roughly m x n 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	About 100 operations
100 x 100	About 10,000 operations
1000 x 1000	About 1,000,000 operations

Pattern observation: Doubling the grid size roughly quadruples the operations, showing growth proportional to the number of cells.

Final Time Complexity

Time Complexity: O(m x n)

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

Common Mistake

[X] Wrong: "The time grows exponentially because there are many paths."

[OK] Correct: The code uses dynamic programming to avoid repeating calculations, so it only visits each cell once, not all paths.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves efficiency by avoiding repeated work, a key skill in problem solving.

Self-Check

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