BFS on array

Question

Implement a Breadth-First Search (BFS) algorithm to traverse a given 2D array, where each cell represents a node. The input will be a 2D array of integers, and your task is to return the order of nodes visited in a BFS traversal starting from a specified node. Ensure that you handle edge cases such as empty arrays and out-of-bounds indices.

Codemia · Accepted Answer

In this problem, we are required to implement a Breadth-First Search (BFS) traversal on a 2D array, treating each cell as a node. BFS is an appropriate choice here because it explores all neighbors at the present depth prior to moving on to nodes at the next depth level. This means we will explore all adjacent cells (up, down, left, right) before moving deeper into the array. BFS is particularly useful in grid-like structures, such as this 2D array, where we want to ensure that all nodes at the current level (distance from the starting node) are visited before moving to the next level.

We will perform the following steps to implement BFS on the given 2D array:
1. **Initialization**: Check if the input array is empty. If it is, return an empty list. If not, proceed to initialize a queue and a visited set.
2. **Queue Setup**: Start by adding the specified starting node (given by its row and column indices) to the queue and mark it as visited.
3. **BFS Loop**: While the queue is not empty, do the following:
   - Dequeue the front node (current position) and add it to the result list.
   - Check all four possible directions (up, down, left, right) for valid adjacent cells.
   - For each valid adjacent cell that hasn't been visited, mark it as visited and enqueue it.
4. **Return Result**: Once the queue is empty, return the result list containing the order of nodes visited.

Below is the Python implementation of the BFS algorithm for the given problem:
```python
from collections import deque

def bfs_traversal(array, start_row, start_col):
    if not array or not array[0]:  # Handle empty array case
        return []
    rows, cols = len(array), len(array[0])
    visited = set()
    queue = deque([(start_row, start_col)])
    visited.add((start_row, start_col))
    result = []

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

while queue:
        current_row, current_col = queue.popleft()
        result.append(array[current_row][current_col])

for dr, dc in directions:
            new_row, new_col = current_row + dr, current_col + dc
            if (0 <= new_row < rows and 0 <= new_col < cols and 
                (new_row, new_col) not in visited):
                visited.add((new_row, new_col))
                queue.append((new_row, new_col))

return result
```
This function takes a 2D array and the starting coordinates and returns the BFS traversal order.

The time complexity of this BFS implementation is O(N), where N is the number of nodes (or cells) in the 2D array. This is because we visit each cell at most once. The space complexity is also O(N) due to the queue used to hold the nodes and the set used for visited nodes. Both structures can grow up to the size of the grid in the worst-case scenario where all nodes are connected.

1. **Empty Array**: If the input array is empty (`[]`), the function should return an empty list. 
2. **Single Element Array**: If the array has only one element (e.g., `[[5]]`), the output should simply be `[5]`. 
3. **Out-of-bounds Start Index**: If the starting indices are out of bounds (e.g., `start_row = 0, start_col = 5` for a 4-column array), the function should handle this gracefully and potentially return an empty list, as there are no valid nodes to traverse from.

BFS on array

Snapchat

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

Snapchat 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