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

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

✓ Brute Force

⏱️ Time: O(m²n²) Space: O(1)

For each position, iterate through all positions to the right in the same row and all positions below in the same column. For each potential target, check if all people in between are shorter than both the current person and the target.

Monotonic Stack Optimization

⏱️ Time: O(mn) Space: O(max(m,n))

Process each row from right to left and each column from bottom to top using a monotonic decreasing stack. The stack maintains people who are still visible, and we can count visible people as we process each position.

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>
#include <ctype.h>

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

void parse2DArray(const char* input, int heights[10][10], int* m, int* n) {
    *m = 0;
    *n = 0;
    const char* p = input;
    
    // Skip to first '['
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p) {
        // Find start of sub-array
        while (*p && *p != '[') p++;
        if (*p != '[') break;
        
        // Parse sub-array
        int temp_arr[10];
        int temp_size;
        parseArray(p, temp_arr, &temp_size);
        
        if (*m == 0) *n = temp_size;
        for (int j = 0; j < temp_size; j++) {
            heights[*m][j] = temp_arr[j];
        }
        (*m)++;
        
        // Move past this sub-array
        while (*p && *p != ']') p++;
        if (*p == ']') p++;
        while (*p && *p != '[' && *p != ']') p++;
        if (*p == ']') break;
    }
}

int** solution(int heights[10][10], 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 can_see = 1;
                // Check if anyone in between blocks the view
                for (int mid = j + 1; mid < k; mid++) {
                    if (heights[i][mid] >= heights[i][j] || heights[i][mid] >= heights[i][k]) {
                        can_see = 0;
                        break;
                    }
                }
                if (can_see) {
                    count++;
                }
            }
            
            // Check down in same column  
            for (int k = i + 1; k < m; k++) {
                int can_see = 1;
                // Check if anyone in between blocks the view
                for (int mid = i + 1; mid < k; mid++) {
                    if (heights[mid][j] >= heights[i][j] || heights[mid][j] >= heights[k][j]) {
                        can_see = 0;
                        break;
                    }
                }
                if (can_see) {
                    count++;
                }
            }
            
            answer[i][j] = count;
        }
    }
    
    return answer;
}

int main() {
    char input[1000];
    if (fgets(input, sizeof(input), stdin) != NULL) {
        int heights[10][10];
        int m, n;
        
        parse2DArray(input, heights, &m, &n);
        
        int** result = solution(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(", ");
            free(result[i]);
        }
        printf("]\n");
        
        free(result);
    }
    
    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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler