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

158. Shortest Path in Binary Matrix

MediumDay 46 of 60Graphs

Given an n x n grid of 0s and 1s, return the length of the shortest clear path from the top-left cell to the bottom-right cell, or -1 if none exists. A clear path visits only cells with value 0, and consecutive cells must touch by an edge or a corner (8 directions). The length is the number of cells visited, including both ends.

Example 1
Input: grid = [[0,1],[1,0]]
Output: 2
Move diagonally from (0,0) to (1,1).
Example 2
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Example 3
Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
The start cell is blocked.
Constraints
  • n == grid.length == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] is 0 or 1
Hints
Frequently asked at: Amazon, Meta, Google
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