Pyramid Array with Reduce Operations

Problem Overview

You may only decrease stone heights.

Intuition

You may only decrease stone heights. A pyramid of height h uses the stones 1, 2, ..., h, ..., 2, 1, which sum to h times h. Paying for every removed unit is the same as maximizing the stones you keep, so the cheapest pyramid is the tallest one the row can support.

Algorithm

1Scan from the right. The tallest rise ending at i is min(arr[i], the next rise plus 1), and the last cell is at most 1.
2Scan from the left with a running height that follows the same rule.
3At each index the feasible peak is the minimum of the left height and the right height.
4Track the maximum of peak times peak while summing the original array.
5Return the array sum minus that maximum kept sum.

Example Walkthrough

Input: arr = [1, 5, 1]

1. The middle can rise to 2 from both sides, and the ends stay at 1.
2. A height-2 pyramid keeps 4 stones.
3. The original sum is 7, so 3 units are reduced.

Output: 3

Common Pitfalls

• Heights can only decrease, never increase past arr[i].
• A peak of height h needs h cells on each side, counting the peak once, which the plus-one growth already enforces.
• The kept sum of a valid pyramid is h times h, not the triangular number h(h+1)/2.
• Use 64-bit arithmetic for the array sum and for h times h.

Pyramid Array with Reduce Operations.java

Java

// Approach: A pyramid of height h keeps h*h stones, since
// 1+2+...+h+...+2+1 = h*h. Only decreases are allowed, so the cheapest
// pyramid is the tallest feasible one. Scan right to left for the tallest
// rise that suffix allows, then left to right with a running height, and
// take the min at each index as a candidate peak.
// Complexity: O(n) time, O(n) extra space.
class Solution {
    public int formPyramid(int[] arr) {
        int n = arr.length;
        long[] fromRight = new long[n];
        fromRight[n - 1] = Math.min(arr[n - 1], 1);
        for (int i = n - 2; i >= 0; i--)
            fromRight[i] = Math.min((long) arr[i], fromRight[i + 1] + 1);

        long total = 0;
        long left = 0;
        long maxKept = 0;
        for (int i = 0; i < n; i++) {
            total += arr[i];
            left = i == 0 ? Math.min(arr[0], 1) : Math.min((long) arr[i], left + 1);
            long height = Math.min(left, fromRight[i]);
            maxKept = Math.max(maxKept, height * height);
        }

        return (int) (total - maxKept);
    }
}

Was this solution helpful?