Minimum Cost to Merge Stones

Hard
1503.

Minimum Cost to Merge Stones

Minimum Cost to Merge Stones is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google and Microsoft interviews.

There are n piles of stones in a row, and pile i holds stones[i] stones.

A move merges exactly k consecutive piles into a single pile, and it costs the total number of stones in those k piles. The new pile takes their place in the row.

Return the minimum total cost to merge all the piles into one pile, or -1 if that is impossible.

Example 1

Input
stones = [6,2,5,1], k = 2
Output
28
Explanation
Merge `[6,2]` (cost 8) and `[5,1]` (cost 6), then `[8,6]` (cost 14): 28 in total.

Example 2

Input
stones = [6,2,5,1], k = 3
Output
-1
Explanation
Each move removes exactly 2 piles, so 4 piles can only become 2, never 1.

Example 3

Input
stones = [2,6,1,3,5], k = 3
Output
26
Explanation
Merge `[2,6,1]` (cost 9) to get `[9,3,5]`, then merge everything (cost 17).

Constraints

  • n == stones.length
  • 1 <= n <= 30
  • 1 <= stones[i] <= 100
  • 2 <= k <= 30
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} stones
 * @param {number} k
 * @return {number}
 */
var mergeStones = function(stones, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost to Merge Stones — Problem & Solution

Minimum Cost to Merge Stones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Cost to Merge Stones is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google and Microsoft interviews.

Problem statement

There are n piles of stones in a row, and pile i holds stones[i] stones.

A move merges exactly k consecutive piles into a single pile, and it costs the total number of stones in those k piles. The new pile takes their place in the row.

Return the minimum total cost to merge all the piles into one pile, or -1 if that is impossible.

Example 1

Input: stones = [6,2,5,1], k = 2
Output: 28
Explanation: Merge `[6,2]` (cost 8) and `[5,1]` (cost 6), then `[8,6]` (cost 14): 28 in total.

Example 2

Input: stones = [6,2,5,1], k = 3
Output: -1
Explanation: Each move removes exactly 2 piles, so 4 piles can only become 2, never 1.

Example 3

Input: stones = [2,6,1,3,5], k = 3
Output: 26
Explanation: Merge `[2,6,1]` (cost 9) to get `[9,3,5]`, then merge everything (cost 17).

Constraints

  • n == stones.length
  • 1 <= n <= 30
  • 1 <= stones[i] <= 100
  • 2 <= k <= 30

Hints for Minimum Cost to Merge Stones

  1. Hint 1

    Each move reduces the number of piles by k - 1. When can n piles end as one?

  2. Hint 2

    Let dp[i][j] be the cheapest way to merge stones[i..j] into as few piles as possible. The leftmost of those piles comes from some prefix stones[i..mid] that was merged all the way down to one pile.

  3. Hint 3

    Only prefixes with mid - i a multiple of k - 1 can become a single pile, so step mid by k - 1: dp[i][j] = min(dp[i][mid] + dp[mid+1][j]). When (j - i) is itself a multiple of k - 1, the range can finish as one pile — add its stone total.

How to solve Minimum Cost to Merge Stones

Every move turns k piles into one, removing k - 1, so n piles become one exactly when (n - 1) % (k - 1) == 0. More generally a range of length L can be reduced to (L - 1) % (k - 1) + 1 piles and no fewer. An interval DP over ranges, splitting off the leftmost final pile, captures every merge order.

Approach

  1. If (n - 1) % (k - 1) != 0, return -1.
  2. Build prefix sums so any range total is O(1).
  3. dp[i][i] = 0. For lengths 2 to n and every start i (end j): dp[i][j] = min over mid = i, i + (k-1), i + 2(k-1), … < j of dp[i][mid] + dp[mid+1][j].
  4. If (j - i) % (k - 1) == 0, the range's piles can be merged one final time into one pile: add sum(i..j) to dp[i][j].
  5. Return dp[0][n - 1].

Why it works

Look at the minimal pile configuration of stones[i..j]: its leftmost pile came from some prefix stones[i..mid] merged into one pile, which is only possible when mid - i is a multiple of k - 1 — hence the step. The rest of the range is handled independently, because merges never cross the boundary between the leftmost pile's stones and the others before that final step. When the whole range reduces to exactly k piles, one more merge costs precisely the range total, whatever order came before — so adding sum(i..j) at those lengths accounts for the last merge.

Complexity

  • Time — O(n^3 / (k - 1))
  • Space — O(n^2)

Pitfalls

  • Check feasibility first — without it the DP happily returns a cost for a row that can never become one pile.
  • Step the split point by k - 1, not by 1; other split points describe prefixes that cannot be a single pile.
  • Add the range sum only when (len - 1) % (k - 1) == 0; adding it elsewhere charges merges that never happen.

Reference solution

Python

from typing import List

def mergeStones(stones: List[int], k: int) -> int:
    n = len(stones)
    if (n - 1) % (k - 1) != 0:
        return -1
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + stones[i]
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            best = 10 ** 18
            for mid in range(i, j, k - 1):
                cand = dp[i][mid] + dp[mid + 1][j]
                if cand < best:
                    best = cand
            if (length - 1) % (k - 1) == 0:
                best += pre[j + 1] - pre[i]
            dp[i][j] = best
    return dp[0][n - 1]

Java

public static int mergeStones(int[] stones, int k) {
    int n = stones.length;
    if ((n - 1) % (k - 1) != 0) return -1;
    int[] pre = new int[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
    int[][] dp = new int[n][n];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            int best = Integer.MAX_VALUE;
            for (int mid = i; mid < j; mid += k - 1) best = Math.min(best, dp[i][mid] + dp[mid + 1][j]);
            if ((len - 1) % (k - 1) == 0) best += pre[j + 1] - pre[i];
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
}

C++

int mergeStones(vector<int>& stones, int k) {
    int n = stones.size();
    if ((n - 1) % (k - 1) != 0) return -1;
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            int best = INT_MAX;
            for (int mid = i; mid < j; mid += k - 1) best = min(best, dp[i][mid] + dp[mid + 1][j]);
            if ((len - 1) % (k - 1) == 0) best += pre[j + 1] - pre[i];
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
}

JavaScript

var mergeStones = function(stones, k) {
    var n = stones.length;
    if ((n - 1) % (k - 1) !== 0) return -1;
    var pre = new Array(n + 1).fill(0);
    for (var i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
    var dp = [];
    for (var i = 0; i < n; i++) dp.push(new Array(n).fill(0));
    for (var len = 2; len <= n; len++) {
        for (var i = 0; i + len <= n; i++) {
            var j = i + len - 1, best = Infinity;
            for (var mid = i; mid < j; mid += k - 1) {
                best = Math.min(best, dp[i][mid] + dp[mid + 1][j]);
            }
            if ((len - 1) % (k - 1) === 0) best += pre[j + 1] - pre[i];
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming