Pyramid Array with Reduce Operations

Problem Statement

Given an array arr[] where arr[i] represents the height of the i-th stone, we need to convert the array into a pyramid by only reducing the heights of the stones.

Reducing the height of a stone by 1 costs 1 unit.

A valid pyramid has the following form:

1 2 3 ... x-1 x x-1 ... 3 2 1

The pyramid must be a contiguous subarray, and every element outside the pyramid must become 0.

The goal is to find the minimum total reduction cost required to form a valid pyramid.

Example

Consider:

arr = [1, 2, 3, 4, 2, 1]

We can reduce the array to:

[1, 2, 3, 2, 1, 0]

The reductions are:

4 → 2 : cost 2
2 → 1 : cost 1
1 → 0 : cost 1

Total cost:

2 + 1 + 1 = 4

Therefore, the answer is:

Key Idea

Since we can only reduce the heights, we should try to keep as much of the original array as possible while forming a valid pyramid.

Therefore:

Minimum Cost
= Total Height of Original Array
  - Maximum Height That Can Be Kept as a Pyramid

So the main problem becomes:

Find the maximum possible pyramid that can be formed from the given array.

Dynamic Programming Approach

For every position i, we calculate two values.

1. `left[i]`

left[i] represents the maximum possible height at position i when we build the pyramid from the left side.

The height can increase by at most 1 from the previous position.

Therefore:

left[i] = min(arr[i], left[i - 1] + 1)

For example:

arr = [1, 2, 3, 4, 2, 1]

The left values are:

left = [1, 2, 3, 4, 2, 1]

2. `right[i]`

Similarly, right[i] represents the maximum possible height at position i when we build from the right side.

The recurrence is:

right[i] = min(arr[i], right[i + 1] + 1)

For the same example:

right = [1, 2, 3, 3, 2, 1]

Finding the Peak

For a position i to be the peak of the pyramid, it must satisfy both the left and right constraints.

Therefore, the maximum possible peak height at i is:

peak = min(left[i], right[i])

For:

arr = [1, 2, 3, 4, 2, 1]

we get:

left  = [1, 2, 3, 4, 2, 1]
right = [1, 2, 3, 3, 2, 1]

So:

peak = [1, 2, 3, 3, 2, 1]

The maximum peak is:

Thus, the largest pyramid is:

1 2 3 2 1

Important Mathematical Observation

For a pyramid whose peak is x:

1 2 3 ... x-1 x x-1 ... 3 2 1

The sum of all its elements is:

(1 + 2 + ... + x-1) + x + (x-1 + ... + 2 + 1)

This simplifies to:

x²

For example, if:

x = 3

the pyramid is:

1 2 3 2 1

Its sum is:

1 + 2 + 3 + 2 + 1 = 9

And:

3² = 9

Therefore, once we know the maximum peak height, we can calculate the maximum amount of height that can be retained as:

peak * peak

Java Implementation

class Solution {
    public int formPyramid(int[] arr) {
        int n = arr.length;

        int[] left = new int[n];
        int[] right = new int[n];

        // Calculate maximum possible height from the left
        left[0] = 1;

        for (int i = 1; i < n; i++) {
            left[i] = Math.min(arr[i], left[i - 1] + 1);
        }

        // Calculate maximum possible height from the right
        right[n - 1] = 1;

        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.min(arr[i], right[i + 1] + 1);
        }

        // Find the maximum pyramid that can be formed
        long maxPyramidSum = 0;

        for (int i = 0; i < n; i++) {
            int peak = Math.min(left[i], right[i]);

            long pyramidSum = (long) peak * peak;

            maxPyramidSum = Math.max(maxPyramidSum, pyramidSum);
        }

        // Calculate total height of the original array
        long totalSum = 0;

        for (int height : arr) {
            totalSum += height;
        }

        // Required reduction cost
        return (int) (totalSum - maxPyramidSum);
    }
}

Code Explanation

Step 1: Create DP Arrays

int[] left = new int[n];
int[] right = new int[n];

We use two arrays:

left[] → constraints from the left
right[] → constraints from the right

Step 2: Calculate `left[]`

left[0] = 1;

for (int i = 1; i < n; i++) {
    left[i] = Math.min(arr[i], left[i - 1] + 1);
}

At every position, the height cannot be greater than:

previous height + 1

and it also cannot be greater than the original stone height.

Hence:

left[i] = min(arr[i], left[i - 1] + 1)

