**Difficulty:** Easy, **Asked-in:** Amazon, Microsoft

**Key takeaway:** An excellent problem to learn problem-solving by building partial solutions using a single loop.

Given an input array height[] representing the heights of buildings, write a program to count the number of buildings facing the sunset. It is assumed that the heights of all buildings are distinct.

Input: height[] = [7, 4, 8, 2, 9], Output: 3 Explanation: As 7 is the first element, it can see the sunset. Similarly, 8 and 9 can see the sunset. 4 and 2 can't see the sunset because 7 and 8 are hiding it.

Input: height[] = [2, 3, 4, 5], Output: 4

For each building height [i], if the maximum height among the buildings from height[0] to height[i-1] is less than height[i], then building height[i] can see the sunset. Otherwise, building height[i] will be hiding by some larger building before it.

So solution idea is to scan the height[] array from left to right and track two variables: the current maximum height seen so far and the number of buildings facing the sun. If the current max height is less than the height[i], we update the max height to height[i] and increment the building count by 1.

- Before starting the loop, we initialize two variables:
**currMaxHeight**with height[0] and**buildingCount**with 1. -
Now we run a loop from

**i**= 1 to**n**- 1. At each**ith**iteration:- When we find height[i] >
**currMaxHeight**, we increment**buildingCount**by 1, update**currMaxHeight**with height[i], and move to the next iteration. - Otherwise, the building with height[i] will be guaranteed hidden by the building with height
**currMaxHeight**. So the height[i] building will not see the sunset, and we ignore it.

- When we find height[i] >
- By the end of the loop, we return the value stored in the variable
**buildingCount**as the output.

```
int facingSunCount(int height[], int n)
{
int buildingCount = 1;
int currMaxHeight = height[0];
for (int i = 1; i < n; i = i + 1)
{
if (height[i] > currMaxHeight)
{
buildingCount = buildingCount + 1;
currMaxHeight = height[i];
}
}
return buildingCount;
}
```

```
def facingSunCount(height, n):
buildingCount = 1
currMaxHeight = height[0]
for i in range(1, n):
if height[i] > currMaxHeight:
buildingCount = buildingCount + 1
currMaxHeight = height[i]
return buildingCount
```

We are running loop n-1 times and doing O(1) operations at each iteration. So time complexity = O(n)* O(1) = O(n). We are using a constant number of variables, so space complexity = O(1).

- How can we modify the above code to also return the building that can see the sunset?
- How can we modify the above code when some buildings have the same height? Assume that a building of the same height will block the one after it.
- Is it possible to solve this problem using a stack?

- Valid mountain array
- The minimum and maximum value in an array
- Leaders in an array
- Roman to Integer
- Find equilibrium index of an array

**Enjoy learning, Enjoy coding!**

Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.

©2023 Code Algorithms Pvt. Ltd.

All rights reserved.