We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Merge Stones

Number: 1042

Difficulty: Hard

Paid? No

Companies: Google, Amazon

Problem Description

Given n piles of stones arranged in a row where the i-th pile has stones[i] stones, a move consists of merging exactly k consecutive piles into one, and the cost to do so is the sum of the stones in these k piles. The goal is to merge all piles into a single pile with minimum cost; if it is impossible, return -1.

Key Insights

  • You can only merge stones into one final pile if (n - 1) is divisible by (k - 1). If not, return -1.
  • A dynamic programming approach is used where dp[i][j] represents the minimum cost to merge the subarray stones[i...j] into as few piles as possible.
  • A prefix sum array is precomputed to quickly calculate the sum of stones in any subarray.
  • When a segment can be merged into one pile (i.e. when (length - 1) % (k - 1) == 0), add the sum of stones in that segment to the dp value.

Space and Time Complexity

Time Complexity: O(n^3) due to the triple nested loop over segments and splits. Space Complexity: O(n^2) from the dp table and O(n) for the prefix sum array.

Solution

The problem is solved using a range DP approach. We first verify that merging all piles into one is feasible by checking if (n - 1) % (k - 1) == 0. Next, a prefix sum array is computed to optimize range sum calculations. A 2D dp table dp[i][j] is then used to store the minimum cost to merge stones[i...j]. For each interval, we consider valid split points, updating dp[i][j] by combining sub-problems. If the current segment can form a single merged pile (determined by the condition on the interval length), the cost of merging that segment (the sum of stones) is added to dp[i][j].

Code Solutions

# Python solution for merging stones with detailed comments.
class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        # Check for merge feasibility.
        if (n - 1) % (k - 1) != 0:
            return -1
        
        # Precompute prefix sums for fast range sum queries.
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]
        
        # Initialize dp table, dp[i][j] represents minimal cost to merge stones[i...j].
        dp = [[0] * n for _ in range(n)]
        
        # Process all possible subarrays with lengths >= k.
        for length in range(k, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = float('inf')
                # Try all valid partitions with step size (k-1).
                for mid in range(i, j, k - 1):
                    dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid+1][j])
                # If this segment can be merged into one pile, add cost.
                if (length - 1) % (k - 1) == 0:
                    dp[i][j] += prefix[j+1] - prefix[i]
        return dp[0][n-1]

# Example usage:
# solution = Solution()
# print(solution.mergeStones([3, 2, 4, 1], 2))  # Expected output: 20
← Back to All Questions