Abstract / Summary

Given a grid of land heights, find the maximum possible height increase for buildings while keeping the skyline visible from all directions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 67% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Math
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution.maxBuilding method computes the maximum possible height of any building in a line of n buildings, given a set of height restrictions for specific positions. The algorithm first normalizes the restriction set by inserting mandatory constraints for the first and last buildings, then propagates feasible height limits forward and backward across the line. Finally, it evaluates the highest attainable peak between each pair of consecutive constrained positions.

Normalizing the restriction set

The method begins by converting the list of restrictions into a dictionary for constant-time access and by inserting the mandatory constraints for the first and last buildings.

limits = { pos : height for pos, height in restrictions }
limits[1] = 0
if n not in limits:
    limits[n] = n

• The first building is forced to height 0, satisfying the problem’s base condition.
• If the last building lacks an explicit restriction, a placeholder with height n is added. This placeholder represents the theoretical maximum height allowed at position n (the problem statement caps it at n-1, and the later propagation step will tighten it as needed).

Ordering the constrained positions

All positions that now have a known limit are collected and sorted. This ordered list, known, drives the subsequent forward and backward passes.

known = sorted(limits)

Sorting once yields a deterministic traversal order and avoids repeated ordering operations.

Forward propagation of limits

The algorithm walks from left to right, ensuring that each building’s limit does not exceed what is reachable from its left neighbor given the one-unit height-change rule.

for a, b in zip(known, known[1:]):
    gap = b - a
    limits[b] = min(limits[b], limits[a] + gap)

For a pair of consecutive constrained positions a and b, the maximum height at b cannot be larger than the height at a plus the distance gap. The min operation tightens limits[b] accordingly.

Backward propagation of limits

A symmetric pass from right to left enforces the same feasibility condition in the opposite direction.

for a, b in zip(reversed(known[:-1]), reversed(known)):
    gap = b - a
    limits[a] = min(limits[a], limits[b] + gap)

Here limits[a] is reduced if the height reachable from the right neighbor b would otherwise be violated. The two passes together guarantee that every entry in limits respects the one-step height-difference constraint from both sides.

Determining the highest attainable building

With all limits now consistent, the method evaluates the peak that can be formed between each adjacent pair of constrained positions. The peak height is derived from the higher of the two endpoint limits plus the “extra” height that can be built in the middle, which is limited by the remaining distance after accounting for the required slope between the endpoints.

for a, b in zip(known, known[1:]):
    gap  = b - a
    high = max(limits[a], limits[b])
    diff = abs(limits[a] - limits[b])
    result = max(result, high + (gap - diff) // 2)

• high captures the taller endpoint.
• diff is the absolute height difference between the endpoints, which determines the minimum slope needed.
• The term (gap - diff) // 2 computes how many additional height units can be added symmetrically in the middle before the slope constraint is breached.
• result retains the maximum value observed across all intervals.

Edge cases handled

• Missing restriction for the last building - The insertion of a placeholder entry for position n ensures that the algorithm always has a rightmost anchor point, preventing index errors and guaranteeing that the final interval is processed.
• First building height - By explicitly setting limits[1] = 0, the code respects the requirement that the line starts at ground level, even if the input list contains a contradictory restriction.
• Single-building scenario - When n equals 1, the dictionary ends up with a single entry {1: 0}. Both propagation loops iterate over empty ranges, and the final loop also skips execution, leaving result at its initial value of 0, which is the correct maximum height.
• Consecutive identical positions - If the input contains duplicate positions, the dictionary comprehension retains the last supplied height for that position. The subsequent passes treat it as a single constraint, effectively resolving any redundancy.
• Large gaps between constrained positions - The forward and backward passes correctly limit heights across arbitrarily long distances, and the peak calculation uses integer division to handle both even and odd gaps without overflow.

Performance optimizations

• Dictionary for O(1) lookups - Converting the restriction list to a hash map enables constant-time updates during the propagation phases.
• Single sort operation - Sorting the keys once yields an ordered sequence used by all later loops, avoiding repeated ordering work.
• Zip-based pair iteration - Using zip to traverse adjacent pairs eliminates explicit index arithmetic and reduces the number of loop constructs.
• In-place limit updates - The algorithm updates the limits dictionary directly during forward and backward passes, avoiding auxiliary arrays and minimizing memory footprint.
• Integer arithmetic only - All calculations stay within integer domain, which is faster than floating-point operations and sidesteps rounding concerns.

The combination of these choices results in a solution that scales efficiently with the number of buildings and restrictions, delivering the correct maximum height while maintaining a compact and readable implementation.

Imagine there is a big line of empty spots where houses will be built. Each spot is numbered, and the houses must follow some strict rules about how tall they can be. Some spots have special markers showing exactly how tall the house there is allowed to be. Because houses cannot jump up in height too quickly, the height of one house affects its neighbor. If one house is short, the next one cannot be super tall.

First, the building rules are collected into a sort of map so the computer knows the height limit for every special spot. There is also a rule that the very first spot must have a height of zero. The computer then organizes these spots in order from the beginning of the line to the end.

To figure out the tallest possible house, the computer does three passes over these spots. In the first pass, it travels from the start to the end. It looks at each marker and makes sure no house is so tall that it breaks the climbing rule from its neighbor on the left. If a house would be too tall based on the one before it, the limit is lowered.

In the second pass, the computer goes backward from the end to the start. It does this because a house on the right can also limit how tall the house on the left is allowed to be if the ground goes down steeply. By checking both ways, the computer ensures that every building follows the rules set by all the markers.

Finally, the computer looks at every pair of markers. It calculates the space between them and finds the highest point that could exist in that gap without breaking the rules. It keeps track of the tallest height it finds during this process so that at the end, it knows the biggest possible building that fits all the restrictions.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality