1944. Number of Visible People in a Queue - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given an array of positive integers, where each integer represents the height of a person standing in a queue (from left to right). For every person, determine how many people they can see to their right. One person can see another if the other person is not blocked by a taller (or equal height) person in between. More formally, for person i:

They can see person j (with j > i) if every person between i and j is shorter than person j.
Note that if a person of equal or greater height is encountered, that person is visible but blocks any further view behind them.

Your goal is to return an array answer where answer[i] is the number of people that person i can see.

Hints

Here are some clear, step-by-step hints to help you solve the "Number of Visible People in a Queue" problem:

Understand the Visibility Rule:
- For a person at index i, they can see someone at index j (where j > i) if no one in between is taller than or equal to the person at j.
- Once a person of greater or equal height is encountered, that person is visible, but further people beyond are blocked.
Use a Monotonic Stack:
- Consider maintaining a stack that stores indices of people in decreasing order of heights.
- This way, when you add a new person, you can easily find out which previous people are blocked by this new height.
Processing the Queue:
- Iterate through the array from left to right.
- For each person, while the stack is not empty and the current person’s height is greater than or equal to the height at the top of the stack:
  - Pop the index from the stack, and for each popped index, increment their visible count (since they can see the current person).
- After the while loop, if the stack is still not empty, then the person at the top of the stack (who is taller than the current person) will see the current person. So, increment the visible count for that person.
- Push the current index onto the stack.
Corner Cases to Consider:
- What happens if the array is empty or contains only one person?
- Think about cases where all heights are equal, or strictly increasing or decreasing.

Detailed Algorithm (Monotonic Stack Approach)

Initialize:
Create an answer array of the same length as the input heights, initialized to 0. Also, create an empty stack (to store indices).
Traverse the Queue (Left to Right):
For each person at index i with height h:
- While the Stack Is Non-Empty and the Height of the Person at the Top of the Stack is ≤ h:
  - Pop the top index from the stack.
  - For each popped index, increment its count in the answer array by 1 because the current person is visible to that person (they see over all the popped persons).
- After the While Loop:
  - If the stack is not empty, then the current person is blocked by the person at the top of the stack. In that case, increment the answer of the person at the top of the stack by 1 (since the top person sees the current person).
- Push the Current Index onto the Stack.
Return the Answer Array:
Once the iteration completes, the answer array will hold the count of visible people for each person.

Walkthrough Example

Consider heights = [10, 3, 7, 4, 12, 2].

Index 0, height 10:
Stack is empty.
→ Push index 0.
Stack: [0]
Answer: [0,0,0,0,0,0]
Index 1, height 3:
Height at stack top = 10, which is greater than 3.
→ Increment answer[0] (person at index 0 can see index 1).
→ Push index 1.
Stack: [0, 1]
Answer: [1,0,0,0,0,0]
Index 2, height 7:
Height at stack top (index 1) = 3 ≤ 7, so pop index 1 and increment its answer.
→ answer[1] becomes 1.
Now, stack top = index 0 with height 10, which is > 7.
→ Increment answer[0] (person at index 0 sees index 2).
→ Push index 2.
Stack: [0, 2]
Answer: [2,1,0,0,0,0]
Index 3, height 4:
Stack top = index 2 with height 7, which is > 4.
→ Increment answer[2] (person at index 2 sees index 3).
→ Push index 3.
Stack: [0, 2, 3]
Answer: [2,1,1,0,0,0]
Index 4, height 12:
Process stack from top:
- Stack top index 3 (height 4) ≤ 12 → pop index 3; answer[3] becomes 1.
- New stack top index 2 (height 7) ≤ 12 → pop index 2; answer[2] becomes 2.
- New stack top index 0 (height 10) ≤ 12 → pop index 0; answer[0] becomes 3. Now stack is empty. → Push index 4.
  Stack: [4]
  Answer: [3,1,2,1,0,0]
Index 5, height 2:
Stack top = index 4 (height 12) > 2.
→ Increment answer[4] (person at index 4 sees index 5).
→ Push index 5.
Stack: [4, 5]
Answer: [3,1,2,1,1,0]

Final output is the answer array: [3, 1, 2, 1, 1, 0].

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
Each element is pushed and popped at most once, so the overall time complexity is O(n), where n is the number of people (length of the heights array).
Space Complexity:
The stack uses O(n) space in the worst case.

Edge Cases

When designing and testing your solution, be sure to consider the following edge cases:

Empty Input:
- Case: The heights array is empty ([]).
- Expected Behavior: The returned answer should also be an empty array since there are no people in the queue.
Single Person:
- Case: The array contains only one person (e.g. [5]).
- Expected Behavior: The answer should be [0] because with only one person, there is no one else to be seen.
All Equal Heights:
- Case: All persons have the same height (e.g. [4, 4, 4, 4]).
- Expected Behavior:
  - Each person (except the last) will see the next person, but once one person sees someone of equal height, that person blocks further view behind them.
  - A typical output might be [1, 1, 1, 0], because every person can see exactly one person in front of them, and the last person sees none.
Strictly Increasing Heights:
- Case: The heights are strictly increasing (e.g. [1, 2, 3, 4]).
- Expected Behavior:
  - Each person can only see the very next person since each next person is taller and immediately blocks the view further.
  - The answer would be [1, 1, 1, 0].
Strictly Decreasing Heights:
- Case: The heights are strictly decreasing (e.g. [5, 4, 3, 2, 1]).
- Expected Behavior:
  - In this scenario, every person can see all persons to their right because no one is tall enough to block the view.
  - For example, the answer for [5, 4, 3, 2, 1] would be [4, 3, 2, 1, 0].

The "Number of Visible People in a Queue" problem is a typical example of problems that can be efficiently solved using a monotonic stack. Here are several related problems that employ similar techniques:

Next Greater Element / Next Greater Element II:
- Concept: Given an array, find for each element the next greater element.
- Similarity: Uses a monotonic stack to keep track of the elements and find the next element that is greater than the current one.
Daily Temperatures:
- Concept: For each day, determine how many days you would have to wait until a warmer temperature occurs.
- Similarity: This problem uses a monotonic decreasing stack to keep track of the days and compare temperatures.
Stock Span Problem:
- Concept: For each day, determine the span of stock prices (how many consecutive days before the current day with a price less than or equal to today's price).
- Similarity: Uses a monotonic stack to efficiently compute spans based on previous values.
Car Fleet:
- Concept: Given the positions and speeds of cars, determine how many car fleets will arrive at a destination.
- Similarity: While not using a monotonic stack directly, it involves processing items in a sorted order and merging groups based on specific criteria, akin to how we process visible people.
Largest Rectangle in Histogram:
- Concept: Find the largest rectangle in a histogram.
- Similarity: This classic problem uses a monotonic stack to determine the bounds of the largest rectangle, a technique that shares similarities with the way we maintain a decreasing sequence in the queue problem.