Katkat
Back

Solve Two Grid Search Problems

PinterestSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate 2D grids and apply graph traversal algorithms to identify connected components and calculate propagation distances.

Problem Description

You are given an m x n grid representing a map of an office floor. The grid consists of two types of cells: 0 (empty space) and 1 (a desk).

Two desks are connected if they are adjacent horizontally or vertically. A 'cluster' is defined as a group of connected desks.

Task 1: Count Clusters

Write a function count_clusters(grid) that returns the total number of distinct clusters of desks in the grid.

Task 2: Calculate Propagation

Suppose a network signal starts from all desk clusters simultaneously. Write a function signal_propagation(grid) that returns a grid of the same dimensions where each cell contains the Manhattan distance to the nearest desk. If a cell contains a desk, its value should be 0.

Constraints

  • m, n are between 1 and 200.
  • grid[i][j] is either 0 or 1.

Examples

Example 1: Counting Clusters

Input: grid = [[1, 1, 0], [0, 0, 1], [0, 0, 1]]
Output: 2
# Explanation: One cluster of two desks (top-left) and one cluster of two desks (right).

Example 2: Signal Propagation

Input: grid = [[1, 0], [0, 0]]
Output: [[0, 1], [1, 2]]
# Explanation: The desk at (0,0) is distance 0. (0,1) and (1,0) are distance 1 away.

Hints

Hint 1

For Task 1, use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse each unvisited desk and mark all reachable desks as visited.

Hint 2

For Task 2, consider treating all desks as starting nodes for a Multi-Source BFS, where you initialize the queue with all coordinates containing a '1'.

Hint 3

Ensure you handle the 'visited' state effectively for Task 2 by initializing empty cells with infinity and updating them as you propagate outward from the desks.

Follow-up questions

  • How would your approach change if you were only allowed to move diagonally as well?
  • What is the time and space complexity of your propagation solution in terms of total grid cells N?
  • If the grid was extremely sparse (mostly 0s), how could you optimize the memory usage for the propagation task?