Problem Description

You have an m x n grid where each cell contains a positive integer representing the height of a person standing at that position. The goal is to determine how many people each person in the grid can see.

A person at position (row1, col1) can see another person at position (row2, col2) if two conditions are met:

1. Direction constraint: The second person must be either:

   • In the same row to the right: row1 == row2 and col1 < col2, OR
   • In the same column below: row1 < row2 and col1 == col2

2. Height constraint: All people between these two positions must be shorter than both of them. This means if person A can see person B, everyone standing between them must have a height less than both heights[row1][col1] and heights[row2][col2].

You need to return an m x n matrix where each cell answer[i][j] contains the count of people that the person at position (i, j) can see.

For example, if a person is at position (1, 1), they can only look:

• To the right along row 1 (positions (1, 2), (1, 3), etc.)
• Downward along column 1 (positions (2, 1), (3, 1), etc.)

They cannot look diagonally, to the left, or upward. The number of visible people depends on the heights - taller people in between can block the view of shorter people behind them.

Intuition

The key insight is that a person can only see others who form a "visibility sequence" - where each visible person must be taller than all the people between them and the observer.

Think about it from one person's perspective: when looking in a direction (right or down), the people they can see must have increasing heights. Why? Because if person B is shorter than person A, and person A is between the observer and person B, then person A would block the view of person B.

