Number of People That Can Be Seen in a Grid

Number of People That Can Be Seen in a Grid - Problem

You are given an m x n 0-indexed 2D array of positive integers heights where heights[i][j] is the height of the person standing at position (i, j).

A person standing at position (row1, col1) can see a person standing at position (row2, col2) if:

The person at (row2, col2) is to the right or below the person at (row1, col1). More formally, this means that either row1 == row2 && col1 < col2 or row1 < row2 && col1 == col2.
Everyone in between them is shorter than both of them.

Return an m x n 2D array of integers answer where answer[i][j] is the number of people that the person at position (i, j) can see.

Input & Output

Example 1 — Basic Grid

$ Input: heights = [[3,1,4,2,5],[1,2,3,4,5]]

› Output: [[2,1,2,1,0],[0,0,0,0,0]]

💡 Note: Person at (0,0) with height 3 can see (0,1) height 1 and (1,0) height 1. Person at (0,1) with height 1 can see (0,2) height 4. Person at (0,2) with height 4 can see (0,3) height 2 and (1,2) height 3. Person at (0,3) with height 2 can see (0,4) height 5. Last column and bottom row see 0 people.

Example 2 — Single Row

$ Input: heights = [[1,2,3]]

› Output: [[2,1,0]]

💡 Note: Person at (0,0) height 1 can see both (0,1) height 2 and (0,2) height 3. Person at (0,1) height 2 can see (0,2) height 3. Person at (0,2) sees no one.

Example 3 — Blocking Heights

$ Input: heights = [[5,1,2,3,4],[1,1,1,1,1]]

› Output: [[4,3,2,1,0],[0,0,0,0,0]]

💡 Note: Person at (0,0) height 5 can see everyone to the right since they're all shorter. Bottom row can't see anyone since they're at the last row and no one is to their right in same row.

Constraints

1 ≤ m, n ≤ 50
1 ≤ heights[i][j] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D array of heights representing people

Visibility Rules

Can only see right in same row or down in same column

Count Visible

Count people visible from each position

Key Takeaway

🎯 Key Insight: Use monotonic decreasing stack to efficiently track which people remain visible after processing each position

Asked in

A Amazon 15 G Google 12 M Microsoft 8

The key insight is to use a monotonic decreasing stack to efficiently track visible people. Process each row from right to left and each column from bottom to top. The stack maintains people who remain visible, and we count those that get popped (blocked by current person). Best approach is Monotonic Stack with Time: O(mn), Space: O(max(m,n))

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(m²n²)	O(1)	For each person, check all people to the right and below directly
Monotonic Stack Optimization	O(mn)	O(max(m,n))	Use monotonic decreasing stack to track visible people efficiently

Brute Force — Algorithm Steps

For each position (i,j), look right in row i and down in column j
For each potential visible person, verify no one in between is taller
Count all visible people from current position

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Position

Pick current person at (i,j)

Check Right & Down

Look at each position to right and below

Verify Visibility

Check if everyone in between is shorter

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int** solution(int** heights, int m, int n) {
    int** answer = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        answer[i] = (int*)calloc(n, sizeof(int));
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int count = 0;
            
            // Check right in same row
            for (int k = j + 1; k < n; k++) {
                int canSee = 1;
                // Check if anyone in between is taller
                for (int mid = j + 1; mid < k; mid++) {
                    if (heights[i][mid] >= max(heights[i][j], heights[i][k])) {
                        canSee = 0;
                        break;
                    }
                }
                if (canSee) count++;
            }
            
            // Check down in same column
            for (int k = i + 1; k < m; k++) {
                int canSee = 1;
                // Check if anyone in between is taller
                for (int mid = i + 1; mid < k; mid++) {
                    if (heights[mid][j] >= max(heights[i][j], heights[k][j])) {
                        canSee = 0;
                        break;
                    }
                }
                if (canSee) count++;
            }
            
            answer[i][j] = count;
        }
    }
    
    return answer;
}

int main() {
    // Simple parsing for small test cases
    int heights[10][10] = {{3,1,4,2,5},{1,2,3,4,5}};
    int m = 2, n = 5;
    
    int** result = solution((int**)heights, m, n);
    
    printf("[");
    for (int i = 0; i < m; i++) {
        printf("[");
        for (int j = 0; j < n; j++) {
            printf("%d", result[i][j]);
            if (j < n - 1) printf(",");
        }
        printf("]");
        if (i < m - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

For each of m×n positions, we check up to m+n other positions, and for each check we verify up to m+n intermediate positions

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for counters and loops

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

467 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler