Number of Visible People in a Queue - Practice Coding Problems

Number of Visible People in a Queue - Problem

There are n people standing in a queue, numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the i^th person.

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the i^th person can see the j^th person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).

Return an array answer of length n where answer[i] is the number of people the i^th person can see to their right in the queue.

Input & Output

Example 1 — Basic Queue

$ Input: heights = [10,6,8,5,11,9]

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

💡 Note: Person 0 (height 10) can see persons 1, 2, and 4. Person 1 (height 6) can see person 2. Person 2 (height 8) can see persons 3 and 4. Person 3 (height 5) can see person 4. Person 4 (height 11) can see person 5. Person 5 sees no one.

Example 2 — Increasing Heights

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

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

💡 Note: Person 0 can see everyone to the right since they're all shorter until person 4. Each person can see the next taller person.

Example 3 — Decreasing Heights

$ Input: heights = [10,8,6,4,2]

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

💡 Note: In decreasing order, each person can see all people to their right since no one blocks the view.

Constraints

1 ≤ heights.length ≤ 10⁵
1 ≤ heights[i] ≤ 10⁹
All values in heights are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Queue

People standing in queue with different heights

Visibility Rules

Person can see another if no taller person blocks the view

Count Visible

For each person, count how many they can see to the right

Key Takeaway

🎯 Key Insight: Use a monotonic decreasing stack to efficiently track visible people by processing from right to left

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to use a monotonic decreasing stack to efficiently track which people are visible from each position. The optimal approach processes people from right to left, maintaining a stack of indices in decreasing height order. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack (Optimal)	O(n)	O(n)	Use a monotonic decreasing stack to efficiently track visible people
Brute Force - Check All Pairs	O(n³)	O(1)	For each person, check every person to their right and count visible ones

Monotonic Stack (Optimal) — Algorithm Steps

Process people from right to left
For each person, pop from stack while current height >= stack top height
Count popped elements plus one more if stack not empty
Push current person index to stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Right to Left

Process people from right to left

Pop Shorter

Pop stack elements shorter than current person

Count Visible

Count popped elements plus one more if stack not empty

Code -

solution.c — C

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

int* solution(int* heights, int n, int* returnSize) {
    *returnSize = n;
    int* result = (int*)calloc(n, sizeof(int));
    int* stack = (int*)malloc(n * sizeof(int));
    int top = -1;
    
    for (int i = n - 1; i >= 0; i--) {
        int count = 0;
        
        while (top >= 0 && heights[i] > heights[stack[top]]) {
            top--;
            count++;
        }
        
        if (top >= 0) {
            count++;
        }
        
        result[i] = count;
        stack[++top] = i;
    }
    
    free(stack);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int heights[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        heights[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(heights, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can contain up to n elements in worst case

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Monotonic Stack (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler