How do you solve Shortest Path in Binary Matrix on LeetCode?

Shortest Path in Binary Matrix (LeetCode #1091) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: BFS is optimal for finding the shortest path in unweighted grids.

What is the brute force solution for Shortest Path in Binary Matrix?

The brute force approach for Shortest Path in Binary Matrix is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves exploring all possible paths from the top-left to the bottom-right of the matrix. This means checking every possible route, which can be very inefficient, especially for larger matrices. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Shortest Path in Binary Matrix?

Shortest Path in Binary Matrix uses the following concepts: Array, Breadth-First Search, Matrix. The recommended patterns to study are: Breadth-First Search, Graph Traversal.

What are the interview tips for Shortest Path in Binary Matrix?

Always clarify the problem constraints and edge cases before diving into the solution. Explain your thought process while coding; it helps the interviewer understand your approach. Practice BFS and DFS problems to get comfortable with graph traversal techniques.

What are common mistakes when solving Shortest Path in Binary Matrix?

Not checking for boundary conditions before accessing grid elements. Forgetting to mark cells as visited, leading to infinite loops.

#1091

Shortest Path in Binary Matrix

Medium

ArrayBreadth-First SearchMatrixBreadth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal approach uses Breadth-First Search (BFS) because it explores all possible paths level by level, ensuring that the first time we reach the bottom-right cell, it is through the shortest path.

⚙️

Algorithm

3 steps

1Step 1: Initialize a queue and add the starting cell (0, 0) along with the initial path length of 1.
2Step 2: While the queue is not empty, dequeue the front cell and explore all 8 possible directions.
3Step 3: For each valid neighboring cell (that is 0 and within bounds), enqueue it with an incremented path length and mark it as visited.

solution.py23 lines

1# Full working Python code
2from collections import deque
3from typing import List
4
5def shortestPathBinaryMatrix(grid: List[List[int]]) -> int:
6    n = len(grid)
7    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
8        return -1
9
10    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
11    queue = deque([(0, 0, 1)])  # (x, y, path_length)
12    grid[0][0] = 1  # mark as visited
13
14    while queue:
15        x, y, path_length = queue.popleft()
16        if x == n - 1 and y == n - 1:
17            return path_length
18        for dx, dy in directions:
19            nx, ny = x + dx, y + dy
20            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
21                grid[nx][ny] = 1  # mark as visited
22                queue.append((nx, ny, path_length + 1))
23    return -1

ℹ

Complexity note: The time complexity is O(n²) because we may need to visit each cell in the grid once. The space complexity is O(n) due to the queue used for BFS, which can grow to the size of the grid in the worst case.

1BFS is optimal for finding the shortest path in unweighted grids.
2Marking cells as visited is crucial to avoid cycles and redundant checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.