Merge Stones Problem

I decided to try out this Leetcode problem: https://leetcode.com/problems/minimum-cost-to-merge-stones/

Unfortunately, I’m not sure how to approach this problem where one of my solutions would be correct. The implementation I decided to write my code involves the sliding window approach to find the local minimum cost, then perform the merge and repeat.

However, the code fails in one of the test cases:
Input - [6, 4, 4, 6]
My Output - 42
Expected Output - 40

What framework will I be learning in one of the software workshops that covers this problem? I see this as a greedy algorithm problem, as it’s looking for an optimal solution.

P.S. In preparing for my on-site interview day with Amazon, which I wasn’t reached out yet on when mine is taking place, I’m wondering if I should start out with easy and less frequent questions first before I build up and try out questions that are the most frequent over the past six months. Problem is, that doesn’t give me a lot of time to learn and practice some patterns I’ll need for those arbitrary problems I’ll be asked in the interviews.

I’d say it’s probably a DP problem. The greedy approach won’t work as you’ve outlined in your example. The DP framework workshop that Pathrise has, goes over that approach. That being said, DP problem are notorious for being subtle in their implementation. They take practice(lots of it), as well as intuition to come up with the recurrence relations, and the insight to identify the duplicate work being done in the recursive solution.

If you’re just starting, here is something I can suggest :muscle: :

  1. Realize the greedy approach doesn’t work (your example accomplishes this) :100: .
  2. Perhaps start by identifying this as a recursive problem. You can make all the groups of K stones each time, and see if that works. That’s a brute force solution. In this case, since the constraints of the problem are small :
1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

This hints that an exponential solution with some modification, might work (if it’s in an interview, asking the constraints would be a good clarifying question here, as it also doubles up as a hint to the approach you can take. In general, lower constraints => exponential solutions, with some modifications.) EDIT: lower constraints => quadratic/cubic solutions are more likely.

NOTE: Let me take this opportunity to mention that there isn’t always a sure fire way to come at the right approach instantly. A lot of it just comes from practice and awareness of the problems you’ve already solved. DP solutions in particular are some of the trickiest to arrive at :bomb: !! Plus it’s a LC Hard :space_invader:problem, so building up to it would be beneficial, i.e. starting from Medium, but that’s just my opinion, and differs in every individual case :busts_in_silhouette::world_map:.

When I first looked at the problem (and the constraints), I started with the recursive solution. It worked for the smaller test cases, but not on the large ones, since right now it has around ~O(nCk) complexity :face_with_monocle:.

Here’s my recursive solution, it’s the first iteration, so I haven’t polished it so bear with me. :bear:

class Solution:
    
    def __init__(self):
        self.min_count = float('inf')
    
    def mergeStones(self, stones: List[int], K: int) -> int:
        """
        For each location, we have the option of starting a pile at that location.
        """
        
        if len(stones)<K:
            return 0
        
        for i in range(len(stones)-K+1):
            self.rec(stones, i, K,0)
        
        return self.min_count if self.min_count!=float('inf') else -1
        
    def rec(self, stones, start, K, cur_cost):
        # print(stones)
        if len(stones)==K:
            cur_cost+=sum(stones)
            self.min_count = min(self.min_count, cur_cost)
            return
        
        if len(stones)<K: # can't make combination
            return
        
#       combine step
#       not recommended because slicing is slow
        prev = stones[:start]
        next = stones[start+K:]
        merged = sum(stones[start:start+K])
        
        stones = prev+[merged]+next
        
        for i in range(len(stones)-K+1): # loop through all possible start positions
            self.rec(stones, i, K,cur_cost+merged)
        
        return
        

Now that I know i’m doing duplicate work (you should try to see how!), i’ll try to come up with the DP solution. (wish me luck! :japanese_ogre:)
Posted this solution, cause I wanted to walk you through my thought process.

1 Like

No one wished me luck :sob: just kidding (am i though :thinking:). On a more serious note, the DP approach was really interesting! I definitely needed some inspiration for this approach(LC Discuss FTW :trophy: ). The key insight :face_with_monocle: for me was the constraint that the length of an array should satisfy:

(n-1)%(k-1)==0

Illustration at the end to showcase this point.
Although it seems straight forward, it helps us memoize information later pretty well!(once we’ve broken down our problem into smaller sub-problems).

Then we split our larger array into smaller pieces, which satisfy this constraint, and in our DP matrix store the min_cost for a subarray from i to j. dp[i][j] = min_cost to combine subarray from i to j.

Here is my final solution:

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        """
        Using dp

        dp[i][j] = state, min_cost to combine stones from index i to j(inclusive)

        dp[i][j] = min(dp[i][temp]+dp[temp+1][j] for temp in range(i,j, K-1))
        so temp = i, i+(K-1), i+2*(K-1)...., because we know adding (K-1) to a pile(of min size 1) will result in a combinable length of stones.

        """

        if K>2 and len(stones)%(K-1)!=1:    # every combine, reduces len by K-1, leaving 1 element at the end, special case for K=2, which can always combine
            return -1

        cum_sum = [0]*(len(stones)+1)    # array to store cumulative sum. Will help us to find sum of array from i to j index. Need to start with 0 to take care of base cases later.

        my_dict = {}

        for i in range(len(stones)):
            cum_sum[i+1] = cum_sum[i]+stones[i]

        return self.dp_helper(0, len(stones)-1, K, stones, cum_sum, my_dict)

    def dp_helper(self, start, end, K, stones, cum_sum,my_dict):
        if end-start+1<K:
            return 0

        if (start,end) in my_dict: # if we've already calculated the min_cost for this range.
            return my_dict[(start,end)]

        # Sorry, about the extended parameter list, you can just nest the helper function. I prefer having it separate (for some reason :shrug:).
        # Essentially res = min(self.dp(start,temp)+self.dp(temp+1,end) for temp in range(i,j,K-1))
        # Minimum of all combinations of left + right.
        res = min(self.dp_helper(start, temp, K, stones, cum_sum, my_dict) + self.dp_helper(temp+1, end, K, stones, cum_sum, my_dict) for temp in range(start, end, K-1))
        # Splitting start-end range into various [prefix(start-temp)][suffix(temp+1,end)], and calculating min sum for each smaller range, and storing it in map later.

        if (K>2 and (end-start+1)%(K-1)==1) or K-1==1:  # basically (end-start)%(K-1)==0
            res+= cum_sum[end+1]-cum_sum[start]

        my_dict[(start, end)] = res
        return res

Some illustrations to drive the point home:


Hope that helps. Thanks for the question!! :100: :trophy:

4 Likes

Thank you for sharing, Chaitanya. This is definitely a lot tougher than I thought it would be, and I feel like a dynamic programming approach requires a lot more time than greedy algorithms. No wonder I don’t like the approach to coming up with DP solutions from recursion that much right now.

I hope Derrick’s workshop on dynamic programming in a few weeks will introduce me to some concepts that’ll help me a lot. In a technical interview, I won’t have a lot of time to analyze my recursive approach to find duplicate steps.

As a data point, this is a question that has come up at Google multiple times earlier this year, often in variations involving candy instead of stones. And @1ndie’s solution here is amazing!

2 Likes

For now, @michael.mroczka shared me a couple of links I’m going through to get a lot more exposure to recursion. I must admit, though, I don’t particularly like the amount of work that’s involved towards dynamic programming because some problems would take far too long for me to identify redundant work that recursion creates and how to simplify it with only arithmetic / string / array manipulation statements to stop previous work from overlapping.