Maximum Value of K Coins From Piles
HardPrompt
There are n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.
In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.
Given a list piles, where piles[i] is a list of integers denoting the composition of the ith pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.
Example 1:
Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.Example 2:
Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation:
The maximum total can be obtained if we choose all coins from the last pile.
Constraints:
n == piles.length1 <= n <= 10001 <= piles[i][j] <= 1051 <= k <= sum(piles[i].length) <= 2000
Approaches
3 approaches with complexity analysis and trade-offs.
This problem can be modeled as a variation of the knapsack problem. We need to make a sequence of choices: for each pile, how many coins to take? The goal is to maximize the total value for exactly k coins. This structure is perfect for dynamic programming. A natural way to approach this is using recursion with memoization (a top-down DP approach). We can define a recursive function solve(i, k) that computes the maximum value we can get by picking k coins from piles i to n-1.
Algorithm
- Define a recursive function, let's call it
solve(i, k), which will compute the maximum value obtainable from pilesiton-1given that we still need to pickkcoins. - Base Cases:
- If
ireachesn(all piles considered) orkbecomes 0 (no more coins can be picked), we can't gain any more value, so we return 0.
- If
- Memoization: To avoid recomputing results for the same state
(i, k), we use a 2D arraymemo[n][k+1]. Before any computation, we check ifmemo[i][k]has already been computed. If so, we return the stored value. - Recursive Step: For the current pile
i, we explore all possibilities of how many coins to take from it.- First, consider taking 0 coins from pile
i. The value would besolve(i + 1, k). - Then, iterate through taking
xcoins from pilei, wherexgoes from 1 up tomin(k, piles.get(i).size()). - For each
x, calculate the sum of the topxcoins. The total value for this choice is(sum of top x coins) + solve(i + 1, k - x). - The result for
solve(i, k)is the maximum value among all these possibilities.
- First, consider taking 0 coins from pile
- Store the computed result in
memo[i][k]before returning.
Walkthrough
The state of our recursion is (i, k), where i is the index of the current pile we are considering, and k is the number of coins we still need to pick. The function solve(i, k) will return the maximum value obtainable from piles i onwards, given we need to pick k more coins. To avoid recomputing the same subproblems, we use a 2D array memo[i][k] for memoization. To efficiently get the sum of the top x coins, we can calculate it iteratively within the recursive function.
import java.util.List;import java.util.Arrays; class Solution { private List<List<Integer>> piles; private int[][] memo; private int n; public int maxValueOfCoins(List<List<Integer>> piles, int k) { this.n = piles.size(); this.piles = piles; this.memo = new int[n][k + 1]; for (int[] row : memo) { Arrays.fill(row, -1); } return solve(0, k); } private int solve(int i, int k) { if (i == n || k == 0) { return 0; } if (memo[i][k] != -1) { return memo[i][k]; } // Option 1: Take 0 coins from the current pile int res = solve(i + 1, k); // Option 2: Take 1, 2, ... coins from the current pile int currentSum = 0; for (int j = 0; j < Math.min(piles.get(i).size(), k); j++) { currentSum += piles.get(i).get(j); res = Math.max(res, currentSum + solve(i + 1, k - (j + 1))); } return memo[i][k] = res; }}Complexity
Time
O(k * sum(piles[i].length)). There are `n * k` possible states for `(i, k)`. For each state, we iterate up to `piles[i].size()` times. The total complexity is the sum of `k * piles[i].size()` over all `i`, which simplifies to `O(k * sum(piles[i].length))`. Given the constraints, this is feasible.
Space
O(n * k) for the memoization table `memo`. The recursion depth can go up to `n`, so there's also O(n) space for the call stack.
Trade-offs
Pros
Intuitive to derive from the problem's recursive nature.
Directly translates the problem's logic into code.
Cons
Can be slightly slower than iterative solutions due to function call overhead.
Space complexity of O(n*k) is not optimal for this problem.
This approach is an iterative version of the recursive solution, often called tabulation. It systematically builds up the solution from the smallest subproblems, which can be more efficient and avoids recursion limits. We use a 2D DP table, dp[i][j], to store the maximum value obtainable by picking exactly j coins from the first i piles.
Algorithm
- Define a 2D DP table
dp[n+1][k+1], wheredp[i][j]stores the maximum value obtainable by picking exactlyjcoins from the firstipiles. - Initialize the table with zeros.
dp[0][j] = 0anddp[i][0] = 0are the base cases, meaning 0 value if we have no piles or need to pick 0 coins. - Iterate through each pile
ifrom 1 ton. - For each pile, iterate through the number of coins
jfrom 1 tok. - To calculate
dp[i][j], we consider the(i-1)-th pile. We can takexcoins from this pile andj-xcoins from the previousi-1piles. The value from the previousi-1piles is already computed asdp[i-1][j-x]. - The transition formula is:
dp[i][j] = max(dp[i-1][j-x] + sum_of_top_x_coins_from_pile_(i-1))wherexranges from 0 tomin(j, piles[i-1].size()). - The
x=0case (taking no coins from the current pile) meansdp[i][j]can be initialized todp[i-1][j]. Then we iteratexfrom 1 upwards to consider taking coins. - The final answer is the value in
dp[n][k].
Walkthrough
We define dp[i][j] as the maximum value using j coins from piles 0 to i-1. The table size will be (n+1) x (k+1). We iterate through each pile and each possible number of total coins, and for each (i, j) pair, we decide how many coins x to take from the current pile i-1. The value is the sum of top x coins plus the value we got from previous i-1 piles with j-x coins, which is dp[i-1][j-x].
import java.util.List; class Solution { public int maxValueOfCoins(List<List<Integer>> piles, int k) { int n = piles.size(); int[][] dp = new int[n + 1][k + 1]; for (int i = 1; i <= n; i++) { List<Integer> currentPile = piles.get(i - 1); for (int j = 0; j <= k; j++) { // Option 1: Take 0 coins from the current pile dp[i][j] = dp[i - 1][j]; int currentSum = 0; // Option 2: Take x > 0 coins from the current pile for (int x = 1; x <= Math.min(currentPile.size(), j); x++) { currentSum += currentPile.get(x - 1); dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - x] + currentSum); } } } return dp[n][k]; }}Complexity
Time
O(k * sum(piles[i].length)). We have three nested loops. The outer loop runs `n` times, the middle loop `k` times, and the inner loop `piles[i-1].size()` times. The total complexity is `sum_{i=1 to n} (k * piles[i-1].size())`, which is `O(k * sum(piles[i].length))`.
Space
O(n * k) to store the DP table.
Trade-offs
Pros
Avoids recursion overhead and potential stack overflow issues.
Often slightly faster in practice than the memoized version due to better memory locality.
Cons
The space complexity of O(n*k) can be large and is not optimal for this problem.
We can optimize the space complexity of the bottom-up DP approach. Notice that to compute the values for the current pile i (i.e., dp[i][...]), we only need the values from the immediately preceding pile i-1 (i.e., dp[i-1][...]). This dependency allows us to reduce the space complexity from O(n*k) to O(k). We can use a single 1D array dp[j] to represent the maximum value achievable with j coins using the piles considered so far.
Algorithm
- Initialize a 1D DP array
dpof sizek+1with all zeros.dp[j]will store the maximum value achievable withjcoins. - Iterate through each
pilein the inputpiles. - For each pile, we want to update the
dparray. To do this correctly, we iterate the number of coinsjfromkdown to 1. This backward iteration is crucial to ensure that when we calculate a newdp[j], we are usingdpvalues from the state before considering the current pile. - Inside this loop, we iterate through the number of coins
xto take from the current pile, from 1 up tomin(j, pile.size()). - Calculate the
currentSumof the topxcoins from the current pile. - Update
dp[j]with the maximum of its current value and the value from takingxcoins from this pile:dp[j] = max(dp[j], dp[j-x] + currentSum). - After iterating through all piles,
dp[k]will hold the maximum value for exactlykcoins.
Walkthrough
Let dp[j] be the maximum value we can obtain by picking j coins from the piles considered so far. We iterate through each pile and update this dp array. When considering a new pile, we update dp[j] by potentially taking x coins from this new pile. This requires the value for j-x coins from the previous piles, which is dp[j-x] (from the previous state). By iterating j from k down to 1, we ensure dp[j-x] holds the value from the previous iteration (before processing the current pile), thus correctly modeling the choice.
import java.util.List; class Solution { public int maxValueOfCoins(List<List<Integer>> piles, int k) { int[] dp = new int[k + 1]; for (List<Integer> pile : piles) { // Iterate downwards to use dp values from the previous state (before this pile) for (int j = k; j >= 1; j--) { int currentSum = 0; for (int x = 1; x <= Math.min(pile.size(), j); x++) { currentSum += pile.get(x - 1); dp[j] = Math.max(dp[j], dp[j - x] + currentSum); } } } return dp[k]; }}Complexity
Time
O(k * sum(piles[i].length)). The time complexity remains the same as the previous approaches because the loop structure is fundamentally the same.
Space
O(k). We only need a 1D array of size `k+1`. This is a significant improvement over the previous approaches.
Trade-offs
Pros
Optimal space complexity of O(k).
Maintains the same time efficiency as less space-efficient methods.
Cons
The logic of iterating backwards can be less intuitive for beginners compared to the 2D DP approach.
Solutions
Solution
class Solution {public int maxValueOfCoins(List<List<Integer>> piles, int k) { int n = piles.size(); List<int[]> presum = new ArrayList<>(); for (List<Integer> p : piles) { int m = p.size(); int[] s = new int[m + 1]; for (int i = 0; i < m; ++i) { s[i + 1] = s[i] + p.get(i); } presum.add(s); } int[] dp = new int[k + 1]; for (int[] s : presum) { for (int j = k; j >= 0; --j) { for (int idx = 0; idx < s.length; ++idx) { if (j >= idx) { dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]); } } } } return dp[k]; }}class Solution {public: int maxValueOfCoins(vector<vector<int>> &piles, int k) { vector<vector<int>> presum; for (auto &p : piles) { int m = p.size(); vector<int> s(m + 1); for (int i = 0; i < m; ++i) s[i + 1] = s[i] + p[i]; presum.push_back(s); } vector<int> dp(k + 1); for (auto &s : presum) { for (int j = k; ~j; --j) { for (int idx = 0; idx < s.size(); ++idx) { if (j >= idx) dp[j] = max(dp[j], dp[j - idx] + s[idx]); } } } return dp[k]; }};class Solution: def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int: presum = [list(accumulate(p, initial=0)) for p in piles] n = len(piles) dp = [[0] * (k + 1) for _ in range(n + 1)] for i, s in enumerate(presum, 1): for j in range(k + 1): for idx, v in enumerate(s): if j >= idx: dp[i][j] = max(dp[i][j], dp[i - 1][j - idx] + v) return dp[- 1][- 1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.