Build the Tallest Skyscraper - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is an array floors, where each element represents the height of a building floor.
• Q: What is the output?
  • A: The output is an integer representing the number of skyscrapers that can be built using the given floors.
• Q: What are the rules for building a skyscraper?
  • A: Each floor must be placed on top of a floor with equal or greater height. A new skyscraper can only be started when no more floors can be added to the current one.

P-lan

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

• Not correctly handling the case where multiple floors of the same height should be part of the same skyscraper.
• Failing to pop elements from the stack when the current floor is taller than the top of the stack.

I-mplement

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