Maximum Building Height

Maximum Building Height

What is this problem about?

The Maximum Building Height problem is a challenging math and array problem. You have n building slots arranged in a line (1 to n). Building 1 must have height 0. For any two adjacent buildings, their height difference cannot exceed 1. Additionally, you are given a list of restrictions: (id, maxHeight) which limits the height of specific buildings.

The goal is to find the maximum possible height any building can reach while satisfying all conditions.

Why is this asked in interviews?

Companies like Dataminr use this hard-level question to test:

1. Constraint Propagation: Can you understand how a restriction at one point affects the possible heights at all other points?
2. Multi-pass Algorithms: Often, a single pass isn't enough to settle all constraints. This problem requires a "left-to-right" and "right-to-left" pass, similar to the "Trapping Rain Water" or "Candy" problems.
3. Mathematical Optimization: Finding the peak height between two restricted buildings requires a bit of geometry/algebra.

Algorithmic pattern used

This problem uses Constraint Propagation and Sorting.

1. Sort the restrictions by building ID.
2. Two-Pass Update:
   • Pass 1 (Left to Right): A building's height is limited by the building to its left (height[i] = min(height[i], height[i-1] + gap)).
   • Pass 2 (Right to Left): A building's height is limited by the building to its right (height[i] = min(height[i], height[i+1] + gap)).
3. Peak Calculation: Between any two restricted buildings (id1, h1) and (id2, h2), the maximum height reached between them is (h1 + h2 + (id2 - id1)) / 2.

Example explanation

Buildings 1 to 10. Restriction: Building 10 must be height 3.

1. Building 1 is height 0 (fixed).
2. Gap between 1 and 10 is 9.
3. From left: Building 10 could be 0 + 9 = 9. But restriction says 3. So min(9, 3) = 3.
4. Now calculate the peak between Building 1 (height 0) and Building 10 (height 3):
   • Distance = 9.
   • Height diff = 3.
   • Remaining distance after covering height diff = 9 - 3 = 6.
   • We can go up for 3 more steps and down for 3.
   • Max height = 3 (base) + 3 (extra) = 6. Or use formula: (0 + 3 + 9) / 2 = 6.

Common mistakes candidates make

• Only using one pass: Failing to realize that a restriction at building 100 can limit the height of building 50.
• Ignoring the end: Forgetting that the very last building (if not restricted) can continue to rise after the last restriction.
• Integer Division: Being careless with the math when calculating the peak height between two points.

Interview preparation tip

When dealing with "maximum possible" values subject to "slope" or "difference" constraints, always think about how restrictions propagate in both directions. The "left-pass, right-pass" strategy is a powerful tool for these types of grid or linear array problems.