Number of People That Can Be Seen in a Grid

Medium

Asked by:

23 views

Topics:

ArraysStacks

You are given a 0-indexed n x n integer matrix grid representing a city. The value of grid[i][j] represents the height of the building at position (i, j).

A person standing at position (row, col) in the city can see the building at position (r, c) if:

r == row or c == col
All the buildings located between (row, col) and (r, c) have strictly smaller heights than both grid[row][col] and grid[r][c].

You want to build the tallest building in the city, so find the best position to place this building such that the number of buildings you can see from it is maximized. The height of the building can be any non-negative integer.

Return an array [row, col] representing the optimal position to place the building. If there are multiple optimal positions, return the lexicographically smallest one.

Example 1:

Input: grid = [[5,4,5],[6,5,6],[5,4,5]]
Output: [1,1]
Explanation: Placing the tallest building at position (1, 1), height 5, the number of buildings you can see is 12, which is the maximum. 
From (1, 1) you can see:
- (1, 0) since grid[1][0] < grid[1][1] and grid[1][0] <= 5.
- (1, 2) since grid[1][2] < grid[1][1] and grid[1][2] <= 5.
- (0, 1) since grid[0][1] < grid[1][1] and grid[0][1] <= 5.
- (2, 1) since grid[2][1] < grid[1][1] and grid[2][1] <= 5.

Example 2:

Input: grid = [[3,1],[2,7]]
Output: [1,1]
Explanation: Placing the tallest building at position (1, 1), height 7, the number of buildings you can see is 4, which is the maximum. 
From (1, 1) you can see:
- (0, 1) since grid[0][1] < grid[1][1] and grid[0][1] <= 7.
- (1, 0) since grid[1][0] < grid[1][1] and grid[1][0] <= 7.

Example 3:

Input: grid = [[1,0,5],[4,1,3],[1,0,3]]
Output: [0,0]
Explanation: Placing the tallest building at position (0, 0), height 5, the number of buildings you can see is 5, which is the maximum. 
From (0, 0) you can see:
- (0, 2) since grid[0][2] < grid[0][0] and grid[0][2] <= 5.
- (1, 0) since grid[1][0] < grid[0][0] and grid[1][0] <= 5.

Constraints:

1 <= n == grid.length == grid[i].length <= 100
0 <= grid[i][j] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what is the maximum size of each dimension?
What are the possible values for the height of each person in the grid? Can heights be negative or zero?
If a person's view is blocked entirely in all directions, should they still be counted as seeing 0 people, or is there a specific return value for this case?
Are we looking for the *total* number of people that can be seen by *all* people in the grid, or the number of people that can be seen by each person individually?
If there are multiple people with the same height blocking the view, do we stop counting at the first such person, or do we consider all people with the same height until a taller person is encountered?

Brute Force Solution

Approach

We want to figure out how many people each person in a grid can see. The brute force way to do this is to check, for every single person, whether they can see every other person. This involves manually checking the line of sight between each pair of people.

Here's how the algorithm would work step-by-step:

For each person in the grid, consider them as the starting point.
Now, for that person, go through every other person in the grid one by one.
For each of those other people, imagine a straight line connecting the starting person to that other person.
Check every grid cell along that line to see if anyone is blocking the view.
If the line of sight is clear (no one blocking), then the starting person can see that other person. Keep track of this.
If the line of sight is blocked, then the starting person cannot see that other person.
Once you've checked all the other people in the grid from the starting person's perspective, count how many people that starting person can see.
Repeat this entire process for every person in the grid.

Code Implementation

def number_of_people_that_can_be_seen_in_a_grid(grid):
    grid_height = len(grid)
    grid_width = len(grid[0]) if grid_height > 0 else 0

    def is_blocking(row_index, column_index, starting_row, starting_column, target_row, target_column):
        if grid[row_index][column_index] == 1 and (row_index != starting_row or column_index != starting_column) and (row_index != target_row or column_index != target_column):
            return True
        return False

    def can_see(starting_row, starting_column, target_row, target_column):
        row_difference = target_row - starting_row
        column_difference = target_column - starting_column
        maximum_difference = max(abs(row_difference), abs(column_difference))

        for step in range(1, maximum_difference + 1):
            current_row = starting_row + round(row_difference * step / maximum_difference)
            current_column = starting_column + round(column_difference * step / maximum_difference)

            if is_blocking(current_row, current_column, starting_row, starting_column, target_row, target_column):
                return False

        return True

    people_seen_counts = []

    for starting_row in range(grid_height):
        for starting_column in range(grid_width):
            if grid[starting_row][starting_column] == 1:
                people_seen_count = 0

                for target_row in range(grid_height):
                    for target_column in range(grid_width):
                        if grid[target_row][target_column] == 1 and (starting_row != target_row or starting_column != target_column):
                            # Only check other people
                            if can_see(starting_row, starting_column, target_row, target_column):
                                people_seen_count += 1

                people_seen_counts.append(people_seen_count)

    return people_seen_counts