This naturally leads us to think about monotonic sequences. When we look from a position, the visible people form a sequence where each subsequent visible person must be taller than the previous ones (otherwise they'd be blocked).

Now, how do we efficiently find these visible people? If we process people from far to near (reverse order), we can maintain a stack of "potentially visible" people. As we move closer to the observer:

• If we encounter someone taller than people in our stack, those shorter people become visible to our current person (they can see over them)
• We remove people from the stack who are shorter than the current person (they're now blocked)
• The remaining people in the stack who are taller than or equal to the current person might still be visible

This is the classic monotonic stack pattern! We maintain a stack that's monotonically decreasing (from bottom to top) as we traverse in reverse. Each person can see:

1. All people they can "see over" (those popped from the stack because they're shorter)
2. At most one person who is taller or equal (the first one remaining in the stack)

Since people can only look right or down, we apply this algorithm:

• Once for each row (to count people visible to the right)
• Once for each column (to count people visible below)
• Sum both counts for each position to get the total number of visible people

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution implements a monotonic stack approach by creating a helper function f(nums) that counts visible people in a single direction (either horizontal or vertical).

Helper Function f(nums):

The function processes a 1D array from right to left (far to near) and uses a monotonic stack to track visible people:

1. Initialize: Create an empty stack stk and a result array ans of zeros
2. Traverse in reverse (from index n-1 to 0):
   • Count shorter people: While the stack has elements and stk[-1] < nums[i], increment ans[i] and pop from stack. These are people the current person can see over.
   • Check for taller person: If the stack still has elements, increment ans[i] by 1. This represents the first person taller than or equal to the current person.
   • Remove equal heights: While the stack has elements and stk[-1] == nums[i], pop them. People of equal height block each other.
   • Add current person: Push nums[i] onto the stack for future comparisons.

Main Algorithm:

1. Process rows (looking right):

   • Apply f(row) to each row in the heights matrix
   • This gives us the count of people visible to the right for each position

2. Process columns (looking down):

   • For each column j, extract the column as [heights[i][j] for i in range(m)]
   • Apply f() to this column array to get visibility counts looking down
   • Add these counts to the corresponding positions in the answer matrix

3. Combine results: The final answer at each position is the sum of:

   • People visible to the right (from row processing)
   • People visible below (from column processing)

Stack Invariant: The stack maintains heights in non-increasing order from bottom to top. When we encounter a new person:

• Shorter people in the stack are visible and get removed
• The first taller/equal person (if exists) is also visible but remains
• Equal height people get removed to prevent double counting

Time Complexity: O(m × n) - each element is pushed and popped from the stack at most once for row processing and once for column processing.

Space Complexity: O(max(m, n)) - the stack can contain at most one row or column worth of elements at a time.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a 3×3 grid of heights:

heights = [[4, 2, 3],
           [1, 5, 2],
           [3, 1, 4]]

We need to count how many people each person can see (looking only right or down).

Step 1: Process Rows (Looking Right)

For each row, we apply the helper function f():

Row 0: [4, 2, 3]

• Process from right to left using a stack:
  • i=2 (height=3): stack=[], ans[2]=0, push 3 → stack=[3]
  • i=1 (height=2): stack=[3], 2<3 so ans[1]++, pop 3, stack=[], push 2 → stack=[2]
  • i=0 (height=4): stack=[2], 4>2 so ans[0]++, pop 2, stack=[], push 4 → stack=[4]
• Result for row 0: [1, 1, 0]

Row 1: [1, 5, 2]

• Process from right to left:
  • i=2 (height=2): stack=[], ans[2]=0, push 2 → stack=[2]
  • i=1 (height=5): stack=[2], 5>2 so ans[1]++, pop 2, stack=[], push 5 → stack=[5]
  • i=0 (height=1): stack=[5], 1<5 so stack stays, ans[0]++ for seeing 5 → ans[0]=1
• Result for row 1: [1, 1, 0]

Row 2: [3, 1, 4]

• Process from right to left:
  • i=2 (height=4): stack=[], ans[2]=0, push 4 → stack=[4]
  • i=1 (height=1): stack=[4], 1<4 so stack stays, ans[1]++ for seeing 4 → ans[1]=1
  • i=0 (height=3): stack=[4,1], 3>1 so ans[0]++, pop 1, stack=[4], 3<4 so ans[0]++ → ans[0]=2
• Result for row 2: [2, 1, 0]

After row processing:

answer = [[1, 1, 0],
          [1, 1, 0],
          [2, 1, 0]]

Step 2: Process Columns (Looking Down)

Column 0: [4, 1, 3]

• Process from bottom to top:
  • i=2 (height=3): stack=[], ans[2]=0, push 3 → stack=[3]
  • i=1 (height=1): stack=[3], 1<3 so stack stays, ans[1]++ for seeing 3 → ans[1]=1
  • i=0 (height=4): stack=[3,1], 4>1 so ans[0]++, pop 1, stack=[3], 4>3 so ans[0]++, pop 3 → ans[0]=2
• Add to column 0: [2, 1, 0]

Column 1: [2, 5, 1]

• Process from bottom to top:
  • i=2 (height=1): stack=[], ans[2]=0, push 1 → stack=[1]
  • i=1 (height=5): stack=[1], 5>1 so ans[1]++, pop 1, stack=[], push 5 → stack=[5]
  • i=0 (height=2): stack=[5], 2<5 so stack stays, ans[0]++ for seeing 5 → ans[0]=1
• Add to column 1: [1, 1, 0]

Column 2: [3, 2, 4]

• Process from bottom to top:
  • i=2 (height=4): stack=[], ans[2]=0, push 4 → stack=[4]
  • i=1 (height=2): stack=[4], 2<4 so stack stays, ans[1]++ for seeing 4 → ans[1]=1
  • i=0 (height=3): stack=[4,2], 3>2 so ans[0]++, pop 2, stack=[4], 3<4 so ans[0]++ → ans[0]=2
• Add to column 2: [2, 1, 0]

Step 3: Combine Results

Final answer (sum of row and column visibility):

answer = [[1+2, 1+1, 0+2],     [[3, 2, 2],
          [1+1, 1+1, 0+1],  =    [2, 2, 1],
          [2+0, 1+0, 0+0]]       [2, 1, 0]]

Each cell shows the total number of people that person can see by looking right and down.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n * (m + n))

The analysis breaks down as follows:

• The helper function f(nums) processes an array of length k in O(k) time, as each element is pushed and popped from the stack at most once.
• Processing all rows: We call f(row) for each of the m rows, where each row has n elements. This takes O(m * n) time total.
• Processing all columns: We call f([heights[i][j] for i in range(m)]) for each of the n columns, where each column has m elements. Creating the column array takes O(m) time, and processing it takes O(m) time. This is done n times, resulting in O(n * m) time.
• The final loop to add column results takes O(m * n) time.
• Total: O(m * n) + O(n * m) + O(m * n) = O(m * n * 2) = O(m * n)

However, considering the worst-case scenario where we need to traverse through both dimensions completely for each cell, and the stack operations within function f, the more precise complexity is O(m * n * (m + n)) when accounting for the maximum possible stack operations across all rows and columns.

Space Complexity: O(m + n)

The space analysis:

• The stack in function f can hold at most O(k) elements where k is the length of the input array.
• The ans array for function f uses O(k) space.
• When processing rows, the maximum stack size is O(n).
• When processing columns, we create a temporary array of size O(m) and the stack can hold at most O(m) elements.
• The output array ans is O(m * n) but this is not counted as auxiliary space since it's the required output.
• Maximum auxiliary space used at any point: O(max(m, n)) which simplifies to O(m + n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Equal Heights

The Pitfall: A common mistake is treating people of equal height inconsistently. Developers often forget that if person A (height H) can see person B (also height H), then person A cannot see anyone beyond person B, even if those people are taller. This is because person B blocks the view completely.

Incorrect Implementation:

# WRONG: Not removing equal heights from stack
while stack and stack[-1] < current_height:
    visible_count[i] += 1
    stack.pop()
if stack:
    visible_count[i] += 1
# Missing: removal of equal heights
stack.append(current_height)

Why It's Wrong: This keeps equal heights in the stack, which can lead to:

• Double counting when multiple people of the same height exist
• Incorrect visibility calculations for subsequent people

Correct Solution:

# Remove all shorter people
while stack and stack[-1] < current_height:
    visible_count[i] += 1
    stack.pop()

# Count the first taller/equal person
if stack:
    visible_count[i] += 1

# IMPORTANT: Remove all equal heights to prevent blocking issues
while stack and stack[-1] == current_height:
    stack.pop()

stack.append(current_height)

2. Processing Direction Confusion

The Pitfall: Processing the array in the wrong direction (left-to-right instead of right-to-left) when building the visibility count.

Incorrect Implementation:

# WRONG: Processing from left to right
for i in range(n):  # Should be range(n-1, -1, -1)
    current_height = heights_list[i]
    # ... rest of logic

Why It's Wrong: The stack approach requires processing from the far end (right/bottom) toward the near end (left/top) because:

• We need to know who is visible from each position looking forward
• The stack maintains people that haven't been "seen over" yet
• Processing backwards allows us to build this information incrementally

Correct Solution: Always process from right-to-left for horizontal visibility and bottom-to-top for vertical visibility:

for i in range(n - 1, -1, -1):  # Correct direction
    current_height = heights_list[i]
    # ... rest of logic

3. Misunderstanding the Visibility Rules

The Pitfall: Assuming that a person can see ALL people shorter than them in their line of sight, rather than understanding that the first person of equal or greater height blocks all visibility beyond them.

Example Scenario:

Heights: [4, 2, 1, 5, 3]
Person at index 0 (height 4) can see:
- Person at index 1 (height 2) ✓
- Person at index 2 (height 1) ✓
- Person at index 3 (height 5) ✓
- Person at index 4 (height 3) ✗ (blocked by person at index 3)

Correct Understanding: Once you encounter someone taller than or equal to the current person, they block all visibility beyond that point, regardless of the heights of people further away.