Step 3: Calculate `right[]`

right[n - 1] = 1;

for (int i = n - 2; i >= 0; i--) {
    right[i] = Math.min(arr[i], right[i + 1] + 1);
}

This performs the same calculation from the right side.

It ensures that the pyramid can decrease by exactly 1 as we move away from the peak.

Step 4: Find the Maximum Peak

int peak = Math.min(left[i], right[i]);

A position can be a pyramid peak only if both sides can support that height.

Therefore, we take the smaller value.

For example:

left[i]  = 4
right[i] = 3

The peak can only be:

min(4, 3) = 3

Step 5: Calculate Pyramid Sum

long pyramidSum = (long) peak * peak;

A pyramid with peak x has total height:

x²

So there is no need to explicitly construct the pyramid.

Step 6: Calculate Original Sum

long totalSum = 0;

for (int height : arr) {
    totalSum += height;
}

This gives the total height of all stones before performing any reductions.

Step 7: Calculate Minimum Cost

return (int) (totalSum - maxPyramidSum);

The stones that remain in the final pyramid are not reduced.

Everything else must be removed or reduced.

Therefore:

Minimum Cost
= Original Total Height
  - Maximum Pyramid Height

Dry Run

Consider:

arr = [1, 2, 3, 4, 2, 1]

Left DP

left[0] = 1

left[1] = min(2, 1 + 1) = 2
left[2] = min(3, 2 + 1) = 3
left[3] = min(4, 3 + 1) = 4
left[4] = min(2, 4 + 1) = 2
left[5] = min(1, 2 + 1) = 1

Therefore:

left = [1, 2, 3, 4, 2, 1]

Right DP

right[5] = 1

right[4] = min(2, 1 + 1) = 2
right[3] = min(4, 2 + 1) = 3
right[2] = min(3, 3 + 1) = 3
right[1] = min(2, 3 + 1) = 2
right[0] = min(1, 2 + 1) = 1

Therefore:

right = [1, 2, 3, 3, 2, 1]

Possible Peaks

min(left[i], right[i])

gives:

[1, 2, 3, 3, 2, 1]

Maximum peak:

Maximum pyramid sum:

3 × 3 = 9

Original array sum:

1 + 2 + 3 + 4 + 2 + 1 = 13

Therefore:

Minimum Cost = 13 - 9
             = 4

Why Does This Work?

The important observation is that the final pyramid must increase by 1 until the peak and decrease by 1 after the peak.

The left[] array tells us how high the pyramid can grow from the left.

The right[] array tells us how high it can grow from the right.

Taking:

min(left[i], right[i])

ensures that both sides of the pyramid are valid.

Among all possible peaks, choosing the largest peak retains the maximum total stone height. Since the only operation allowed is reduction, retaining the maximum possible height gives the minimum reduction cost.

Complexity Analysis

Time Complexity

We perform three linear passes:

O(n) + O(n) + O(n)

Therefore:

O(n)

Auxiliary Space

We use two arrays of size n:

left[n]
right[n]

Therefore:

O(n)

Edge Cases

Already a pyramid

arr = [1, 2, 1]

The maximum pyramid is the entire array.

Original sum = 4
Pyramid sum  = 4
Answer       = 0

Single element

arr = [5]

The valid pyramid can only have height 1:

[1]

Therefore:

Cost = 5 - 1 = 4

Large values

Since arr[i] can be up to 10^5, using long for the sum calculations is safer than using int.

Conclusion

The main trick in this problem is to avoid trying every possible pyramid explicitly.

Using two DP arrays:

left[i]
right[i]

we can determine the maximum possible peak at every position:

peak = min(left[i], right[i])

A pyramid with peak x has a total height of:

x²

Finally:

Minimum Reduction Cost
= Total Array Sum - Maximum Pyramid Sum

This gives an efficient O(n) time and O(n) space solution.

Problem Statement

Example

1. left[i]

2. right[i]

Step 1: Create DP Arrays

Step 2: Calculate left[]

Step 3: Calculate right[]

Step 4: Find the Maximum Peak

Step 5: Calculate Pyramid Sum

Step 6: Calculate Original Sum

Step 7: Calculate Minimum Cost

Left DP

Right DP

Possible Peaks

Time Complexity

Auxiliary Space

Already a pyramid

Single element

Large values

1. `left[i]`

2. `right[i]`

Step 2: Calculate `left[]`

Step 3: Calculate `right[]`