# Count Number of Buildings Facing Sun

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

### Let’s understand the problem

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

### Solution Idea using a single loop

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.

#### Solution steps

1. Before starting the loop, we initialize two variables: currMaxHeight with height[0] and buildingCount with 1.
2. 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.
3. By the end of the loop, we return the value stored in the variable buildingCount as the output.

#### Solution code C++

``````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;
}``````

#### Solution code Python

``````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``````

#### 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).

### Critical ideas to think!

• 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?

### Suggested coding questions to practice

Enjoy learning, Enjoy coding!