## PROBLEM LINK:

**Author**: Rishabh Karnad

**Tester**: Omkar Prabhu

**Editorialist**: Rishabh Karnad

## DIFFICULTY:

Easy

# PRE-REQUISITES:

[Dynamic Programming][2]## PROBLEM:

Given a rectangular grid of dimensions m x n, in which each cell consists of either a 1 or a 0, find out whether there exists a path from (m,0) to (0,n) which only passes through cells containing 1s, while only making the following moves:

- (i,j) -> (i-1,j)
*[An UP or NORTH move]* - (i,j) -> (i,j+1)
*[A RIGHT or EAST move]*

## SOLUTION:

This problem has a typical dynamic programming solution.

The grid itself is represented as a matrix, say **grid[m][n]**, whose contents are 0s and 1s and taken as input. A second matrix, say **path_exists[m][n]** is used to contain the information about the existence of a path to every cell; if **path_exists[i][j]** is **1**, then there is a path from (m,0) to (i,j) and if it is **0**, there is no path to (i,j).

The algorithm begins at (m,0) and may proceed row-by-row, column-by-column or diagonal-wise. For simplicity, we consider a row-by-row approach. Two loops are required: an inner **j** loop for columns and an outer **i** loop for rows. For each cell (i,j), we check if:

- Either or both
**path_exists[i+1][j]**and**path_exists[i][j-1]**is**1**. If yes, it means a path exists to one of those cells (i+1,j) or (i,j-1). -
**grid[i][j]**is**1**, meaning that a path can pass through it.

If both conditions are satisfied, then the path to (i+1,j) or (i,j-1) can be extended to (i,j). Hence a path to (i,j) exists and we mark **path_exists[i][j]** as **1**. Otherwise, we mark it **0**.

When the algorithm terminates, the value of **path_exists[0][n]** will indicate the existence of a path between (m,0) and (0,n).

## TIME COMPLEXITY:

Since each cell must be checked and operation on each cell takes constant time, time complexity is O(n^2).

## SPACE COMPLEXITY:

O(n^2)

It can be reduced to O(n) by keeping track of only two rows at a time in **path_exists** and the algorithm can still be made to work correctly.

## AUTHORâ€™S SOLUTION

Will be provided soon.