Problem

You have N stones in a row, and would like to create from them a pyramid. This pyramid should be constructed such that the height of each stone increases by one until reaching the tallest stone, after which the heights decrease by one. In addition, the start and end stones of the pyramid should each be one stone high.

You can change the height of any stone by paying a cost of 1 unit to lower its height by 1, as many times as necessary. Given this information, determine the lowest cost method to produce this pyramid.

Examples

Example 1

1
2
3

Input: [1, 1, 3, 3, 2, 1]
Output: 2
Explanation: The optimal solution is to pay 2 to create [0, 1, 2, 3, 2, 1]. We reduce stones[0] by 1 (cost 1) and stones[4] by 0 (cost 0), and stones[5] by 0 (cost 0). Total cost = 1 + 0 + 0 + 0 + 0 + 0 = 1. Wait, let me recalculate: [1,1,3,3,2,1] -> [0,1,2,3,2,1] means reduce first stone by 1 and fifth stone by 0. Actually, the target is [0,1,2,3,2,1], so cost = (1-0) + (1-1) + (3-2) + (3-3) + (2-2) + (1-1) = 1 + 0 + 1 + 0 + 0 + 0 = 2.

Example 2

1
2
3

Input: [5, 4, 3, 2, 1]
Output: 6
Explanation: To create pyramid [1, 2, 3, 2, 1], we need costs: (5-1) + (4-2) + (3-3) + (2-2) + (1-1) = 4 + 2 + 0 + 0 + 0 = 6.

Example 3

1
2
3

Input: [1, 2, 3, 4, 5]
Output: 9
Explanation: To create pyramid [1, 2, 3, 2, 1], we need costs: (1-1) + (2-2) + (3-3) + (4-2) + (5-1) = 0 + 0 + 0 + 2 + 4 = 6. But peak at index 2 gives [1,2,3,2,1]. Let's try peak at index 4: [1,2,3,4,5] -> this violates end=1. Peak at index 3: [1,2,3,4,3,2,1] - invalid length. Best is [1,2,3,2,1] with cost 6.

Example 4

1
2
3

Input: [3, 3, 3, 3]
Output: 4
Explanation: For pyramid [1, 2, 2, 1], costs: (3-1) + (3-2) + (3-2) + (3-1) = 2 + 1 + 1 + 2 = 6. For [1, 2, 1, 0], we get negative height which is invalid. The valid pyramid is [1, 2, 2, 1] with cost 6. Actually, let me reconsider: [1, 2, 2, 1] isn't a valid pyramid (should be [1,2,1,0] but 0 height invalid). Valid pyramid: [1, 2, 2, 1] cost = 2+1+1+2=6. But this violates the strict increase-decrease rule. For length 4, valid pyramid is [1,2,2,1] or we consider [0,1,2,1] but 0 height invalid. Actually valid pyramid for length 4 where ends are 1: [1,2,2,1]. Cost = 2+1+1+2=6. But this doesn't strictly increase then decrease. The constraint is ends must be 1, and it should form a mountain. For length 4: [1,2,2,1] seems to be the only valid option if we allow plateaus at peak. Cost = 6. If strict mountain: impossible for even length with end=1 constraint.

Example 5

1
2
3

Input: [10]
Output: 9
Explanation: Single stone must have height 1, so cost = 10 - 1 = 9.

Solution

Method 1 - Dynamic Programming with Peak Selection

Intuition

The key insight is that we need to try every possible position as the peak of the pyramid. For each peak position, we can determine the exact target heights (forming a mountain with peak at that position and ends at height 1), then calculate the cost to achieve those heights.

Approach

  1. For each possible peak position i from 0 to n-1, calculate the target pyramid
  2. The target heights form: [1, 2, 3, ..., peak_height, ..., 3, 2, 1]
  3. The peak height at position i is min(i+1, n-i) to ensure ends are height 1
  4. For each position j, calculate target height based on distance from peak
  5. Calculate cost as sum of max(0, current_height - target_height) for all positions
  6. Return minimum cost across all possible peak positions

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    int minCostPyramid(vector<int>& stones) {
        int n = stones.size();
        if (n == 1) return max(0, stones[0] - 1);
        
        int minCost = INT_MAX;
        
        // Try each position as peak
        for (int peak = 0; peak < n; peak++) {
            int cost = calculateCost(stones, peak);
            minCost = min(minCost, cost);
        }
        
        return minCost;
    }
    
