Frontend School

Visible Buildings Count

DSA
medium

Visible Buildings Count

Medium
Matrix
Arrays

Overview

Browserstack provides a robust platform for testing web and mobile applications across a vast array of real devices and browsers. Imagine a scenario where Browserstack needs to optimize resource allocation for its global data centers. Each data center's server rack heights are represented in a 2D grid. To ensure optimal airflow and cooling, it's crucial to identify "visible" server racks, as these might require special considerations. This problem challenges you to calculate the total count of such visible server racks.

What you need to do / Task

You are given a 2D integer array grid where grid[r][c] represents the height of a server rack at row r and column c. Your task is to implement a function that determines the total number of "visible" server racks. A server rack at grid[r][c] is considered visible if there exists at least one cardinal direction (up, down, left, or right) such that all other server racks between (r, c) and the edge of the grid in that specific direction are strictly shorter than grid[r][c].

Specifically, for a cell (r, c):

  1. Visible from Left: All cells grid[r][j] where 0 <= j < c are strictly less than grid[r][c]. If c = 0, this condition is vacuously true.
  2. Visible from Right: All cells grid[r][j] where c < j < N are strictly less than grid[r][c]. If c = N-1, this condition is vacuously true.
  3. Visible from Up: All cells grid[i][c] where 0 <= i < r are strictly less than grid[r][c]. If r = 0, this condition is vacuously true.
  4. Visible from Down: All cells grid[i][c] where r < i < M are strictly less than grid[r][c]. If r = M-1, this condition is vacuously true.

If any of these conditions are met for grid[r][c], it is counted as a visible server rack.

Input & output

  • Input:
    • grid: A 2D integer array (number[][] in TypeScript, number[][] in JavaScript) representing the heights of server racks. grid will have M rows and N columns.
  • Output:
    • An integer, the total count of visible server racks.

Clarifications

  • Edge Cases: Racks on the very edge of the grid (first row, last row, first column, last column) are inherently visible from at least one direction (e.g., grid[0][c] is visible from Up by definition as there are no cells above it). These should be counted if they meet the criteria for any direction.
  • Empty Grid: The grid will not be empty. It will always have at least one row and one column.
  • Strictly Shorter: If grid[r][c] has the same height as a building in its path, it is NOT considered visible from that direction. It must be strictly taller than all intervening buildings.

Examples

1

Example 1

Input:

grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

Output:

15

Note:

Let's trace a few cells:

  • grid[0][0]=3: Visible from Left (no buildings), Visible from Up (no buildings). Counts.
  • grid[0][1]=0: Visible from Up (no buildings). Counts.
  • grid[1][1]=4: Visible from Left (2 < 4), Visible from Up (0 < 4), Visible from Down (2 < 4, 3 < 4). Counts.
  • grid[2][1]=2: Not visible from Left (9 >= 2), Not visible from Right (6 >= 2), Not visible from Up (4 >= 2), Not visible from Down (3 >= 2). Does NOT count. Total visible cells: 15.
2

Example 2

Input:

grid = [[5]]

Output:

1

Note:

The single building at (0,0) is visible from all four directions as there are no other buildings blocking it. It counts as 1 visible building.

3

Example 3

Input:

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

Output:

8

Note:

Only the corner and edge buildings are visible. For example, grid[0][0]=1 is visible from Up and Left. However, the center building grid[1][1]=1 is not visible from any direction because all its neighbors are of equal height, thus not strictly shorter. There are 9 total buildings, and only the center one is not visible, so 8 are visible.

Constraints

Constraints & assumptions

  • 1 <= M, N <= 500 (where M is the number of rows, N is the number of columns)
  • 0 <= grid[r][c] <= 10^9
  • The input grid will always be a valid 2D array.

What interviewers evaluate

  • Correctness: The solution accurately counts all visible server racks according to the problem definition.
  • Efficiency: The algorithm demonstrates optimal time and space complexity, preferably O(M*N) time.
  • Code Quality: The code is well-structured, readable, and handles edge cases gracefully.
  • Problem-Solving Approach: The candidate effectively breaks down the problem, explores different approaches, and articulates their chosen strategy.

Loading editor...