Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

171. Unique Paths II

MediumDay 49 of 60Dynamic Programming

Same robot, same moves (only right or down), but now the grid obstacleGrid has obstacles marked with 1 and free cells marked with 0. The robot cannot step on an obstacle. Return the number of distinct paths from the top-left to the bottom-right corner.

Example 1
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
The rock in the middle leaves only the path along the top edge and the path along the left edge.
Example 2
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Constraints
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] is 0 or 1
  • The answer is at most 2 * 10^9
Hints
Frequently asked at: Amazon, Google, Meta
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min