💡 Problem Formulation: Imagine you’re looking at a skyline of buildings of varying heights from a fixed point. Some buildings are not visible because taller buildings block them. The goal is to identify buildings that have an unobstructed view towards the observer, presuming we’re looking from east to west. Given an array of heights representing the building’s height from east to west [3, 7, 8, 3, 6, 1], the output should be the list of buildings with an unobstructed view [8, 6, 1].
Method 1: Using a Stack
This method employs a stack to keep track of the buildings that have an unobstructed view. Starting with the last building, we traverse the array from right to left. If the current building is taller than the last one in the stack, it has a view, and we add it to the stack.
Here’s an example:
def buildings_with_view(heights):
stack = []
for height in reversed(heights):
if not stack or height > stack[-1]:
stack.append(height)
return stack[::-1]
print(buildings_with_view([3, 7, 8, 3, 6, 1]))
Output: [8, 6, 1]
The function buildings_with_view() processes the inputs from right to left, comparing each building’s height with the last element of the stack. When a building with height greater than the last element is found, it is added to the stack. The result is then reversed to present the buildings from left to right as they would appear from the observer’s viewpoint.
Method 2: Linear Scan with Temp Variable
This method uses a single pass from right to left, similar to Method 1. Instead of a stack, we use a temp variable to store the height of the tallest building so far. We compare each building’s height with this temp variable to determine if it has a view.
Here’s an example:
def buildings_with_view(heights):
result = []
tallest_so_far = 0
for height in reversed(heights):
if height > tallest_so_far:
result.append(height)
tallest_so_far = height
return result[::-1]
print(buildings_with_view([3, 7, 8, 3, 6, 1]))
Output: [8, 6, 1]
The code snippet implements a scanning method where it keeps updating the tallest_so_far variable whenever a taller building is encountered. It then appends such buildings to the result list. Eventually, the final list is reversed to maintain the left-to-right order.
Method 3: Filter with a Custom Function
We can apply a custom filter condition using a generator to yield buildings that have a better view. The condition ensures that only buildings taller than the last yielded building are considered.
Here’s an example:
def buildings_with_view(heights):
def view(heights):
tallest = 0
for height in reversed(heights):
if height > tallest:
tallest = height
yield height
return list(view(heights))[::-1]
print(buildings_with_view([3, 7, 8, 3, 6, 1]))
Output: [8, 6, 1]
Here, the view() function is a generator that processes the buildings array in reverse order. It updates the tallest variable when a building with a better view is found and yields these buildings. The final result is obtained by converting the generator to a list and then reversing it.
Method 4: Using List Comprehension
A more Pythonic approach might employ list comprehension that internally mimics the stack-based methodology. This can be more readable and succinct for those familiar with Python’s list comprehensions.
Here’s an example:
def buildings_with_view(heights):
return [heights[i] for i in range(len(heights) - 1, -1, -1) if not i max(heights[i + 1:])]
Output: [8, 6, 1]
This list comprehension progresses from the end of the heights list towards the start and selects buildings that are taller than all buildings to the right. It involves computing max(heights[i + 1:]) for each element, which may be inefficient for large lists.
Bonus One-Liner Method 5: Using Functional Programming
This one-liner takes advantage of Python’s functional programming features, such as the filter function, to deliver the desired output with minimal code.
Here’s an example:
print(list(filter(lambda h: heights[heights.index(h):] and h == max(heights[heights.index(h):]), reversed(heights))))
Output: [8, 6, 1]
Using the filter function combined with a lambda function and list slicing, this snippet efficiently compacts the whole process into a single line. The reversed(heights) function ensures we examine buildings from right to left, maintaining the problem’s requirement.
Summary/Discussion
- Method 1: Using a Stack. Strength: Simple and efficient, as it only keeps track of relevant buildings. Weakness: Requires a full traversal of the input and reversing the stack.
- Method 2: Linear Scan with Temp Variable. Strength: Constant space complexity since it uses a single variable instead of a stack. Weakness: Still needs a full reversal at the end.
- Method 3: Filter with a Custom Function. Strength: Utilizes Python’s generators for efficient memory use. Weakness: Could be less intuitive to those unfamiliar with generator functions.
- Method 4: Using List Comprehension. Strength: Very readable for those familiar with Python’s syntax. Weakness: Potentially inefficient for large lists due to repeated max calculations.
- Method 5: Using Functional Programming. Strength: Concise one-liner that’s stylishly Pythonic. Weakness: Readability may suffer; the same efficiency concern as Method 4 with large lists.