**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.

**Examples**

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 every building height[i], if the max (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 the solution idea is to scan the height[] array from left to right and track two things using variables: current maximum height seen so far and building count facing the sun. If the current max height is less than the building height[i], we update the max height with height[i] and increment the building count by 1.

Note: It can be easily observed that only the maximum height found so far will see the sunset and then only the element greater than the maximum height found so far will see the sunset. In other words, all the buildings facing sunlight will be arranged in increasing order! Think!

**Solution steps**

- 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, then 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 one of the previous larger buildings with height currMaxHeight. So height[i] building will not see the sunset and we need to ignore this.

- By the end of the loop, we return the value stored in the variable buildingCount as an output.

**Solution Pseudocode**

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

**Time and space complexity analysis**

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 do we modify the above code when we also need to return the building which 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 one after it.
- Can we solve this problem using a stack?

- Roman to Integer
- Find equilibrium index of an array
- Move zeroes to the end of an array
- Valid Mountain Array
- The minimum and maximum value in an array
- The maximum difference between two elements

**Enjoy learning, Enjoy coding!**

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.