Problem Statement
You are given an array arr[] where arr[i] represents the height of the i-th person standing in a line.
A person i can see another person j if:
Each person can look in both directions (left and right).
Your task is to determine the maximum number of people visible to any person, including the person themselves.
Example
Input
arr = [6, 2, 5, 4, 5, 1, 6]
Output
6
Explanation
The first person (height = 6) can see:
6, 2, 5, 4, 5, 1
Total visible people:
6
including themselves.
Similarly, the last person can also see 6 people.
Hence, the answer is:
6
Understanding the Visibility Rule
Consider a person of height H.
While looking left or right:
They can see only people shorter than H.
As soon as a person with height greater than or equal to H appears, the view is blocked.
The blocking person is not visible because visibility requires:
height[j] < height[i]
Therefore, the visibility region ends just before the first greater-or-equal person.
Key Observation
For every person i, we need to know two boundaries.
Left Boundary
The nearest person on the left whose height is:
>= arr[i]
This is called the:
Previous Greater-or-Equal Element (PGE)
Right Boundary
The nearest person on the right whose height is:
>= arr[i]
This is called the:
Next Greater-or-Equal Element (NGE)
Why These Boundaries Matter
Suppose:
left[i] = nearest greater-or-equal index on left
right[i] = nearest greater-or-equal index on right
Then every person between:
(left[i] + 1) and (right[i] - 1)
is shorter than arr[i].
Therefore, person i can see the entire range:
left[i] + 1 ... right[i] - 1
including themselves.
Thus:
visibleCount = right[i] - left[i] - 1
Dry Run
Consider:
arr = [6, 2, 5, 4, 5, 1, 6]
First Person
Height:
6
Nearest greater-or-equal on the left:
None
left = -1
Nearest greater-or-equal on the right:
Index 6 (height = 6)
right = 6
Visible count:
6 - (-1) - 1 = 6
Visible people:
[6, 2, 5, 4, 5, 1]
Total:
6
Brute Force Approach
For each person:
Move left until the view is blocked.
Move right until the view is blocked.
Count visible people.
Complexity
O(n²)
This exceeds the expected complexity for large inputs.
Optimized Approach Using Monotonic Stack
The problem can be transformed into:
Both can be computed efficiently using a monotonic decreasing stack.
Step 1: Find Previous Greater-or-Equal
Maintain a stack of indices.
For every index i:
while (!st.empty() && arr[st.top()] < arr[i])
st.pop();
left[i] = st.empty() ? -1 : st.top();
st.push(i);
After removing all smaller heights:
The stack top becomes the nearest greater-or-equal element on the left.
If the stack is empty, no such element exists.
Step 2: Find Next Greater-or-Equal
Traverse from right to left.
Again, remove all smaller elements:
while (!st.empty() && arr[st.top()] < arr[i])
st.pop();
right[i] = st.empty() ? n : st.top();
st.push(i);
After processing:
Step 3: Calculate Visibility
For each person:
visible = right[i] - left[i] - 1
Track the maximum value among all people.
Why Monotonic Stack Works
The stack always maintains heights in decreasing order.
Whenever a taller person appears:
Smaller heights lose their usefulness
because they can no longer serve as the nearest greater-or-equal boundary for future elements.
Therefore, they are permanently removed.
Each index:
This guarantees linear complexity.
C++ Solution
class Solution {
public:
int maxPeople(vector<int> &arr) {
int n = arr.size();
vector<int> left(n), right(n);
stack<int> st;
// Previous Greater-or-Equal
for(int i = 0; i < n; i++) {
while(!st.empty() &&
arr[st.top()] < arr[i])
st.pop();
left[i] = st.empty() ? -1 : st.top();
st.push(i);
}
while(!st.empty())
st.pop();
// Next Greater-or-Equal
for(int i = n - 1; i >= 0; i--) {
while(!st.empty() &&
arr[st.top()] < arr[i])
st.pop();
right[i] = st.empty() ? n : st.top();
st.push(i);
}
int ans = 0;
for(int i = 0; i < n; i++) {
ans = max(ans,
right[i] - left[i] - 1);
}
return ans;
}
};
Complexity Analysis
Time Complexity
Each index is pushed and popped at most once.
O(n)
Space Complexity
The arrays:
left[]
right[]
and the stack require:
O(n)
extra space.
Interview Pattern Recognition
Whenever a problem contains phrases such as:
Think immediately of:
Monotonic Stack
This pattern appears frequently in interview questions, including:
Why This Solution Is Efficient
Instead of checking visibility for every pair of people, we identify the nearest blocking person on both sides. Once these boundaries are known, the visible range can be calculated directly using a simple formula. Monotonic stacks make it possible to find these boundaries in linear time.
Key Takeaway
The crucial insight is that a person's visible region is bounded by the nearest person on both sides whose height is greater than or equal to theirs. Once the problem is transformed into finding Previous and Next Greater-or-Equal Elements, a Monotonic Stack provides an elegant and efficient O(n) solution.
Summary
To determine the maximum number of visible people, find the nearest greater-or-equal person on the left and right for every individual. These boundaries define the entire visibility range. Using a monotonic decreasing stack, both boundaries can be computed in linear time, resulting in an overall complexity of O(n) with O(n) extra space. This problem is a classic application of the Previous Greater Element and Next Greater Element patterns.
Join the conversation! Your thoughts help the community grow.