Number of buildings facing the 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 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

  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, 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.
  3. 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).

Critical ideas to think!

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

Suggested coding questions to practice

Critical Concepts To Explore

Enjoy learning, Enjoy coding!

Our Weekly Newsletter

Subscribe to get well-designed content on data structures and algorithms, machine learning, system design, oops, and mathematics. enjoy learning!

We Welcome Doubts and Feedback!

More Content From EnjoyAlgorithms