Find shortest distance in grid

Question

Given a 2D grid of cells where each cell represents a point in a coordinate system, find the shortest distance from a starting cell to a target cell while only being able to move up, down, left, or right. The grid may contain obstacles that cannot be traversed, and you should return the minimum number of steps required to reach the target cell, or -1 if it is not reachable.

Codemia · Accepted Answer

The problem can be categorized as a graph traversal problem, specifically suitable for the Breadth-First Search (BFS) algorithm. BFS is ideal here because it explores all possible paths layer by layer, ensuring that the first time it reaches the target cell, it does so with the minimum number of steps. This is critical in a grid where obstacles can block paths, and we need to find the shortest route efficiently.

1. **Initialization**: Start by defining the grid dimensions and identifying the starting and target cells. Initialize a queue to facilitate BFS and a set to track visited cells to prevent cycles.

2. **BFS Implementation**: Enqueue the starting cell along with the initial distance of 0. While the queue is not empty, dequeue an element which represents the current cell and its distance from the start. If this cell is the target, return the distance.

3. **Exploring Neighbors**: For each current cell, check its four possible neighbors (up, down, left, right). For each neighbor, check if it is within the grid bounds, not an obstacle, and not already visited. If valid, enqueue the neighbor with an incremented distance and mark it as visited.

4. **Termination**: If the queue empties without reaching the target, return -1, indicating that the target cell is unreachable.

```python
from collections import deque

def shortest_distance(grid, start, target):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start[0], start[1], 0)])  # (row, col, distance)
    visited = set()
    visited.add(start)

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up

while queue:
        row, col, dist = queue.popleft()
        if (row, col) == target:
            return dist

for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if (0 <= new_row < rows and 0 <= new_col < cols and
                grid[new_row][new_col] == 0 and
                (new_row, new_col) not in visited):
                visited.add((new_row, new_col))
                queue.append((new_row, new_col, dist + 1))

return -1  # Target is unreachable
```

The time complexity of this BFS solution is O(N * M), where N is the number of rows and M is the number of columns in the grid. In the worst case, we may have to explore every cell once. The space complexity is also O(N * M) due to the queue and the visited set storing each cell in the worst case.

1. **No Path**: If the starting cell or target cell is an obstacle (value 1), return -1 immediately. 
2. **Start Equals Target**: If the starting cell is the same as the target cell, return 0, as no movement is required. 
3. **All Obstacles**: If the grid is filled with obstacles, ensure the function returns -1. 
4. **Single Cell Grid**: A 1x1 grid where the single cell is either an obstacle or the start/target cell should be handled correctly.

Find shortest distance in grid

Apple

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Apple Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string