Skip to main content
Talentd

Shortest Path to Get Food - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBreadth-First SearchMatrix8 min readAsked at: DoorDash, Bloomberg
Practice this problem

Problem Statement

You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any food cell.

You are given an m x n character matrix, grid, of these different types of cells:

  • '*' is your location. There is exactly one '*' cell.
  • '#' is a food cell. There may be multiple food cells.
  • 'O' is free space, and you can travel through these cells.
  • 'X' is an obstacle, and you cannot travel through these cells.

You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle.

Return the length of the shortest path for you to reach any food cell. If there is no path for you to reach food, return -1.

 

Example 1:

Input: grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]
Output: 3
Explanation: It takes 3 steps to reach the food.

Example 2:

Input: grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]
Output: -1
Explanation: It is not possible to reach the food.

Example 3:

Input: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]]
Output: 6
Explanation: There can be multiple food cells. It only takes 6 steps to reach the bottom food.

Example 4:

Input: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["O","O","O","O","O","O","O","O"]]
Output: 5

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • grid[row][col] is '*', 'X', 'O', or '#'.
  • The grid contains exactly one '*'.

Approach Overview

Problem Overview: You are given a grid containing walls (X), empty cells (O), a starting position (*), and food cells (#). From the start, move up, down, left, or right. The goal is to reach any food cell using the minimum number of steps while avoiding walls.

Approach 1: DFS / Backtracking Search (O(m*n) time, O(m*n) space)

A naive idea is to explore every possible path from the starting cell using depth-first search. You recursively move in four directions and track visited cells to avoid cycles. Whenever a food cell is found, record the path length and keep the minimum. While DFS can eventually find the answer, it explores deep paths first and does not naturally guarantee the shortest route. In dense grids this leads to unnecessary exploration, making it inefficient for shortest-path problems on a matrix.

Approach 2: Breadth-First Search (BFS) (O(m*n) time, O(m*n) space)

The grid can be treated as an unweighted graph where each cell connects to up to four neighbors. Breadth-First Search processes nodes level by level, which naturally corresponds to distance in steps. Start from the * cell, push it into a queue, and expand neighbors while marking visited cells. Each BFS layer represents one step from the start. The first time a # cell is reached, the current level count is the shortest path length.

During traversal, skip cells outside bounds, walls (X), or already visited positions. Because each cell is processed at most once, the total work is proportional to the number of cells in the grid. This makes BFS the standard solution for shortest-path problems in an unweighted array-based grid.

Recommended for interviews: Interviewers expect the BFS solution. Shortest path in an unweighted grid is a classic signal for BFS with a queue and level tracking. Mentioning DFS as a brute-force exploration shows problem understanding, but implementing BFS demonstrates strong knowledge of graph traversal patterns commonly tested in interviews.

Solution

According to the problem, we need to start from *, find the nearest #, and return the shortest path length.

First, we traverse the entire two-dimensional array to find the position of *, which will be the starting point for BFS, and put it into the queue.

Then, we start BFS, traversing the elements in the queue. Each time we traverse an element, we add the elements in the four directions (up, down, left, and right) of it into the queue, until we encounter #, and return the current layer number.

The time complexity is O(m times n), and the space complexity is O(1). Here, m and n are the number of rows and columns of the two-dimensional array, respectively.

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS / BacktrackingO(m*n)O(m*n)Conceptual brute-force exploration; not ideal for shortest-path guarantees
Breadth-First Search (BFS)O(m*n)O(m*n)Best approach for shortest path in an unweighted grid
Multi-source BFS VariantO(m*n)O(m*n)Useful when starting from multiple positions or extending the problem

Video Solution

SHORTEST PATH TO GET FOOD | LEETCODE # 1730 | PYTHON BFS SOLUTION • Cracking FAANG • 3,810 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest Path to Get Food easy or hard?
Shortest Path to Get Food is typically rated Medium difficulty. The challenge is recognizing that the grid represents an unweighted graph and that BFS guarantees the minimum number of moves. Once the BFS pattern is known, the implementation is straightforward.
Shortest Path to Get Food Python/Java solution
Most implementations follow the same BFS template: locate the start cell, push it into a queue, iterate through four directions, and count levels until reaching food. The logic is identical across Python, Java, C++, Go, and JavaScript with only syntax differences.
How to solve Shortest Path to Get Food in O(m*n)?
Start BFS from the starting cell (*) and push it into a queue. Expand neighbors in four directions while skipping walls (X) and visited cells. Track the number of BFS levels, which represents distance in steps. When a food cell (#) is dequeued or discovered, return the current step count.
What is the best approach for Shortest Path to Get Food?
Breadth-First Search (BFS) is the optimal approach. The grid behaves like an unweighted graph where each move has equal cost. BFS explores cells level by level, so the first time a food cell (#) is reached guarantees the minimum number of steps. The overall complexity is O(m*n).
Is Shortest Path to Get Food asked at Google/Amazon/Meta?
Grid traversal and shortest path problems using BFS frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as shortest path in a matrix, rotten oranges, and walls-and-gates test the same BFS pattern used in this problem.
What data structure is used in Shortest Path to Get Food?
The core data structure is a queue used for Breadth-First Search traversal. A visited set or in-place grid marking prevents revisiting cells. The grid itself acts as an adjacency structure representing neighbors in four directions.
What is the time complexity of Shortest Path to Get Food?
The optimal BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is inserted into the queue at most once and processed once. Space complexity is also O(m*n) due to the visited set or queue storing grid positions.

Ready to solve this problem?

Practice Shortest Path to Get Food with our built-in code editor and test cases.

Practice on FleetCode
Previous

01 Matrix

Next

Amount of Time for Binary Tree to Be Infected