Watch 10 video solutions for Maximum Value of K Coins From Piles, a hard level problem involving Array, Dynamic Programming, Prefix Sum. This walkthrough by NeetCodeIO has 11,970 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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) <= 2000Problem Overview: You are given several piles of coins where each pile is stacked vertically. You can only take coins from the top of a pile. The goal is to pick exactly k coins across all piles while maximizing the total value.
Approach 1: Greedy Selection with Heap (O(k log n) time, O(n) space)
A straightforward idea is to always take the next best visible coin. Push the top coin from each pile into a max heap and repeatedly extract the largest value until k coins are chosen. After taking a coin from a pile, push the next coin from that same pile into the heap. This approach uses a priority queue to greedily maximize immediate gain. However, it does not always produce the optimal result because taking a slightly smaller coin early might unlock larger coins deeper in the same pile.
Approach 2: Dynamic Programming with Prefix Sums (O(n * k * m) time, O(k) space)
The optimal strategy treats the problem like a grouped knapsack. For each pile, you can take 0..m coins from the top, but they must be taken in order. First compute prefix sums for each pile so that the value of taking the first x coins can be retrieved in constant time. Then use dp[j] to represent the maximum value achievable by taking j coins so far.
Iterate through each pile and update the DP array from right to left. For every possible coin count j, try taking x coins from the current pile and combine it with the previous state dp[j - x]. This explores every valid distribution of picks across piles while avoiding recomputation. Prefix sums eliminate repeated summations, making transitions efficient.
This technique is a classic combination of dynamic programming and prefix sum optimization applied to grouped choices. The piles themselves are stored in an array, and each pile contributes multiple candidate transitions.
Recommended for interviews: The dynamic programming approach is the expected solution. It demonstrates the ability to model constrained selections similar to knapsack problems. Greedy reasoning helps build intuition, but only the DP formulation guarantees the optimal result for all inputs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Heap Selection | O(k log n) | O(n) | Quick heuristic when piles are shallow or when approximate greedy behavior is acceptable |
| Dynamic Programming + Prefix Sums | O(n * k * m) | O(k) | General case. Guarantees optimal value when selecting exactly k coins across piles |