Shortest Path in Binary Matrix
Medium About 20 min Free, no account needed
Shortest 8-directional path across an open grid - DFS wanders, BFS knows.
The brief
In an n x n grid of 0 (open) and 1 (blocked), a clear path runs from
the top-left to the bottom-right cell moving in all 8 directions through
open cells. Return the path's length in cells, or -1 if none exists.
The obvious approach explores whole paths one by one and keeps the best; on an open grid the number of paths is exponential. The hidden test is an open 200x200 grid, so that approach is far too slow. You need a method that visits each cell once, O(cells).
Starter code
using System;
public class Solution
{
// TODO: return the length (in cells) of the shortest 8-directional clear path, or -1.
public int ShortestPathBinaryMatrix(int[][] grid)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Breadth-first search
- Explore a graph or grid level by level for shortest unweighted distances and spreading processes.
Related katas
- Minimum Forward Jumps Medium Free Cross a jump array with the fewest hops, including dead ends, without enumerating every reachable edge.
- Number of Islands Medium Free Count the connected patches of land in a grid.
- Rotting Oranges Medium Free How many minutes until the rot spreads everywhere?
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.