Unique Path Finder

Unique Path Finder

February 9, 2024
medium
dynamic programming

Problem Statement #

Given a grid of dimensions m x n, each cell in the grid can be either land (1) or water (0). You start at the top-left corner of the grid (0, 0) and can move either down or right at any point in time, but you can’t move through water. Find the number of unique paths from the top-left corner to the bottom-right corner (m-1, n-1).

Constraints:

  • The grid is a 2D array of integers, where grid[i][j] is 1 for land and 0 for water.
  • 1 <= m, n <= 100
  • The start (0,0) and the end (m-1,n-1) cells will be land.

Example:

Input: grid = [
  [1,1,0],
  [1,1,0],
  [0,1,1]
]
Output: 2
Explanation: There are two unique paths without walking through water.

Solution Approach: #

Algorithm Steps:

  1. Dynamic Programming (DP) Approach: We use a 2D DP array dp of the same dimensions as the grid, where dp[i][j] represents the number of unique paths to reach (i, j) from (0, 0).

  2. Base Case Initialization: Initialize dp[0][0] as 1 if the starting cell is land. For the first row and first column, if a cell is reachable (land) and its previous cell has a path to it, set its value to 1.

  3. Filling the DP Table: Iterate through the grid starting from (1, 1). For each cell (i, j), if it’s land (grid[i][j] == 1), update the DP table as follows: dp[i][j] = dp[i-1][j] + dp[i][j-1]. This equation adds the number of paths to the current cell from the cell above it and from the cell left to it.

  4. Handling Water Cells: If a cell is water (grid[i][j] == 0), set dp[i][j] to 0 as it’s not possible to pass through.

  5. Result: The value at dp[m-1][n-1] gives the total number of unique paths from the top-left to the bottom-right corner.

Code: # 

def uniquePaths(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    if grid[0][0] == 1: dp[0][0] = 1
    
    for i in range(1, m):
        if grid[i][0] == 1 and dp[i-1][0] == 1:
            dp[i][0] = 1
            
    for j in range(1, n):
        if grid[0][j] == 1 and dp[0][j-1] == 1:
            dp[0][j] = 1
            
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[-1][-1]

Time Complexity: #

  • O(m*n): We iterate through each cell of the grid exactly once, where m is the number of rows and n is the number of columns in the grid.

Space Complexity: #

  • O(m*n): We use a 2D DP array of size m x n to store the number of unique paths to each cell.

This problem is a variation of the classic unique paths problem, incorporating obstacles (water in this case), which requires dynamic programming to efficiently solve while ensuring paths only go through valid cells.