Frontend School

Max Visible Network Cell

DSA
hard

Max Visible Network Cell

Hard
Matrix
Grid
Traversal
Line of Sight

Overview

Browserstack's core business involves testing websites and applications across a vast array of real devices and browsers. Imagine a new feature where we want to intelligently place "monitoring probes" (signal emitters) across a virtual network grid to maximize coverage for "data collection points" (empty cells). This problem simulates a simplified version of determining optimal placement by identifying the most "visible" data collection point, given existing signal emitters and network obstacles. Understanding line-of-sight propagation in a grid is crucial for network planning and resource optimization.

What you need to do / Task

You are given a 2D grid representing a virtual network. Each cell can be:

  • . (empty): A potential data collection point.
  • S (signal emitter): A source broadcasting a signal.
  • # (obstacle): A block that prevents signal propagation.

Your task is to implement a function findMaxVisibleCell that identifies an empty cell ('.') in the grid that receives signals from the maximum number of distinct signal emitters. A signal from an emitter travels in all 8 cardinal and diagonal directions (horizontal, vertical, and both diagonals) until it hits an obstacle (#) or the boundary of the grid. Any empty cell . on a direct line of sight from an emitter, without an obstacle in between, receives a signal from that emitter.

If there are multiple empty cells that receive the maximum number of signals, any one of them is a valid answer. If no empty cells exist, or no empty cell receives any signal, return [-1, -1].

Input & output

  • Input: grid: string[][]
    • grid: A 2D array of strings, where each string is a single character (., S, or #). grid[r][c] represents the character at row r and column c.
  • Output: number[]
    • An array [row, col] representing the 0-indexed coordinates of an empty cell . that receives the maximum number of distinct signals.
    • If no such cell exists, or no empty cell receives any signal, return [-1, -1].

Clarifications

  • The grid will always be non-empty.
  • The grid can contain zero emitters or zero empty cells.
  • An emitter itself does not receive signals that count towards its own 'visibility'. We only care about empty cells.
  • The problem asks for the number of distinct emitters whose signals reach an empty cell. If an empty cell is reached by signals from two different emitters, it counts as 2. If it's reached by a single emitter, it counts as 1. Signals from other emitters (S) or empty cells (.) do not block propagation; only obstacles (#) do.

Examples

1

Example 1

Input:

grid = [["S",".","."], [".","#","."], [".",".","S"]]

Output:

[0,2]

Note:

Cell (0,2) receives signals from S at (0,0) and S at (2,2). Cell (2,0) also receives from S at (0,0) and S at (2,2). Both (0,2) and (2,0) achieve the maximum count of 2. Any valid cell is acceptable.

2

Example 2

Input:

grid = [[".",".","."], [".",".","."], [".",".","."]]

Output:

[-1,-1]

Note:

There are no signal emitters in the grid, so no empty cell receives any signal. The maximum count is 0, thus we return [-1,-1].

3

Example 3

Input:

grid = [["#","#"],["#","S"]]

Output:

[-1,-1]

Note:

There are no empty cells ('.') in the grid to receive signals. Thus, we return [-1,-1].

4

Example 4

Input:

grid = [["S", ".", "#", ".", "S"], [".", ".", ".", ".", "."], ["#", ".", "S", ".", "#"], [".", ".", ".", ".", "."], ["S", ".", "#", ".", "S"]]

Output:

[1,1]

Note:

Many cells receive signals. For example, cell (1,1) receives signals from S at (0,0), S at (2,2), and S at (4,0). Cell (1,3) receives signals from S at (0,4), S at (2,2), and S at (4,4). Both achieve 3 distinct signals. Other cells might also achieve this maximum. For this example, [1,1] is a valid output.

Constraints

Constraints & assumptions

  • 1 <= grid.length, grid[0].length <= 500
  • Each grid[r][c] will be one of '.', 'S', '#'
  • At least one cell will exist in the grid.

Out of scope

  • Handling invalid input characters or malformed grids.
  • Considering different signal strengths or attenuation.
  • Optimizing for scenarios where emitters can move or obstacles appear/disappear dynamically.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies the cell with maximum distinct signals, handling all edge cases (e.g., no empty cells, no emitters, obstacles).
  • Time and Space Complexity: The solution demonstrates an understanding of optimal time and space complexity for the given constraints, aiming for O(N*M * max(N,M)) time complexity.
  • Code Structure and Readability: The code is well-organized, clean, and easy to understand, using appropriate data structures and helper functions.
  • Edge Case Handling: Robustness in handling scenarios like empty grids, grids with no emitters, or grids with no empty cells.

Loading editor...