private:
    int calculateCost(const vector<int>& stones, int peak) {
        int n = stones.size();
        int totalCost = 0;
        
        for (int i = 0; i < n; i++) {
            int targetHeight;
            if (i <= peak) {
                // Left side: height increases from 1 to peak
                targetHeight = min(i + 1, peak + 1);
            } else {
                // Right side: height decreases from peak to 1
                targetHeight = min(n - i, peak + 1);
            }
            
            // We can only reduce height, not increase
            totalCost += max(0, stones[i] - targetHeight);
        }
        
        return totalCost;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

func minCostPyramid(stones []int) int {
    n := len(stones)
    if n == 1 {
        return max(0, stones[0] - 1)
    }
    
    minCost := math.MaxInt32
    
    // Try each position as peak
    for peak := 0; peak < n; peak++ {
        cost := calculateCost(stones, peak)
        minCost = min(minCost, cost)
    }
    
    return minCost
}

func calculateCost(stones []int, peak int) int {
    n := len(stones)
    totalCost := 0
    
    for i := 0; i < n; i++ {
        var targetHeight int
        if i <= peak {
            // Left side: height increases from 1 to peak
            targetHeight = min(i + 1, peak + 1)
        } else {
            // Right side: height decreases from peak to 1
            targetHeight = min(n - i, peak + 1)
        }
        
        // We can only reduce height, not increase
        totalCost += max(0, stones[i] - targetHeight)
    }
    
    return totalCost
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int minCostPyramid(int[] stones) {
        int n = stones.length;
        if (n == 1) return Math.max(0, stones[0] - 1);
        
        int minCost = Integer.MAX_VALUE;
        
        // Try each position as peak
        for (int peak = 0; peak < n; peak++) {
            int cost = calculateCost(stones, peak);
            minCost = Math.min(minCost, cost);
        }
        
        return minCost;
    }
    
    private int calculateCost(int[] stones, int peak) {
        int n = stones.length;
        int totalCost = 0;
        
        for (int i = 0; i < n; i++) {
            int targetHeight;
            if (i <= peak) {
                // Left side: height increases from 1 to peak
                targetHeight = Math.min(i + 1, peak + 1);
            } else {
                // Right side: height decreases from peak to 1
                targetHeight = Math.min(n - i, peak + 1);
            }
            
            // We can only reduce height, not increase
            totalCost += Math.max(0, stones[i] - targetHeight);
        }
        
        return totalCost;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def min_cost_pyramid(self, stones: List[int]) -> int:
        n = len(stones)
        if n == 1:
            return max(0, stones[0] - 1)
        
        min_cost = float('inf')
        
        # Try each position as peak
        for peak in range(n):
            cost = self._calculate_cost(stones, peak)
            min_cost = min(min_cost, cost)
        
        return min_cost
    
    def _calculate_cost(self, stones: List[int], peak: int) -> int:
        n = len(stones)
        total_cost = 0
        
        for i in range(n):
            if i <= peak:
                # Left side: height increases from 1 to peak
                target_height = min(i + 1, peak + 1)
            else:
                # Right side: height decreases from peak to 1
                target_height = min(n - i, peak + 1)
            
            # We can only reduce height, not increase
            total_cost += max(0, stones[i] - target_height)
        
        return total_cost

Complexity

  • ⏰ Time complexity: O(n²), where n is the number of stones. We try each position as peak (O(n)) and for each peak calculate cost for all positions (O(n))
  • 🧺 Space complexity: O(1), only using constant extra space for calculations

Method 2 - Dynamic Programming Optimization

Intuition

The key insight is that we can precompute the maximum possible pyramid height at each position by considering constraints from both left and right sides. The maximum height at any position is limited by: the stone’s current height, the position index (since pyramid starts from 1), and the neighboring positions.

Approach

  1. Left Pass: For each position, calculate maximum possible height considering left-to-right constraints
    • left[i] = min(stones[i], min(left[i-1] + 1, i + 1))
    • This ensures pyramid can increase by 1 and doesn’t exceed stone height
  2. Right Pass: For each position, calculate maximum possible height considering right-to-left constraints
    • right[i] = min(stones[i], min(right[i+1] + 1, n - i))
    • This ensures pyramid can decrease by 1 toward the end
  3. Combine: Take minimum of left and right constraints for actual maximum height at each position
  4. Find Peak: The position with maximum combined height becomes our optimal peak
  5. Calculate Cost: Sum the reduction costs for the optimal pyramid configuration

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
public:
    int minCostPyramid(vector<int>& stones) {
        int n = stones.size();
        if (n == 1) return max(0, stones[0] - 1);
        
        vector<int> left(n), right(n);
        
        // Left pass: calculate max height considering left constraints
        left[0] = min(stones[0], 1);
        for (int i = 1; i < n; i++) {
            left[i] = min(stones[i], min(left[i-1] + 1, i + 1));
        }
        
        // Right pass: calculate max height considering right constraints  
        right[n-1] = min(stones[n-1], 1);
        for (int i = n-2; i >= 0; i--) {
            right[i] = min(stones[i], min(right[i+1] + 1, n - i));
        }
        
        // Find maximum possible height at each position
        vector<int> maxHeight(n);
        int peakHeight = 0, peakPos = 0;
        for (int i = 0; i < n; i++) {
            maxHeight[i] = min(left[i], right[i]);
            if (maxHeight[i] > peakHeight) {
                peakHeight = maxHeight[i];
                peakPos = i;
            }
        }
        
        // Calculate minimum cost for optimal pyramid
        int totalCost = 0;
        for (int i = 0; i < n; i++) {
            int targetHeight = maxHeight[peakPos] - abs(i - peakPos);
            if (targetHeight > 0) {
                totalCost += max(0, stones[i] - targetHeight);
            } else {
                totalCost += stones[i]; // Reduce to 0
            }
        }
        
        return totalCost;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

func minCostPyramidOptimized(stones []int) int {
    n := len(stones)
    if n == 1 {
        return max(0, stones[0] - 1)
    }
    
    left := make([]int, n)
    right := make([]int, n)
    
    // Left pass: calculate max height considering left constraints
    left[0] = min(stones[0], 1)
    for i := 1; i < n; i++ {
        left[i] = min(stones[i], min(left[i-1] + 1, i + 1))
    }
    
    // Right pass: calculate max height considering right constraints
    right[n-1] = min(stones[n-1], 1)
    for i := n-2; i >= 0; i-- {
        right[i] = min(stones[i], min(right[i+1] + 1, n - i))
    }
    
    // Find maximum possible height at each position
    maxHeight := make([]int, n)
    peakHeight, peakPos := 0, 0
    for i := 0; i < n; i++ {
        maxHeight[i] = min(left[i], right[i])
        if maxHeight[i] > peakHeight {
            peakHeight = maxHeight[i]
            peakPos = i
        }
    }
    
    // Calculate minimum cost for optimal pyramid
    totalCost := 0
    for i := 0; i < n; i++ {
        targetHeight := maxHeight[peakPos] - abs(i - peakPos)
        if targetHeight > 0 {
            totalCost += max(0, stones[i] - targetHeight)
        } else {
            totalCost += stones[i] // Reduce to 0
        }
    }
    
    return totalCost
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    public int minCostPyramid(int[] stones) {
        int n = stones.length;
        if (n == 1) return Math.max(0, stones[0] - 1);
        
        int[] left = new int[n];
        int[] right = new int[n];
        
        // Left pass: calculate max height considering left constraints
        left[0] = Math.min(stones[0], 1);
        for (int i = 1; i < n; i++) {
            left[i] = Math.min(stones[i], Math.min(left[i-1] + 1, i + 1));
        }
        
        // Right pass: calculate max height considering right constraints
        right[n-1] = Math.min(stones[n-1], 1);
        for (int i = n-2; i >= 0; i--) {
            right[i] = Math.min(stones[i], Math.min(right[i+1] + 1, n - i));
        }
        
        // Find maximum possible height at each position
        int[] maxHeight = new int[n];
        int peakHeight = 0, peakPos = 0;
        for (int i = 0; i < n; i++) {
            maxHeight[i] = Math.min(left[i], right[i]);
            if (maxHeight[i] > peakHeight) {
                peakHeight = maxHeight[i];
                peakPos = i;
            }
        }
        
        // Calculate minimum cost for optimal pyramid
        int totalCost = 0;
        for (int i = 0; i < n; i++) {
            int targetHeight = maxHeight[peakPos] - Math.abs(i - peakPos);
            if (targetHeight > 0) {
                totalCost += Math.max(0, stones[i] - targetHeight);
            } else {
                totalCost += stones[i]; // Reduce to 0
            }
        }
        
        return totalCost;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def min_cost_pyramid(self, stones: List[int]) -> int:
        n = len(stones)
        if n == 1:
            return max(0, stones[0] - 1)
        
        left = [0] * n
        right = [0] * n
        
        # Left pass: calculate max height considering left constraints
        left[0] = min(stones[0], 1)
        for i in range(1, n):
            left[i] = min(stones[i], min(left[i-1] + 1, i + 1))
        
        # Right pass: calculate max height considering right constraints
        right[n-1] = min(stones[n-1], 1)
        for i in range(n-2, -1, -1):
            right[i] = min(stones[i], min(right[i+1] + 1, n - i))
        
        # Find maximum possible height at each position
        max_height = [min(left[i], right[i]) for i in range(n)]
        peak_height = max(max_height)
        peak_pos = max_height.index(peak_height)
        
        # Calculate minimum cost for optimal pyramid
        total_cost = 0
        for i in range(n):
            target_height = max_height[peak_pos] - abs(i - peak_pos)
            if target_height > 0:
                total_cost += max(0, stones[i] - target_height)
            else:
                total_cost += stones[i]  # Reduce to 0
        
        return total_cost

Complexity

  • ⏰ Time complexity: O(n), where n is the number of stones. We make three linear passes through the array: left pass, right pass, and cost calculation
  • 🧺 Space complexity: O(n), for storing the left, right, and max_height arrays