Abstract / Summary

Given a list of tower heights, determine if it is possible to make all towers the same height by moving blocks between them.

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 45% (70k+ submissions).

Typical patterns to solve this problem:

• Array
• Monotonic Stack
• Stack

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 class implements a method maximumSumOfHeights that receives a list of integers representing upper bounds for a sequence of heights. The goal of the method is to determine the greatest possible total sum of a height configuration that respects two constraints: each height must not exceed its corresponding upper bound, and the heights must form a non-increasing sequence when moving outward from a chosen peak position. The implementation follows a straightforward exhaustive approach, evaluating every index as a potential peak and aggregating the feasible heights to the left and right of that peak.

Key Steps

The algorithm proceeds through three distinct phases for each candidate peak index.

Selecting a Peak

for i, m in enumerate(maxHeights):
    total = 0

The outer loop iterates over the list maxHeights, exposing both the index i and the maximum allowable height m at that position. A running accumulator total is initialized for each candidate peak.

Scanning to the Left

height = m
for j in reversed(range(i)):
    height = min(height, maxHeights[j])
    total += height

Starting from the peak, the code walks leftward through the indices preceding i. The variable height holds the current permissible height, which is continuously reduced to the minimum of its current value and the upper bound at the examined position maxHeights[j]. This ensures the left side never rises above the height of any element closer to the peak. Each adjusted height is added to total.

Scanning to the Right

height = m
for j in range(i, len(maxHeights)):
    height = min(height, maxHeights[j])
    total += height

A symmetric scan proceeds from the peak toward the end of the list. The same monotonic reduction logic applies, guaranteeing that the right side also respects the non-increasing requirement relative to the peak. The contributions from the right side are accumulated into the same total variable.

Updating the Global Maximum

result = max(result, total)

After both directional scans complete for a given peak, the algorithm compares the computed total with the best result seen so far, retaining the larger value.

Returning the Answer

return result

When all indices have been examined as potential peaks, the method returns the highest sum discovered.

Edge Cases Handled

When the input list contains a single element, the outer loop executes once, the left scan iterates over an empty range, and the right scan processes the sole element. The algorithm correctly returns that element’s value as the maximum sum.

If the list consists of monotonically decreasing values, each left scan will quickly converge to the smallest encountered bound, while the right scan will maintain the decreasing trend without needing to lower the height further. The method therefore captures the sum of the original sequence, which is the optimal configuration.

Conversely, for a monotonically increasing list, the left scan will progressively lower the height to match earlier, smaller bounds, while the right scan will start from the peak and immediately reduce to the first element’s bound. This behavior ensures that the resulting configuration never violates the non-increasing rule, and the algorithm still evaluates every possible peak to find the best achievable sum.

When multiple equal maximum heights appear, each occurrence is treated as an independent peak candidate. The scans on both sides will produce identical totals for those positions, and the global maximum will reflect the correct sum without duplication or omission.

Performance Optimizations Observed

The implementation leverages the built-in min function to perform the monotonic reduction in constant time per iteration, avoiding any auxiliary data structures for tracking the decreasing sequence. By reusing the same height variable for both left and right scans, the code minimizes memory overhead.

The use of reversed(range(i)) for the leftward traversal eliminates the need for an explicit index decrement, allowing Python’s iterator protocol to handle the backward iteration efficiently. Similarly, the forward scan employs a direct range(i, len(maxHeights)), which benefits from Python’s optimized range object.

The comparison result = max(result, total) updates the best answer in place, preventing the accumulation of intermediate results in additional containers. This in-place update contributes to a lean runtime profile, especially when the input size grows.

Overall, the method maintains a compact control flow, with each loop performing only essential arithmetic and comparison operations, which collectively constitute the primary source of computational work.

Imagine there is a row of blocks of different heights, and the goal is to build a nice, sloping mountain shape using those blocks. To make a mountain, every block must be no taller than the one next to it as you move toward the edges.

This code acts like a tiny architect. It walks through every single block and pretends for a moment that the current block is the very top peek of the mountain. Once the architect decides which block is the peak, it goes exploring. It looks to the left to see how tall the other blocks can be without being taller than their neighbors, and it does the same thing looking to the right.

As it looks around, it keeps track of how many blocks it can use to build this shape. After it finishes measuring the height for the mountain centered at that specific block, it writes down the total number of blocks used. Then, it moves on to the next block and tries again to build a different mountain. Throughout the whole process, it constantly compares the new mountains it builds to the best one found so far, keeping hold of the biggest number it has seen. By the time it has checked every possible peak, it knows exactly how to build the largest mountain possible.

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

Time: polynomial
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	Python		Java	C++		TS
	WalkCCC	Python		Java	C++
	leetcode.ca	Python		Java	C++	Go	TS
	Progiez	Python		Java	C++
github	charles-wangkai			Java
	fsq				C++
	JoshCrozier		JS
	lkwq007	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python

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