Problem

You are given an array representing the heights of neighboring buildings on a city street, from east to west. The city assessor would like you to write an algorithm that returns how many of these buildings have a view of the setting sun, in order to properly value the street.

Assumption: Good to clarify with the interviewer, if the heights are equal? For this problem, equal height building don’t obstruct the view, and should be included in answer.

Follow up

Can you do this using just one forward pass through the array?

Examples

Example 1:

Input: heights = [3, 7, 8, 3, 6, 1]
Output: 3
Explanation: Since the top floors of the buildings with heights `8`, `6`, and `1` all have an unobstructed view to the west.

Solution

Method 1 - Iterating backwards

A building has open sight to the right, which is “west” and we can see the sunset. So, if there is no higher building on the right, we can see the sunset.

Last building will be able to see the sunset, no matter what is the height. The buildings to the left, will have problems, when they have buildings taller than them.

Code

Java
public int buildingsWithSunsetView(int[] heights) {
	int count = 1, n = heights.length;
	
	int max = heights[n - 1];
	for (int i = heights.length - 2; i >= 0; i--) {
		int curr = heights[i];
		if (curr >= max) {
			max = curr;
			count++;
		}
	}
	return count;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - Using Monotonic stack

We can also use NGR - Nearest Greater Element to Right of every element. If we find the next greater element, on the right, that means the view to the west in obstructed. If no such greater element, the view is not obstructed and answer is included.

Code

Java
class Solution {

	public int[] buildingsWithSunsetView(int[] heights) {
		int count = 0;

		Stack<Integer> s = new Stack<Integer>();

		for (int i = heights.length - 1; i >= 0; i--) {
			count++;

			while (!s.empty()) {
				int top = s.peek();

				if (top > heights[i]) {
					count--;
					break;
				} else {
					s.pop();
				}
			}

			s.push(heights[i]);
		}

		return count;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - Using Monotonic Queue

Now, on the follow up, to solve this problem in a single forward pass (left to right), we can use a concept similar to a monotonic stack, where we can traverse the array from the beginning and maintain a stack that keeps track of buildings that can see the sunset.

However, since this is a forward pass, we should utilize a concept of a “monotonic queue” where buildings at the end that are shorter or equal to the last building in the queue (since equal heights do not obstruct the view) will be removed since they won’t see the sunset with a taller or equal-height building in front of them. So, it will be monotonic decreasing queue.

Code

Java
 public class Solution {
 
     public int countBuildingsWithSunsetView(int[] heights) {
         Deque<Integer> deque = new ArrayDeque<>();
 
         for (int currHeight : heights) {
             while (!deque.isEmpty() && deque.peekLast() <= currHeight) {
                 deque.pollLast();
             }
             deque.addLast(currHeight);
         }
 
         return deque.size();
     }
}

Dry Run

heights = [3, 7, 8, 3, 6, 1]

  • currHeight = 3, as queue is empty we add to queue. deque = [3]
  • currHeight = 7, as 7 is more than 3 in queue, it obstructs sunset view. Hence, we dequeue 3. And then add 7 to queue. deque = [7]
  • currHeight = 8, as 8 is more than 7 in queue, it obstructs sunset view. Hence, we dequeue 7. And then add 8 to queue. deque = [8]
  • currHeight = 3, as 3 is less than 8 in queue, we wont poll 8. Add 3 to queue. deque = [8, 3]
  • currHeight = 6, as 6 is more than 3 in deque, we poll out 3. And add 6 now. deque = [8, 6]
  • currHeight = 1, as 1 is less than 6 in dequeue, we just add 1 to dequeue. deque = [8, 6, 1].

Now, loop has ended, and size of deque is, 3, so we return the answer.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)