Maximum Value of K Coins From Piles - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Dynamic Programming Approach
This approach uses dynamic programming to find the maximum value of k coins from the given piles. We maintain a DP table where dp[i][j] represents the maximum value of coins we can obtain using the first i piles and j picks.
The main idea is to update this table by considering the top coin from the current pile, and deciding whether or not to pick it. We also keep track of cumulative sums for quicker reference.
The code defines a function maxValueOfCoins that initializes a DP table. The DP table is updated for each pile and each coin up to k using previously calculated results. The cumulative sum of coins for the current pile is used to efficiently update the table when considering picking certain coins from it.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n * k * m), where n is the number of piles, k is the number of coins to pick, and m is the average number of coins in each pile.
Space Complexity: O(n * k)
Approach 2: Greedy Approach
This approach involves greedy selection to achieve a near-optimal solution. The idea is to always select the coin with the highest value from a potential list of top coins from each pile, and repeat this k times.
This method might not guarantee the absolute optimal solution due to local-optimal greediness but can offer a reasonable approximation for certain constraints and datasets.
The solution uses a max-heap to store the possible top coins from each pile. We keep track of the coin values along with their indices and iteratively pop and push from/to the heap as we select the highest value coins.
Complexity
Time Complexity: O(k log n), as we perform k heap operations on n piles.
Space Complexity: O(n), due to storing piles in the heap.
Approach 3: Dynamic Programming (Grouped Knapsack)
We define f[i][j] as the maximum value sum of taking j coins from the first i piles. The answer is f[n][k], where n is the number of piles.
For the i-th pile, we can choose to take the first 0, 1, 2, cdots, k coins. We can use a prefix sum array s to quickly calculate the value sum of taking the first h coins.
The state transition equation is:
$
f[i][j] = max(f[i][j], f[i - 1][j - h] + s[h])
where 0 leq h leq j, and s[h] represents the value sum of taking the first h coins from the i-th pile.
The time complexity is O(k times L), and the space complexity is O(n times k). Here, L is the total number of coins, and n$ is the number of piles.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Dynamic Programming (Space Optimization)
We can observe that for the i-th pile, we only need to use f[i - 1][j] and f[i][j - h], so we can optimize the two-dimensional array to a one-dimensional array.
The time complexity is O(k times L), and the space complexity is O(k).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * k * m), where n is the number of piles, k is the number of coins to pick, and m is the average number of coins in each pile. Space Complexity: O(n * k) |
| Greedy Approach | Time Complexity: O(k log n), as we perform k heap operations on n piles. Space Complexity: O(n), due to storing piles in the heap. |
| Dynamic Programming (Grouped Knapsack) | — |
| Dynamic Programming (Space Optimization) | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Maximum Value of K Coins from Piles - Leetcode 2218 - Python • NeetCodeIO • 12,361 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Value of K Coins From Piles easy or hard?
Maximum Value of K Coins From Piles Python/Java solution
How to solve Maximum Value of K Coins From Piles in O(n)?
What is the best approach for Maximum Value of K Coins From Piles?
Is Maximum Value of K Coins From Piles asked at Google/Amazon/Meta?
What data structure is used in Maximum Value of K Coins From Piles?
What is the time complexity of Maximum Value of K Coins From Piles?
Ready to solve this problem?
Practice Maximum Value of K Coins From Piles with our built-in code editor and test cases.
Practice on FleetCode