Frontend School

Matrix Visibility Score

DSA
medium

Matrix Visibility Score

Medium
Matrix
Dynamic Programming
Grid
Visibility

Overview

Netflix relies heavily on data analytics to understand user behavior and optimize content delivery. Imagine you're analyzing a grid-based representation of a content network or a data center layout, where some cells are open paths and others are critical infrastructure (obstacles). Understanding the "visibility" of various points in this grid can be crucial for network routing, security monitoring, or even optimizing sensor placement. This problem challenges you to quantify the visibility of each open point in such a grid.

What you need to do / Task

Your task is to implement a function that calculates the maximum visibility score achievable by any open cell in a given binary grid.

  1. Define an "open cell" as one with a value of 0. "Obstacles" have a value of 1.
  2. For any open cell (r, c), its "visibility score" is the count of cardinal directions (up, down, left, right) from which it has an unobstructed view to the grid's edge.
  3. An "unobstructed view" means there are no obstacles (1) present along the path from the cell (r, c) to the corresponding edge of the matrix in that specific direction.
  4. Return the highest visibility score found among all open cells in the grid. If the grid contains no open cells, return 0.

Input & output

Input:

  • grid: A 2D array (matrix) of integers, where grid[r][c] is either 0 (open cell) or 1 (obstacle).

Output:

  • An integer representing the maximum visibility score found among all open cells.

Clarifications

  • Empty grid: If the input grid is empty or grid[0] is empty, it contains no cells, so the maximum visibility score is 0.
  • All obstacles: If the grid contains only obstacles (1s), there are no open cells, so the maximum visibility score is 0.
  • Single cell grid: For a 1x1 grid [[0]], the cell (0,0) is visible from all 4 directions, so its score is 4. For [[1]], the score is 0.

Examples

1

Example 1

Input:

grid = [[0, 1, 0], [0, 0, 0], [0, 1, 0]]

Output:

4

Note:

Cells (1,0) and (1,2) are visible from all 4 cardinal directions, yielding a score of 4. For example, cell (1,0) is 0. It has an unobstructed path to the top edge (via (0,0)), bottom edge (via (2,0)), left edge, and right edge (via (1,1) and (1,2)). Cell (0,0) has a score of 3 because it's blocked to the right by (0,1).

2

Example 2

Input:

grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Output:

4

Note:

All cells are open (0). Since there are no obstacles, every cell has an unobstructed view to all four edges. Therefore, all cells have a visibility score of 4, and the maximum is 4.

3

Example 3

Input:

grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

Output:

0

Note:

Only cell (1,1) is open (0). However, all adjacent cells (0,1), (2,1), (1,0), and (1,2) are obstacles (1). This means cell (1,1) is blocked from all four cardinal directions, resulting in a visibility score of 0. Since it's the only open cell, the maximum score is 0.

Constraints

Constraints & assumptions

  • 1 <= grid.length <= 500 (number of rows, M)
  • 1 <= grid[0].length <= 500 (number of columns, N)
  • grid[r][c] is 0 or 1.
  • The grid will always be rectangular (i.e., grid[r].length is consistent for all r).

What interviewers evaluate

  • Correctness: Does the solution accurately calculate the maximum visibility score for all valid inputs, handling edge cases correctly?
  • Efficiency: Is the solution's time and space complexity optimal for the given constraints?
  • Clarity & Readability: Is the code well-structured, easy to understand, and appropriately commented?
  • Problem Decomposition: How well does the candidate break down the problem into manageable sub-problems (e.g., calculating visibility from each direction)?

Loading editor...