Number of Buildings Facing Sun

Difficulty: Easy, Asked-in: Amazon, Microsoft

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

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

Count Number of Buildings Facing Sun