loading...
Nlogn

Find if a path is possible in a NxM for reaching bottom right form top left

mayankjoshi profile image mayank joshi Updated on ・2 min read

interview-question (4 Part Series)

1) Find if a path is possible in a NxM for reaching bottom right form top left 2) Find all possible subset of a given set 3) Print all permutations of a string with unique characters 4) DP - Coin Change: Find the number of ways of representing n cents

A robot sitting on the upper left corner(0,0) of a grid with r rows and c columns.
The robot can only move in two directions: right or down, but certain cells are “off-limits” such that the robot cannot step on them. Design an algorithm to find if there exists a path for the robot for reaching the bottom right from the top left.

The problem requires an understanding of Dynamic Programming. Read here…


The first grid has many possible paths of reaching destination(e) form source(s) and one of them is shown using green. In the second grid, there is no possible path to reach the destination from the source.

Algorithm

  1. Let’s start from the end(r,c) and start walking in up(r-1,c) and left(r,c-1) direction.
  2. If we encounter an off-limit, we will take the alternate path.
  3. If both the path contains the off-limit, stop returning no possible path.
  4. Repeat the above steps until we reach the source and return true(path is possible).

Since the subproblems involve repetition, Dynamic Programming is used to speed up and reduce time complexity.

Implementation of above algorithm in CPP

In the above program, the dp[i][j] is used to store the values of subproblems. It is assigned -1, which tells that the current step/subproblem is not computed and -2, tells that it is invalid of the off-limit grid.

Output

true

TIME COMPLEXITY

The time complexity of the above program is O(RC), where R is the number of Rows(r) and C is the number of Columns(c) using Dynamic Programming.


Follow us to stay updated with interview and competitive programming related questions. 👨‍💻 👨‍💻

interview-question (4 Part Series)

1) Find if a path is possible in a NxM for reaching bottom right form top left 2) Find all possible subset of a given set 3) Print all permutations of a string with unique characters 4) DP - Coin Change: Find the number of ways of representing n cents

Posted on Mar 22 by:

mayankjoshi profile

mayank joshi

@mayankjoshi

I love system design and most of the time I find myself learning or designing one of them. I'm highly active on twitter, So ping me there.

Nlogn

nlogn is a Computer Science portal specially designed to help you prepare for product-based companies interviews by practicing a wide variety of problem-related to system Desing, Data-Structure and much more.

Discussion

markdown guide