LeetCode - Last Stone Weight II
https://leetcode.com/problems/last-stone-weight-ii/
Problem
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
- If x == y, both stones are destroyed, and
- If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
Solution
You can convert this problem into knapsack problem: splitting the given array into 2 parts which the sum diff of two parts is minimum. The sum diff is the result of this problem.
Why? I was struggled while proving this. Well, i will put a really good mathematic proof (which i stealed from leetcode). It took me around 30m to understand this… I’m old :<
1 | Given stones {x_1, ..., x_k} |
TL;DR: No, read it please, it’s a really cool induction math :))
So, how we solve the knapsack problem? We need to know, which sum we can build by using some stones in given stones.
Let define f[i] = true if we can build sum i. For each stone, we will need to update the f array. It’s clearly that we can build sum i+stone if we can build sum i.
In the below code, i made a twist of the second loop (len(f)-1 -> 0) to avoid using duplicated stone.
1 | func lastStoneWeightII(stones []int) int { |
There is an optimization i made in the code: The f array has 1500 elements which is equal MAX_STONES * MAX_WEIGHT / 2. Why /2? Well, the smallerSum is less than or equal sum/2.
The time complexity is O(N*MAX_WEIGHT) and memory complexity is O(MAX_WEIGHT)
Support me via: https://ko-fi.com/iamquang95