Number Of Ways To Traverse Graph

Tags

Number Of Ways To Traverse Graph

Category

Dynamic Programming

Difficulty

Medium

Problem Statement

Given a grid with width columns and height rows, find the number of unique paths from the top-left corner to the bottom-right corner. You can only move right or down at each step.

Intuition

At any cell (i, j), you can only arrive from the cell above (i-1, j) or the cell to the left (i, j-1). Therefore, the number of ways to reach (i, j) is the sum of the ways to reach those two cells. This creates a natural DP recurrence. The first row and first column each have exactly one path (all right moves or all down moves, respectively).

An alternative mathematical insight: you need exactly (height - 1) down moves and (width - 1) right moves, for a total of (height + width - 2) moves. The number of unique orderings is the binomial coefficient C(height + width - 2, height - 1).

Approach

DP Approach

  1. Create a 2D table of size height x width.
  2. Initialize all cells in the first row and first column to 1.
  3. For each remaining cell (i, j): dp[i][j] = dp[i-1][j] + dp[i][j-1].
  4. Return dp[height-1][width-1].

Mathematical Approach

  1. Compute the binomial coefficient C(height + width - 2, min(height, width) - 1).

Pseudocode

function numberOfWaysToTraverseGraph(width, height):
    dp = 2D array of size height x width

    for i from 0 to height - 1:
        dp[i][0] = 1
    for j from 0 to width - 1:
        dp[0][j] = 1

    for i from 1 to height - 1:
        for j from 1 to width - 1:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[height - 1][width - 1]

Time & Space Complexity

  • DP Approach:
    • Time: O(height * width). Each cell is computed once.
    • Space: O(height * width) for the table. Can be optimized to O(min(height, width)) using a single row.
  • Mathematical Approach:
    • Time: O(height + width) to compute the binomial coefficient.
    • Space: O(1).

Key Insights

  • This is equivalent to Pascal's Triangle: the value at each cell is the sum of the cell above and to the left.
  • The combinatorial formula C(n+m-2, n-1) gives an O(n+m) time, O(1) space solution.
  • The problem is a special case of counting lattice paths.
  • Space optimization is straightforward since each row only depends on the previous row.

Edge Cases

  • 1 x 1 grid: there is exactly 1 path (you are already at the destination).
  • 1 x n or n x 1 grid: there is exactly 1 path (all moves in one direction).
  • Large grids: the number of paths can grow very large; may need big integer support.

Linked mentions