Unique Path Finder
February 9, 2024
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 topleft 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 topleft corner to the bottomright corner (m1, n1)
.
Constraints:
 The grid is a 2D array of integers, where
grid[i][j]
is1
for land and0
for water. 1 <= m, n <= 100
 The start
(0,0)
and the end(m1,n1)
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:

Dynamic Programming (DP) Approach: We use a 2D DP array
dp
of the same dimensions as the grid, wheredp[i][j]
represents the number of unique paths to reach(i, j)
from(0, 0)
. 
Base Case Initialization: Initialize
dp[0][0]
as1
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 to1
. 
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[i1][j] + dp[i][j1]
. This equation adds the number of paths to the current cell from the cell above it and from the cell left to it. 
Handling Water Cells: If a cell is water (
grid[i][j] == 0
), setdp[i][j]
to0
as it’s not possible to pass through. 
Result: The value at
dp[m1][n1]
gives the total number of unique paths from the topleft to the bottomright 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[i1][0] == 1:
dp[i][0] = 1
for j in range(1, n):
if grid[0][j] == 1 and dp[0][j1] == 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[i1][j] + dp[i][j1]
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 andn
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.