LeetCode Solutions Blog

Number of People That Can Be Seen in a Grid

Number: 2425

Difficulty: Medium

Paid? Yes

Companies: Uber

Problem Description

Given an m x n grid where each cell represents the positive integer height of a person, determine for every person (i, j) the number of people they can see. A person can only see to the right (in the same row) or downward (in the same column) under the condition that every person between them is strictly shorter than both the observer and the target.

Key Insights

The visibility is only checked in one of two directions: right in the same row and downward in the same column.
In each direction, a person can see another if every person in between is shorter than both.
The problem naturally lends itself to using a monotonic stack to efficiently track heights and count visible persons.
Separate processing for rows and columns followed by summing counts will give the final answer for each cell.

Space and Time Complexity

Time Complexity: O(m * n) — each cell is processed in both row-wise and column-wise passes. Space Complexity: O(max(m, n)) — extra space for the monotonic stack in the worst-case scenario for either a row or a column.

Solution

The solution leverages a monotonic stack approach to count visible persons in each direction independently. For the row-wise pass, for each row we iterate from left to right and maintain a stack that helps us count how many persons can be seen from the current position. If the current height is larger than the ones in the stack, those persons are popped because the current person blocks them. We then add one more if the stack isn’t empty (meaning the next taller/equal person is still visible). The same logic is applied column-wise by iterating through each column from top to bottom. Finally, we sum the counts from both passes to construct the final answer grid.

Code Solutions

def visibleInRow(heights_row):
    # This function returns a list of counts for each person in a row.
    n = len(heights_row)
    visible = [0] * n
    stack = []
    for j in range(n):
        # Count how many persons from the left can be seen by popping shorter ones
        while stack and heights_row[stack[-1]] < heights_row[j]:
            idx = stack.pop()
            visible[idx] += 1  # the current person is visible to the popped person
        if stack:
            # The top of the stack is taller or equal, so current person is visible
            visible[stack[-1]] += 1
        stack.append(j)
    return visible

def visibleInColumn(heights_col):
    # This function returns a list of counts for each person in a column.
    m = len(heights_col)
    visible = [0] * m
    stack = []
    for i in range(m):
        while stack and heights_col[stack[-1]] < heights_col[i]:
            idx = stack.pop()
            visible[idx] += 1
        if stack:
            visible[stack[-1]] += 1
        stack.append(i)
    return visible

def numberOfPeople(heights):
    if not heights: 
        return []
    m = len(heights)
    n = len(heights[0])
    # Create answer grid initialized to 0
    answer = [[0] * n for _ in range(m)]
    
    # Process rows: for each row, compute visible counts to the right.
    for i in range(m):
        row_visibility = visibleInRow(heights[i])
        for j in range(n):
            answer[i][j] += row_visibility[j]
    
    # Process columns: for each column, compute visible counts downward.
    for j in range(n):
        col = [heights[i][j] for i in range(m)]
        col_visibility = visibleInColumn(col)
        for i in range(m):
            answer[i][j] += col_visibility[i]
    
    return answer

# Example usage:
heights1 = [[3,1,4,2,5]]
print(numberOfPeople(heights1))  # Expected output: [[2,1,2,1,0]]

heights2 = [[5,1],[3,1],[4,1]]
print(numberOfPeople(heights2))  # Expected output: [[3,1],[2,1],[1,0]]