TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
floors
, where each element represents the height of a building floor.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a stack to simulate the building of skyscrapers. Iterate through the list of floors, and for each floor, decide whether to start a new skyscraper or add to the existing one based on the height of the current floor compared to the previous one.
1. Initialize an empty stack and a counter `skyscrapers` to 0.
2. Iterate through each floor in the `floors` array:
1. If the stack is empty or the top of the stack is greater than or equal to the current floor:
- Start a new skyscraper (increment `skyscrapers` by 1).
- Push the current floor onto the stack.
2. If the top of the stack is less than the current floor:
- Pop floors from the stack until the stack is empty or the top is greater than or equal to the current floor.
- Push the current floor onto the stack.
3. Return the count of `skyscrapers`.
⚠️ Common Mistakes
def build_skyscrapers(floors):
stack = []
skyscrapers = 0
for floor in floors:
if not stack or stack[-1] >= floor:
skyscrapers += 1
stack.append(floor)
else:
while stack and stack[-1] < floor:
stack.pop()
stack.append(floor)
return skyscrapers
# Example usage
print(build_skyscrapers([10, 5, 8, 3, 7, 2, 9])) # Output: 4
print(build_skyscrapers([7, 3, 7, 3, 5, 1, 6])) # Output: 4
print(build_skyscrapers([8, 6, 4, 7, 5, 3, 2])) # Output: 6