How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Ge.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Ge during technical interviews.

Count visible people to the right

Company: Ge

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given an array `heights` of length `n`, where `heights[i]` is the height of the `i`-th person standing in a line from left to right. For each index `i`, compute how many people to the **right** of `i` are **visible** to person `i`. ### Visibility rule Person `i` can see person `j` (`j > i`) if **every** person `k` with `i < k < j` is shorter than **both** `i` and `j`: - `heights[k] < min(heights[i], heights[j])` for all `k` between them. Equivalently (often easier to reason about): looking from `i` to the right, person `i` can see a sequence of shorter people, and they can also see the first person whose height is **greater than or equal to** `heights[i]` (and then visibility stops beyond that point). ### Input - Integer array `heights` (size `n`). ### Output - Integer array `ans` of size `n` where `ans[i]` is the number of visible people to the right of person `i`. ### Example - Input: `heights = [10, 6, 8, 5, 11, 9]` - Output: `[3, 1, 2, 1, 1, 0]` ### Constraints - `1 <= n <= 100000` - `1 <= heights[i] <= 10^9`

Quick Answer: This question evaluates algorithmic problem-solving with arrays and visibility relations, assessing competency in array traversal, handling of relative ordering constraints, and designing time- and space-efficient approaches.

You are given an array `heights` of length `n`, where `heights[i]` is the height of the `i`-th person standing in a line from left to right. For each index `i`, compute how many people to the **right** of `i` are **visible** to person `i`. **Visibility rule:** Person `i` can see person `j` (`j > i`) if and only if every person `k` strictly between them is shorter than **both** endpoints: `heights[k] < min(heights[i], heights[j])` for all `k` with `i < k < j`. Return an integer array `ans` of size `n` where `ans[i]` is the number of visible people to the right of person `i`. **Example:** - Input: `heights = [10, 6, 8, 5, 11, 9]` - Output: `[3, 1, 2, 1, 1, 0]` From index 0 (height 10): sees 6, then 8 (the 6 between is < min(10,8)), then 11 (everything between is < 10), but visibility stops at 11 since 11 >= 10. So 3 people.

Constraints

1 <= n <= 100000
1 <= heights[i] <= 10^9

Examples

Input: [10, 6, 8, 5, 11, 9]

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

Explanation: Index 0 (h=10) sees 6, 8, and 11 (11 >= 10 stops it) -> 3. Index 2 (h=8) sees 5 and 11 -> 2. The last person sees no one to the right -> 0.

Input: []

Expected Output: []

Explanation: Empty line: no people, so the answer array is empty.

Input: [5]

Expected Output: [0]

Explanation: A single person has nobody to the right, so 0 visible.

Input: [1, 2, 3, 4, 5]

Expected Output: [1, 1, 1, 1, 0]

Explanation: Strictly increasing: each person's immediate right neighbor is taller-or-equal and blocks the rest, so everyone sees exactly the next person (last sees none).

Input: [5, 4, 3, 2, 1]

Expected Output: [1, 1, 1, 1, 0]

Explanation: Strictly decreasing: person i sees only the immediate next (shorter) neighbor; the one after is hidden because the neighbor between is not shorter than min of the two endpoints.

Input: [7, 7, 7, 7]

Expected Output: [1, 1, 1, 0]

Explanation: All equal heights: each person sees only the immediate next neighbor (an equal-height person blocks everyone behind them since heights[k] < min(...) fails).

Input: [2, 1, 1, 3]

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

Explanation: Index 0 (h=2) sees the first 1 (visible) and the 3 (both 1s between are < min(2,3)=2), but NOT the second 1, because the first 1 is not < min(2,1)=1. So 2 visible.

Input: [6, 2, 5, 4, 5, 1, 6]

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

Explanation: Index 0 (h=6) sees 2, then 5, then the next 5... it sees indices 1,2,4? Following the rule: 2 (adjacent), 5 at idx2 (2<min(6,5)), and 6 at idx6 (everything between < 6) -> 3. Index 4 (h=5) sees 1 and the final 6 -> 2.

Hints

Process the array from right to left while maintaining a stack of candidate heights.
From person i, you can see a run of people whose heights strictly increase, plus the first person who is at least as tall as i (that person blocks everyone behind them).
Pop every height on the stack that is strictly less than heights[i] (each popped person is visible). If the stack is still non-empty afterward, that top person (height >= heights[i]) is also visible — add one more.
Keep the stack strictly decreasing: before pushing heights[i], also remove any equal heights. This is what makes ties block correctly, e.g. [2,1,1,3] gives 2 (not 3) for index 0 because the second 1 hides the first.

Quick Overview

This question evaluates algorithmic problem-solving with arrays and visibility relations, assessing competency in array traversal, handling of relative ordering constraints, and designing time- and space-efficient approaches.