Build the Tallest Skyscraper

TIP103 Unit 3 Session 2 (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 is the height of one building floor.
• Q: What is the output?
  • A: The output is an integer: the number of skyscrapers we build.
• Q: Can we sort or reorder the floors?
  • A: No. We place the floors one at a time, in the order they appear in floors. (If we could sort them, every input would build only 1 skyscraper.)
• Q: When does a floor go on the current skyscraper?
  • A: When its height is less than or equal to the height of the current skyscraper’s top floor.
• Q: What if the floor is taller than the top floor?
  • A: We start a new skyscraper with it. The new skyscraper becomes the current skyscraper.
• Q: Can we go back and add a floor to an earlier skyscraper?
  • A: No. Only the current skyscraper can grow.
• Q: What if floors is empty?
  • A: Return 0.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to hold the floors of the current skyscraper. The top of the stack is the skyscraper’s top floor. For each floor, look at the top of the stack. If the floor fits, push it. If it is taller, the current skyscraper is finished: start a new stack with this floor and add 1 to the count.

1. Initialize an empty stack `current` and a counter `skyscrapers` to 0.
2. Iterate through each floor in the `floors` array:
   1. If `current` is not empty and the floor is less than or equal to the top of `current`:
       - Place the floor on the current skyscraper (push it onto `current`).
   2. Otherwise (`current` is empty, or the floor is taller than the top floor):
       - Start a new skyscraper: reset `current` so it holds only this floor.
       - Increment `skyscrapers` by 1.
3. Return `skyscrapers`.

Note: The top floor of the current skyscraper is always the floor that came just before. So you can also solve this without a stack: count 1 for the first floor, then add 1 each time a floor is taller than the floor before it. This session practices stacks, so the solution below uses one.

⚠️ Common Mistakes

• Sorting the floors first. The floors must be used in the given order.
• Adding a floor to an earlier skyscraper. Only the current skyscraper can grow.
• Starting a new skyscraper when a floor has the same height as the top floor. Floors with equal heights can go on top of each other.

I-mplement

def build_skyscrapers(floors):
    current = []  # floors of the skyscraper we are building now
    skyscrapers = 0

    for floor in floors:
        # The floor fits on top of the current skyscraper
        if current and floor <= current[-1]:
            current.append(floor)

        # No skyscraper yet, or the floor is taller than the top floor:
        # start a new skyscraper with this floor
        else:
            current = [floor]
            skyscrapers += 1

    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: 2