def solve():
    grid1 = [
        [1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 1, 0, 0],
        [0, 0, 0, 1, 0],
        [0, 0, 0, 0, 1]
    ]
    result1 = number_of_people_that_can_be_seen_in_a_grid(grid1)
    print(f'{result1=}')

    grid2 = [
        [1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 1, 0],
        [0, 0, 0, 0, 1]
    ]
    result2 = number_of_people_that_can_be_seen_in_a_grid(grid2)
    print(f'{result2=}')

    grid3 = [
        [1, 0, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 0, 1]
    ]
    result3 = number_of_people_that_can_be_seen_in_a_grid(grid3)
    print(f'{result3=}')

if __name__ == "__main__":
    solve()

Big(O) Analysis

Time Complexity

O(n^3) – We iterate through each person in the grid, which takes O(n) time where n is the number of people. For each person, we iterate through every other person to check if they are visible, which is another O(n) operation. For each pair of people, we need to check the line of sight, which, in the worst case, could involve traversing a line with length proportional to the size of the grid which is O(n). Thus the time complexity will be n * n * n = O(n^3).

Space Complexity

O(1) – The algorithm iterates through each person and checks visibility to every other person, but it does not appear to store a list of visible people. It only keeps track of a count for each person, and the number of people seen for a particular person. These counts are likely updated in place or using a constant number of extra variables. Therefore, the space used by the algorithm remains constant regardless of the number of people in the grid.

Optimal Solution

Approach

To efficiently count visible people in a grid, we'll cleverly use the concept of increasing height. We'll check each direction from every person and count others who are visible, meaning they are taller than everyone in between.

Here's how the algorithm would work step-by-step:

Imagine you're standing at each person's spot in the grid, one by one.
From that spot, look in each of the four directions: up, down, left, and right.
As you look, keep track of the tallest height you've seen so far.
If the next person you see is taller than everyone you've seen so far in that direction, then you can see them. Count that person as visible.
If the next person you see is shorter or the same height as someone you've already seen that's taller, you can't see them because they're blocked.
Repeat this process for each direction from each person in the grid. At the end, add up all the visible people you counted.

Code Implementation

def number_of_people_that_can_be_seen(grid):
    rows = len(grid)
    cols = len(grid[0])
    visible_people_count = 0

    for row_index in range(rows):
        for col_index in range(cols):
            for direction_x, direction_y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                current_x = row_index + direction_x
                current_y = col_index + direction_y
                max_height_seen = 0
                person_seen = False

                while 0 <= current_x < rows and 0 <= current_y < cols:
                    # We need to track the tallest person.
                    if grid[current_x][current_y] > max_height_seen:
                        max_height_seen = grid[current_x][current_y]
                        person_seen = True
                        visible_people_count += 1
                        break

                    # Stop if blocked by taller or equal person.
                    elif grid[current_x][current_y] <= max_height_seen:
                        break

                    current_x += direction_x
                    current_y += direction_y

    return visible_people_count

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through each cell in the n x n grid, resulting in n^2 operations. From each cell, it checks in four directions (up, down, left, right). In the worst case, each direction requires traversing up to n cells to determine visibility, as we must compare the height of each person along the line of sight. Therefore, for each of the n^2 cells, we potentially perform O(n) operations (checking in each of the four directions), leading to a total time complexity of O(n^2 * n) = O(n^3).

Space Complexity

O(1) – The algorithm iterates through the grid and for each cell, it looks in four directions. While it keeps track of the tallest height seen so far in each direction, this tallest height is stored in a constant number of variables (one for each direction during the inner loop execution). No additional data structures that scale with the input grid size are allocated. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty grid (0 rows or 0 columns)	Return 0 as no people can be seen in an empty grid.
Grid with only one row or one column	Handle single row or column as a special case; all elements can see only in one direction.
Grid with all identical heights	The number of visible people will be 0 in most directions, as all heights are blocked.
Grid with very large heights that could cause integer overflow during calculations	Use a data type that supports larger numbers, like long, to prevent overflow.
Maximum grid dimensions to test scalability of the solution	Analyze time and space complexity to ensure it remains within acceptable limits for maximum input size.
Grid with negative heights if the problem statement disallows	Validate input and throw an error or handle as undefined if negative heights are not allowed.
Grid with heights close to integer limits	Ensure height comparisons don't result in integer overflows during comparisons.
Heights are floating point numbers and might introduce precision errors.	Consider using a tolerance for floating point comparisons to avoid precision issues

Empty grid (0 rows or 0 columns)

How to Handle:

Return 0 as no people can be seen in an empty grid.

Grid with only one row or one column

How to Handle:

Handle single row or column as a special case; all elements can see only in one direction.

Grid with all identical heights

How to Handle:

The number of visible people will be 0 in most directions, as all heights are blocked.

Grid with very large heights that could cause integer overflow during calculations

How to Handle:

Use a data type that supports larger numbers, like long, to prevent overflow.

Maximum grid dimensions to test scalability of the solution

How to Handle:

Analyze time and space complexity to ensure it remains within acceptable limits for maximum input size.

Grid with negative heights if the problem statement disallows

How to Handle:

Validate input and throw an error or handle as undefined if negative heights are not allowed.

Grid with heights close to integer limits

How to Handle:

Ensure height comparisons don't result in integer overflows during comparisons.

Heights are floating point numbers and might introduce precision errors.

How to Handle:

Consider using a tolerance for floating point comparisons to avoid precision issues