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.
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]; }}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.