Grokking Meta Coding Interview
Ask Author
Back to course home

0% completed

Vote For New Content
Shortest Path in Binary Matrix (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a matrix of size m x n, return the length of the shortest path from the top-left corner (0,0) to the bottom-right corner (N-1, N-1). If there is no such path, the output should be -1.

Follow the rules below while calculating the shortest path.

  • You can move horizontally, vertically, and diagonally to adjacent cells.
  • The visited cell should be 0.
  • The path length is counted as the number of steps taken.

Examples

  1. Example 1:
  • Input:
[[0, 0, 0], 
 [0, 1, 0], 
 [0, 0, 0]]
  • Expected Output: 4
  • Justification: The shortest path is (0, 0) -> (1, 0) -> (2, 1) -> (2, 2), totaling 4 steps.
  1. Example 2:
  • Input:
[[0, 1, 0], 
 [0, 0, 0], 
 [0, 1, 0]]
  • Expected Output: 3
  • Justification: The shortest path is (0, 0) -> (1, 1) -> (2, 2), totaling 3 steps.
  1. Example 3:
  • Input:
[1, 1, 1], 
 [0, 1, 1], 
 [0, 0, 0]]
  • Expected Output: -1
  • Justification: The top-left cell can't be visited, as its value is 1. So, it returns -1.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible