Maximum Value of K Coins From Piles solution and explanation
Google
9 more videos on this problem
Maximum Value of K Coins from Piles - Leetcode 2218 - PythonNeetCodeIO · 18:04 · 12K views
Maximum Value of K Coins From Piles | META | Leetcode-2218 | codestorywithMIKcodestorywithMIK · 33:00 · 10K views
2218. Maximum Value of K Coins From Piles || Leetcode Weekly Contest 286 || Leetcode 2218Bro Coders · 10:46 · 4K views
Maximum Value of K Coins From Piles || Dynamic Programming || C++/Java/Python || Leetcode - 2218Aryan Mittal · 17:41 · 3K views
Maximum Value of K Coins From Piles | Leetcode 2218 |Dynamic Programminng | Contest 286 🔥🔥Coding Decoded · 6:58 · 2K views
2218 || Maximum Value of K Coins From Piles || C++ || Leetcode Daily ChallengeCodeFreaks · 14:04 · 891 views
2218. Maximum Value of K Coins From Piles (Leetcode Hard)Programming Live with Larry · 41:50 · 705 views
Leetcode 2218. Maximum Value of K Coins Detailed Explanation + Coding (Python)Algorithms Simplified · 12:53 · 358 views
Leetcode Hard #2218 (Java) - Maximum Value of K Coins From Piles (Contest #286)NatorAlgoVids · 7:06 · 333 views
Leetcode 2218: Maximum Value of K Coins From PilesAlgorithms Casts · 17:58 · 187 views
The problem
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.
def maxValueOfCoins(piles, k):
n = len(piles)
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
current_pile = piles[i - 1]
pile_sum = 0
for j in range(len(current_pile)):
pile_sum += current_pile[j]
for x in range(k, j + 2 - 1, -1):
dp[i][x] = max(dp[i][x], dp[i - 1][x - (j + 1)] + pile_sum)
return dp[n][k]
# Example usage:
piles = [[1, 100, 3], [7, 8, 9]]
k = 2
print(maxValueOfCoins(piles, k)) # Output: 101import java.util.List;
public 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);
int pileSum = 0;
for (int j = 0; j < currentPile.size(); j++) {
pileSum += currentPile.get(j);
for (int x = k; x >= j + 1; x--) {
dp[i][x] = Math.max(dp[i][x], dp[i - 1][x - j - 1] + pileSum);
}
}
}
return dp[n][k];
}
// Example usage:
// List<List<Integer>> piles = Arrays.asList(Arrays.asList(1, 100, 3), Arrays.asList(7, 8, 9));
// int k = 2;
// int result = new Solution().maxValueOfCoins(piles, k); // Output: 101
}#include <vector>
#include <algorithm>
using namespace std;
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
int n = piles.size();
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
for (int i = 1; i <= n; ++i) {
vector<int>& current_pile = piles[i - 1];
int pile_sum = 0;
for (int j = 0; j < current_pile.size(); ++j) {
pile_sum += current_pile[j];
for (int x = k; x >= j + 1; --x) {
dp[i][x] = max(dp[i][x], dp[i - 1][x - (j + 1)] + pile_sum);
}
}
}
return dp[n][k];
}
// Example usage:
// vector<vector<int>> piles = {{1, 100, 3}, {7, 8, 9}};
// int k = 2;
// int result = maxValueOfCoins(piles, k); // Output: 101function maxValueOfCoins(piles, k) {
const n = piles.length;
const dp = Array(n + 1).fill(0).map(() => Array(k + 1).fill(0));
for (let i = 1; i <= n; i++) {
const currentPile = piles[i - 1];
let pileSum = 0;
for (let j = 0; j < currentPile.length; j++) {
pileSum += currentPile[j];
for (let x = k; x >= j + 1; x--) {
dp[i][x] = Math.max(dp[i][x], dp[i - 1][x - (j + 1)] + pileSum);
}
}
}
return dp[n][k];
}
// Example usage:
// const piles = [[1, 100, 3], [7, 8, 9]];
// const k = 2;
// console.log(maxValueOfCoins(piles, k)); // Output: 101using System;
using System.Collections.Generic;
public class Solution {
public int MaxValueOfCoins(IList<IList<int>> piles, int k) {
int n = piles.Count;
var dp = new int[n + 1, k + 1];
for (int i = 1; i <= n; i++) {
var currentPile = piles[i - 1];
int pileSum = 0;
for (int j = 0; j < currentPile.Count; j++) {
pileSum += currentPile[j];
for (int x = k; x >= j + 1; x--) {
dp[i, x] = Math.Max(dp[i, x], dp[i - 1, x - j - 1] + pileSum);
}
}
}
return dp[n, k];
}
// Example usage:
// IList<IList<int>> piles = new List<IList<int>>{ new List<int>{1, 100, 3}, new List<int>{7, 8, 9} };
// int k = 2;
// int result = new Solution().MaxValueOfCoins(piles, k); // Output: 101
}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.
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.
import heapq
def maxValueOfCoins(piles, k):
max_heap = []
for pile in piles:
heapq.heappush(max_heap, (-pile[0], 0, pile))
total_value = 0
for _ in range(k):
value, index, pile = heapq.heappop(max_heap)
total_value -= value
if index + 1 < len(pile):
heapq.heappush(max_heap, (-pile[index + 1], index + 1, pile))
return total_value
# Example usage:
piles = [[1, 100, 3], [7, 8, 9]]
k = 2
print(maxValueOfCoins(piles, k)) # Output: 101import java.util.*;
public class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
for (int i = 0; i < piles.size(); i++) {
maxHeap.offer(new int[]{piles.get(i).get(0), 0, i});
}
int totalValue = 0;
for (int i = 0; i < k; i++) {
int[] top = maxHeap.poll();
totalValue += top[0];
int pileIndex = top[2], coinIndex = top[1];
if (coinIndex + 1 < piles.get(pileIndex).size()) {
maxHeap.offer(new int[]{piles.get(pileIndex).get(coinIndex + 1), coinIndex + 1, pileIndex});
}
}
return totalValue;
}
// Example usage:
// List<List<Integer>> piles = Arrays.asList(Arrays.asList(1, 100, 3), Arrays.asList(7, 8, 9));
// int k = 2;
// int result = new Solution().maxValueOfCoins(piles, k); // Output: 101
}#include <vector>
#include <queue>
using namespace std;
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
struct Compare {
bool operator()(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
};
priority_queue<vector<int>, vector<vector<int>>, Compare> max_heap;
for (auto& pile : piles) {
max_heap.push({pile[0], 0, (int)pile.size(), (int)&pile - (int)&piles[0]});
}
int total_value = 0;
for (int _ = 0; _ < k; ++_) {
auto top = max_heap.top();
max_heap.pop();
int value = top[0], index = top[1], size = top[2];
int pile_idx = top[3];
total_value += value;
if (index + 1 < size) {
int next_value = piles[pile_idx][index + 1];
max_heap.push({next_value, index + 1, size, pile_idx});
}
}
return total_value;
}
// Example usage:
// vector<vector<int>> piles = {{1, 100, 3}, {7, 8, 9}};
// int k = 2;
// int result = maxValueOfCoins(piles, k); // Output: 101The 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.
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.
function maxValueOfCoins(piles: number[][], k: number): number {
const n = piles.length;
const f: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
for (let i = 1; i <= n; i++) {
const nums = piles[i - 1];
const s = Array(nums.length + 1).fill(0);
for (let j = 1; j <= nums.length; j++) {
s[j] = s[j - 1] + nums[j - 1];
}
for (let j = 0; j <= k; j++) {
for (let h = 0; h < s.length && h <= j; h++) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - h] + s[h]);
}
}
}
return f[n][k];
}func maxValueOfCoins(piles [][]int, k int) int {
n := len(piles)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, k+1)
}
for i := 1; i <= n; i++ {
nums := piles[i-1]
s := make([]int, len(nums)+1)
for j := 1; j <= len(nums); j++ {
s[j] = s[j-1] + nums[j-1]
}
for j := 0; j <= k; j++ {
for h, w := range s {
if j < h {
break
}
f[i][j] = max(f[i][j], f[i-1][j-h]+w)
}
}
}
return f[n][k]
}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).
function maxValueOfCoins(piles: number[][], k: number): number {
const f: number[] = Array(k + 1).fill(0);
for (const nums of piles) {
const s: number[] = Array(nums.length + 1).fill(0);
for (let j = 1; j <= nums.length; j++) {
s[j] = s[j - 1] + nums[j - 1];
}
for (let j = k; j >= 0; j--) {
for (let h = 0; h < s.length && h <= j; h++) {
f[j] = Math.max(f[j], f[j - h] + s[h]);
}
}
}
return f[k];
}func maxValueOfCoins(piles [][]int, k int) int {
f := make([]int, k+1)
for _, nums := range piles {
s := make([]int, len(nums)+1)
for j := 1; j <= len(nums); j++ {
s[j] = s[j-1] + nums[j-1]
}
for j := k; j >= 0; j-- {
for h := 0; h < len(s) && h <= j; h++ {
f[j] = max(f[j], f[j-h]+s[h])
}
}
}
return f[k]
}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) | – |
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 |
Frequently asked questions
Is Maximum Value of K Coins From Piles easy or hard?
Maximum Value of K Coins From Piles is categorized as a Hard problem. The difficulty comes from recognizing the grouped knapsack pattern and efficiently combining prefix sums with dynamic programming to handle multiple piles and coin choices.
Maximum Value of K Coins From Piles Python/Java solution
Python and Java solutions typically implement a DP array where dp[j] stores the best value achievable using j coins. For each pile, prefix sums allow constant-time value lookup when taking x coins, and DP transitions update the maximum values efficiently.
How to solve Maximum Value of K Coins From Piles in O(n)?
An exact O(n) solution is not feasible because the algorithm must consider multiple choices from each pile. The standard optimal solution is O(n * k * m) using dynamic programming and prefix sums to evaluate every valid distribution of k coins.
What is the best approach for Maximum Value of K Coins From Piles?
Dynamic programming with prefix sums is the best approach. Treat each pile as a group where you can choose 0 to m coins from the top. Precompute prefix sums for quick value lookup and use DP to track the maximum value for picking j coins. This guarantees the optimal solution.
Is Maximum Value of K Coins From Piles asked at Google/Amazon/Meta?
Maximum Value of K Coins From Piles represents a classic dynamic programming pattern similar to grouped knapsack problems, which frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests DP state design and transition optimization.
What data structure is used in Maximum Value of K Coins From Piles?
The main structures used are arrays for storing piles and prefix sums, along with a dynamic programming array to track the best value for selecting j coins. Some heuristic approaches may also use a priority queue for greedy selection.
What is the time complexity of Maximum Value of K Coins From Piles?
The optimal dynamic programming solution runs in O(n * k * m) time, where n is the number of piles, k is the number of coins to pick, and m is the maximum coins considered from a pile. Space complexity can be optimized to O(k) using a 1D DP array.