Skip to content
Katabench
Try free

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 performance bar

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

C#
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.

C# coding challenges →

What it practices

Breadth-first search
Explore a graph or grid level by level for shortest unweighted distances and spreading processes.

Related katas