Buildings with Sunset View

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given an array of positive integers representing the heights of a row of buildings. You are observing these buildings from the far right side (i.e., from a position at infinity on the positive x-axis).

A building is considered to have a "sunset view" if no building to its right is taller than or equal to it.

Your task is to find and return a list of the heights of all buildings that have a sunset view, in the order they appear from left to right in the original array.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'N', the number of buildings.

The second line contains 'N' space-separated integers, representing the heights of the buildings.

Output Format:

Print a single line containing the space-separated heights of the buildings with a sunset view, in their original order.

Note:

The rightmost building in the array always has a sunset view.

The most efficient way to solve this is to iterate through the array from right to left, keeping track of the maximum height seen so far.

Sample Input 1:

4
1 2 3 4

Sample Output 1:

Explanation for Sample 1:

Start at 4. It has a view. Max seen = 4.
Next is 3. `3 < 4`. No view.
Next is 2. `2 < 4`. No view.
Next is 1. `1 < 4`. No view.
Only the rightmost building has a view.

Sample Input 2:

4
4 3 2 1

Sample Output 2:

4 3 2 1

Explanation for Sample 2:

Every building is taller than all buildings to its right, so every building has a view.

Expected Time Complexity:

The expected time complexity is O(N), where N is the number of buildings.

Constraints:

1 <= N <= 10^5
1 <= height <= 10^9

Time limit: 1 sec

Approaches (2)

Approach 1

Approach 2

Buildings with Sunset View

Time Complexity

Space Complexity

(100% EXP penalty)

Buildings with Sunset View

Console