Minimum Cost to Merge Stones - Practice Coding Problems

Minimum Cost to Merge Stones - Problem

There are n piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.

Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Input & Output

Example 1 — Basic Case

$ Input: stones = [3,2,4,1], k = 2

› Output: 20

💡 Note: Merge [3,2] for cost 5 → [5,4,1]. Merge [4,1] for cost 5 → [5,5]. Merge [5,5] for cost 10. Total: 5+5+10=20

Example 2 — Impossible Case

$ Input: stones = [3,2,4,1], k = 3

› Output: -1

💡 Note: Cannot merge 4 piles into 1 with k=3. Need (n-1) % (k-1) = 0, but (4-1) % (3-1) = 1 ≠ 0

Example 3 — Single Pile

$ Input: stones = [3,5,1,2,6], k = 3

› Output: 25

💡 Note: Merge [3,5,1] for cost 9 → [9,2,6]. Merge [9,2,6] for cost 17. Total: 9+17=26. Wait, optimal is different - need to find minimum path

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

stones = [3,2,4,1], k = 2

Merge Process

Find optimal sequence to merge k consecutive piles

Output

Minimum total cost = 20

Key Takeaway

🎯 Key Insight: Only possible when (n-1) % (k-1) == 0, use interval DP to find optimal merge sequence

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is that merging n piles into 1 pile is only possible when (n-1) % (k-1) == 0. Use interval dynamic programming with dp[i][j] representing minimum cost to merge stones[i..j] optimally. Best approach combines bottom-up DP with prefix sums. Time: O(n³), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(k^n)	O(n)	Try all possible ways to merge k consecutive piles recursively
Bottom-Up Dynamic Programming	O(n³)	O(n²)	Build solution iteratively using 2D DP table with prefix sums
Top-Down Dynamic Programming	O(n³ × k)	O(n² × k)	Use memoization to avoid recalculating the same subproblems

Recursive Backtracking — Algorithm Steps

Check if merging is mathematically possible
Try merging every group of k consecutive piles
Recursively solve for each resulting configuration
Return minimum cost among all valid paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with original piles

Try Merges

For each group of k consecutive piles, try merging

Recurse

Recursively solve for each resulting configuration

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int mergeCost(int* piles, int size, int k) {
    if (size == 1) {
        return 0;
    }
    if (size < k) {
        return INT_MAX;
    }
    
    int minCost = INT_MAX;
    for (int i = 0; i <= size - k; i++) {
        int cost = 0;
        for (int j = i; j < i + k; j++) {
            cost += piles[j];
        }
        
        int* newPiles = (int*)malloc((size - k + 1) * sizeof(int));
        int idx = 0;
        for (int j = 0; j < i; j++) {
            newPiles[idx++] = piles[j];
        }
        newPiles[idx++] = cost;
        for (int j = i + k; j < size; j++) {
            newPiles[idx++] = piles[j];
        }
        
        int nextCost = mergeCost(newPiles, size - k + 1, k);
        if (nextCost != INT_MAX && cost + nextCost < minCost) {
            minCost = cost + nextCost;
        }
        
        free(newPiles);
    }
    
    return minCost;
}

int solution(int* stones, int n, int k) {
    if ((n - 1) % (k - 1) != 0) {
        return -1;
    }
    
    return mergeCost(stones, n, k);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int stones[100];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            stones[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(stones, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

For each of n rounds, we try up to k positions to merge, leading to exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler