Lee's Algorithm

Problem

Given a 2D grid (maze) with obstacles, find the shortest path from a given source cell to a destination cell, moving only in four directions (up, down, left, right). Obstacles are represented by blocked cells. This is the classic Lee's algorithm problem.

Examples

Example 1

Input:
grid = [[0, 0, 0, 0],
		[1, 1, 0, 1],
		[0, 0, 0, 0],
		[0, 1, 1, 0]]
source = (0, 0), destination = (3, 3)
Output: 7
Explanation: The shortest path from (0,0) to (3,3) avoiding obstacles has length 7.

Solution

Method 1 – Lee's Algorithm (BFS for Grid Shortest Path)

Intuition

Lee's algorithm uses BFS to find the shortest path in a grid, expanding all possible moves level by level. BFS guarantees the shortest path in an unweighted grid.

Approach

1. Initialize a queue with the source cell and distance 0.
2. Mark the source as visited.
3. While the queue is not empty:
   • Pop the front cell.
   • For each of the 4 directions, if the next cell is within bounds, not blocked, and not visited, add it to the queue with distance +1.
   • If the destination is reached, return the distance.
4. If the destination is unreachable, return -1.

Code

C++

#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
	int shortestPath(vector<vector<int>>& grid, pair<int,int> src, pair<int,int> dst) {
		int n = grid.size(), m = grid[0].size();
		vector<vector<bool>> vis(n, vector<bool>(m, false));
		queue<pair<int,int>> q;
		q.push(src); vis[src.first][src.second] = true;
		int dist = 0;
		int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
		while (!q.empty()) {
			int sz = q.size();
			while (sz--) {
				auto [x, y] = q.front(); q.pop();
				if (x == dst.first && y == dst.second) return dist;
				for (auto& d : dirs) {
					int nx = x + d[0], ny = y + d[1];
					if (nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny] && grid[nx][ny] == 0) {
						vis[nx][ny] = true;
						q.push({nx, ny});
					}
				}
			}
			++dist;
		}
		return -1;
	}
};

Java

class Solution {
	public int shortestPath(int[][] grid, int[] src, int[] dst) {
		int n = grid.length, m = grid[0].length;
		boolean[][] vis = new boolean[n][m];
		Queue<int[]> q = new LinkedList<>();
		q.offer(src); vis[src[0]][src[1]] = true;
		int dist = 0;
		int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
		while (!q.isEmpty()) {
			int sz = q.size();
			for (int i = 0; i < sz; ++i) {
				int[] cell = q.poll();
				if (cell[0] == dst[0] && cell[1] == dst[1]) return dist;
				for (int[] d : dirs) {
					int nx = cell[0] + d[0], ny = cell[1] + d[1];
					if (nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny] && grid[nx][ny] == 0) {
						vis[nx][ny] = true;
						q.offer(new int[]{nx, ny});
					}
				}
			}
			dist++;
		}
		return -1;
	}
}

Python

class Solution:
	def shortest_path(self, grid: list[list[int]], src: tuple[int,int], dst: tuple[int,int]) -> int:
		from collections import deque
		n, m = len(grid), len(grid[0])
		vis = [[False]*m for _ in range(n)]
		q = deque([src])
		vis[src[0]][src[1]] = True
		dist = 0
		dirs = [(0,1),(1,0),(0,-1),(-1,0)]
		while q:
			for _ in range(len(q)):
				x, y = q.popleft()
				if (x, y) == dst:
					return dist
				for dx, dy in dirs:
					nx, ny = x+dx, y+dy
					if 0<=nx<n and 0<=ny<m and not vis[nx][ny] and grid[nx][ny]==0:
						vis[nx][ny] = True
						q.append((nx, ny))
			dist += 1
		return -1

Complexity

• ⏰ Time complexity: O(N*M), where N and M are the grid dimensions. Each cell is visited at most once.
• 🧺 Space complexity: O(N*M), for the visited array and queue.