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.