Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
You are given an array heights of n integers representing the number of bricks in n consecutive towers. Your task is to remove some bricks to form a mountain-shaped tower arrangement. In this arrangement, the tower heights are non-decreasing, reaching a maximum peak value with one or multiple consecutive towers and then non-increasing.
Return the maximum possible sum of heights of a mountain-shaped tower arrangement.
Example 1:
Input: heights = [5,3,4,1,1]
Output: 13
Explanation:
We remove some bricks to make heights = [5,3,3,1,1], the peak is at index 0.
Example 2:
Input: heights = [6,5,3,9,2,7]
Output: 22
Explanation:
We remove some bricks to make heights = [3,3,3,9,2,2], the peak is at index 3.
Example 3:
Input: heights = [3,2,5,5,2,3]
Output: 18
Explanation:
We remove some bricks to make heights = [2,2,5,5,2,2], the peak is at index 2 or 3.
Constraints:
1 <= n == heights.length <= 1031 <= heights[i] <= 109Problem summary: You are given an array heights of n integers representing the number of bricks in n consecutive towers. Your task is to remove some bricks to form a mountain-shaped tower arrangement. In this arrangement, the tower heights are non-decreasing, reaching a maximum peak value with one or multiple consecutive towers and then non-increasing. Return the maximum possible sum of heights of a mountain-shaped tower arrangement.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Stack
[5,3,4,1,1]
[6,5,3,9,2,7]
[3,2,5,5,2,3]
valid-mountain-array)minimum-number-of-removals-to-make-mountain-array)maximum-number-of-books-you-can-take)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2865: Beautiful Towers I
class Solution {
public long maximumSumOfHeights(List<Integer> maxHeights) {
long ans = 0;
int n = maxHeights.size();
for (int i = 0; i < n; ++i) {
int y = maxHeights.get(i);
long t = y;
for (int j = i - 1; j >= 0; --j) {
y = Math.min(y, maxHeights.get(j));
t += y;
}
y = maxHeights.get(i);
for (int j = i + 1; j < n; ++j) {
y = Math.min(y, maxHeights.get(j));
t += y;
}
ans = Math.max(ans, t);
}
return ans;
}
}
// Accepted solution for LeetCode #2865: Beautiful Towers I
func maximumSumOfHeights(maxHeights []int) (ans int64) {
n := len(maxHeights)
for i, x := range maxHeights {
y, t := x, x
for j := i - 1; j >= 0; j-- {
y = min(y, maxHeights[j])
t += y
}
y = x
for j := i + 1; j < n; j++ {
y = min(y, maxHeights[j])
t += y
}
ans = max(ans, int64(t))
}
return
}
# Accepted solution for LeetCode #2865: Beautiful Towers I
class Solution:
def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
ans, n = 0, len(maxHeights)
for i, x in enumerate(maxHeights):
y = t = x
for j in range(i - 1, -1, -1):
y = min(y, maxHeights[j])
t += y
y = x
for j in range(i + 1, n):
y = min(y, maxHeights[j])
t += y
ans = max(ans, t)
return ans
// Accepted solution for LeetCode #2865: Beautiful Towers I
/**
* [2865] Beautiful Towers I
*/
pub struct Solution {}
// submission codes start here
impl Solution {
pub fn maximum_sum_of_heights(max_heights: Vec<i32>) -> i64 {
let mut result = 0;
for peek in 0..max_heights.len() {
let mut total_height = max_heights[peek] as i64;
let mut heights = vec![0; max_heights.len()];
heights[peek] = max_heights[peek];
for i in (0..peek).rev() {
heights[i] = max_heights[i].min(heights[i + 1]);
total_height += heights[i] as i64;
}
for i in peek + 1..max_heights.len() {
heights[i] = max_heights[i].min(heights[i - 1]);
total_height += heights[i] as i64;
}
result = result.max(total_height);
}
result
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_2865() {
assert_eq!(Solution::maximum_sum_of_heights(vec![5, 3, 4, 1, 1]), 13);
assert_eq!(Solution::maximum_sum_of_heights(vec![6, 5, 3, 9, 2, 6]), 22);
assert_eq!(Solution::maximum_sum_of_heights(vec![3, 2, 5, 5, 2, 3]), 18);
}
}
// Accepted solution for LeetCode #2865: Beautiful Towers I
function maximumSumOfHeights(maxHeights: number[]): number {
let ans = 0;
const n = maxHeights.length;
for (let i = 0; i < n; ++i) {
const x = maxHeights[i];
let [y, t] = [x, x];
for (let j = i - 1; ~j; --j) {
y = Math.min(y, maxHeights[j]);
t += y;
}
y = x;
for (let j = i + 1; j < n; ++j) {
y = Math.min(y, maxHeights[j]);
t += y;
}
ans = Math.max(ans, t);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.