Find shortest distance in grid

Question

Given a 2D grid consisting of 0s and 1s, where 0 represents an empty cell and 1 represents an obstacle, write a function to find the shortest distance from a starting point to a target point, moving only through the empty cells. The function should return the length of the shortest path, or -1 if no path exists. The input will be the grid as a list of lists, and the starting and target points as tuples of coordinates.

Codemia · Accepted Answer

This problem can be classified under the Breadth-First Search (BFS) pattern, which is ideal for finding the shortest path in an unweighted grid. BFS explores all possible paths layer by layer, making it suitable for calculating the shortest distance in scenarios where each step has the same cost (moving from one cell to another). In this grid, we can only move to adjacent cells (up, down, left, right) which contain a 0 (empty cell). The BFS guarantees that once we reach the target point, it is through the shortest path because it explores all paths of a certain length before moving to the next length.

1. **Initialization**: Start by checking if the starting or target points are out of bounds or if they are obstacles (1). If so, return -1.  
2. **Setup BFS**: Initialize a queue to keep track of the cells to explore, starting with the initial position and a distance of 0. Also, keep track of visited cells to prevent cycles.  
3. **BFS Execution**: While the queue is not empty, pop the front cell and check if it is the target. If it is, return the current distance.  
4. **Explore Neighbors**: For the current cell, check all four possible directions (up, down, left, right). For each direction, if the new cell is within bounds, is an empty cell (0), and hasn’t been visited, mark it as visited, add it to the queue with an incremented distance.  
5. **End Condition**: If the queue is exhausted and the target has not been reached, return -1.

Here is the Python implementation of the described approach:  
```python  
def shortest_distance(grid, start, target):  
    from collections import deque  
    rows, cols = len(grid), len(grid[0])  
    start_x, start_y = start  
    target_x, target_y = target  
    if grid[start_x][start_y] == 1 or grid[target_x][target_y] == 1:  
        return -1  
    queue = deque([(start_x, start_y, 0)])  
    visited = set()  
    visited.add((start_x, start_y))  
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  
    while queue:  
        x, y, dist = queue.popleft()  
        if (x, y) == (target_x, target_y):  
            return dist  
        for dx, dy in directions:  
            new_x, new_y = x + dx, y + dy  
            if 0 <= new_x < rows and 0 <= new_y < cols and grid[new_x][new_y] == 0 and (new_x, new_y) not in visited:  
                visited.add((new_x, new_y))  
                queue.append((new_x, new_y, dist + 1))  
    return -1  
```

The time complexity of this BFS approach 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 might have to visit every cell exactly once. The space complexity is also O(N * M) due to the queue storing potentially all cells in the grid and the visited set. This approach is efficient given the constraints of traversing through a grid.

1. **Start or Target is an Obstacle**: If either the start or target coordinates are (1) in the grid, the function should return -1 immediately.  
2. **Single Cell Grid**: If the grid is a 1x1 matrix and it is 0, the function should return 0 if start and target are the same, otherwise -1.  
3. **No Possible Path**: When the grid is filled with obstacles (1s) except for the start and target, the function should return -1.  
4. **Out of Bounds Coordinates**: If the start or target coordinates are outside the grid dimensions, the function should return -1.

Find shortest distance in grid

Elastic

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

Elastic Software 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