Unique Paths to Goal

Given a grid, find the number of unique paths a robot can take to move from the start position to the finish.

We'll cover the following

Statement

Given a robot located at the top-left corner of an m×nm \times n grid (marked start in the illustration below), determine the number of unique paths that the robot could take from start to finish while avoiding all obstacles on the grid.

The robot can only move either down or right at any time. The robot tries to reach the bottom-right corner of the grid (marked finish in the illustration below).

An obstacle is marked as 1, and an unoccupied space is marked as 0 in the grid.

Example

Consider the 3×33 \times 3 grid below, there is one obstacle in the middle of this grid. There are 2 unique paths to reach from start to finish.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.