2218. Maximum Value of K Coins From Piles
Problem Description
You are given n piles of coins, each pile containing a stack of coins with varying denominations. The piles are represented by a list piles, where each element piles[i] is itself a list that contains integers representing the coins' values in the ith pile from the top to the bottom of the pile.
The goal is to maximize the total value of coins you can collect by picking coins from the tops of these piles. However, there's a catch: you can only make a total of k moves, and in each move, you can only pick one coin from the top of any pile. Once you take a coin from a pile, you can't skip coins; you can only take another coin from the same pile if it's now the new top coin of that pile.
Knowing this, you need to find the maximum total value of coins you can amass in your wallet assuming you make exactly k moves and do so in the most optimal way possible.
Intuition
To approach this problem effectively, we need a strategy that allows us to make local decisions that contribute to our overall goal of maximizing the value of the coins we collect. This is a classic optimization problem that hints at using dynamic programming (DP) because it involves making a series of decisions that rely on the outcomes of previous decisions.
The intuition behind the solution involves two key insights:
- We need to track the maximum value we can achieve for any number of moves up to
k, as we progress through the piles. - We must consider all possible options for each pile, i.e., we can choose 0 coins from the pile, or we can take 1 coin, or we can take 2 coins, and so on, and for each of these choices, we need to update the maximum value possible considering the new total number of moves.
The implementation uses a 2D dynamic programming approach, which is effectively compressed into a 1D DP array dp for space efficiency. The dp array stores the maximum value that can be achieved for each possible number of moves up to k.
The presum array contains the prefix sums for each pile, which allows us to easily compute the total value gained by taking the first i coins from a pile.
The trick is to iterate through all piles and all possible coin counts we might take from each pile, update our dp array to store the best result. The updating is done in reverse to ensure that we don't overwrite a DP state before we're done using it for the current pile.
At the end of the iteration, dp[k] will hold our answer, which is the maximum value we can collect with k coins picked.
Learn more about Dynamic Programming and Prefix Sum patterns.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Solution Approach
The solution involves dynamic programming (DP), a technique that solves problems by breaking them down into simpler subproblems. We use a 1D DP array, dp, where each index j represents the maximum value achievable with j moves. The DP array is initialized with zeros, as initially, no coins are taken.
For each pile s in our presum array, where presum is a list of prefix sums (cumulative sums from the start of the pile to the current index), we iterate through our dp array in reverse. We do this because we want to update our dp values for using a certain number of coins, idx, from the current pile without affecting the other values of dp that we haven't processed yet.
For each index j of our dp array, we loop through all possible coin counts, idx, that we could take from the current pile, represented by the different values in the prefix sum. If taking idx coins is feasible (i.e., j is greater than or equal to idx), then we update our dp[j] by choosing the max between its current value and the sum of dp[j - idx] and the value of the idx-th coin, v. Mathematically, this is represented as follows:
1dp[j] = max(dp[j], dp[j - idx] + v)
This line of the code represents the core of the DP transition equation. It updates the dp[j] to the maximum value we could have if we did not take any coins from the current pile or if we took idx coins from the current pile.
The process continues until we have processed all piles and considered all possible moves up to k. The last element of the dp array, dp[-1] or dp[k], will contain the maximum total value achievable by taking k coins across all piles.
Data Structures:
- A list
dpfor the DP array. - A list of lists
presumfor the prefix sums of each pile.
Algorithms and Patterns:
- Dynamic programming for optimal substructure and overlapping subproblems.
- Prefix sums to quickly calculate the sum of taking a certain number of coins from a pile.
- Iterating in reverse to preserve DP states for processing without interference.
By carefully iterating and updating our DP array, we ensure that at the completion of the algorithm, the dp[k] index will hold the maximum value of coins we can collect out of k moves.
Which two pointer techniques do you use to check if a string is a palindrome?
Example Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have the following piles of coins and can make k = 2 moves:
1piles = [[1, 2], [2, 1]]
We want to find the maximum value we can collect by making exactly two moves.
Step 1: Create Prefix Sums for Each Pile
First, we calculate the prefix sum for each pile to make summing coins efficient.
For the first pile [1, 2], the prefix sums are [1, 3] (taking 0 coins gives 0, taking the first coin gives 1, and taking the first two coins gives 3).
For the second pile [2, 1], the prefix sums are [2, 3].
Step 2: Initialize the DP Array
Next, we initialize a dp array with a length of k+1 (for 0 to k moves), starting with all zeros:
dp = [0, 0, 0]
Step 3: Iterate Over Piles and Update DP Array
We iterate over each prefix sum array and update our dp:
-
For the first pile's prefix sums
[1, 3], we compare:- For
j = 1:dp[1] = max(dp[1], dp[1 - 0] + 1) = max(0, 0 + 1) = 1(using 1 coin from the pile) - For
j = 1:dp[1] = max(dp[1], dp[1 - 1] + 1) = max(1, 0 + 2) = 2(opting to instead use 2 coins from the pile) - For
j = 2:dp[2] = max(dp[2], dp[2 - 1] + 1) = max(0, 1 + 2) = 3(taking 1 coin previously and 1 coin now) - For
j = 2:dp[2] = max(dp[2], dp[2 - 2] + 3) = max(3, 0 + 3) = 3(taking both coins from this pile)
- For
In each iteration, idx is considered as the number of coins we pick from the current pile (hence the added values from the prefix sums). We choose the largest possible value to assign to dp[j].
After processing the first pile, our dp array is [0, 2, 3].
-
For the second pile's prefix sums
[2, 3], we perform similar updates:- For
j = 1:dp[1] = max(dp[1], dp[1 - 0] + 2) = max(2, 0 + 2) = 2(no change) - For
j = 1:dp[1] = max(dp[1], dp[1 - 1] + 2) = max(2, 0 + 2) = 2(opting to instead use 2 coins from the pile) - For
j = 2:dp[2] = max(dp[2], dp[2 - 1] + 2) = max(3, 2 + 1) = 3(taking 1 coin from the first pile and 1 from this one) - For
j = 2:dp[2] = max(dp[2], dp[2 - 2] + 3) = max(3, 0 + 3) = 3(no change)
- For
After processing the second pile, our dp array is still [0, 2, 3].
Step 4: Collect the Result
After iterating through all piles, the last entry in the dp array gives us the answer. For k = 2, dp[k] is 3, so the maximum value we can collect is 3.
In this example, the best strategy is to take one coin with a value of 2 from the first pile and one coin with a value of 1 from the second pile, or to take the top coin from each pile, as both strategies yield the total maximum value of 3.
Solution Implementation
1from itertools import accumulate
2
3class Solution:
4 def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
5 # Precompute the prefix sums for each pile
6 # Each prefix sum list starts with 0 for convenience
7 prefix_sums = [list(accumulate(pile, initial=0)) for pile in piles]
8
9 # Initialize the DP array with 0's; size k+1 for the 'zero' case
10 dp = [0] * (k + 1)
11
12 # Iterate over each pile's prefix sums
13 for sums in prefix_sums:
14 # Iterate over the DP values in reverse
15 # This is to ensure that we do not use a value from this step
16 # in the calculation of another value in the same step
17 for remaining_coins in range(k, -1, -1):
18 # Enumerate over the prefix sums providing index and value
19 for index, value in enumerate(sums):
20 # Make sure when taking 'index' coins from this pile,
21 # it does not exceed the remaining_coin limit
22 if remaining_coins >= index:
23 # Update the DP value with the maximum between the current value
24 # and the value achievable by taking 'index' coins from this pile
25 dp[remaining_coins] = max(dp[remaining_coins], dp[remaining_coins - index] + value)
26 # The last element of dp is the maximum value achievable by taking k coins
27 return dp[-1]
281class Solution {
2 public int maxValueOfCoins(List<List<Integer>> piles, int k) {
3 int numPiles = piles.size();
4 List<int[]> prefixSums = new ArrayList<>();
5
6 // Calculate prefix sums for each pile to have quick access to the sum of the first i coins
7 for (List<Integer> pile : piles) {
8 int pileSize = pile.size();
9 int[] prefixSum = new int[pileSize + 1];
10
11 for (int i = 0; i < pileSize; ++i) {
12 prefixSum[i + 1] = prefixSum[i] + pile.get(i);
13 }
14
15 prefixSums.add(prefixSum);
16 }
17
18 // Initialize DP array to store the maximum value we can achieve picking i coins
19 int[] dp = new int[k + 1];
20
21 // Iterate through each pile's prefix sums
22 for (int[] prefixSum : prefixSums) {
23 // Iterate over the dp array in reverse to avoid overwriting values we still need to read
24 for (int j = k; j >= 0; --j) {
25 // Try taking 0 to pileSize coins from the current pile and update dp values
26 for (int idx = 0; idx < prefixSum.length; ++idx) {
27 if (j >= idx) {
28 // Update the dp value if taking idx coins gives us a better result
29 dp[j] = Math.max(dp[j], dp[j - idx] + prefixSum[idx]);
30 }
31 }
32 }
33 }
34
35 // Finally, return the maximum value that can be achieved by taking k coins
36 return dp[k];
37 }
38}
391#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to calculate the maximum value of coins we can obtain by selecting at most k coins from several piles
7 int maxValueOfCoins(vector<vector<int>>& piles, int k) {
8 // Create a vector to store the prefix sums for all piles
9 vector<vector<int>> prefixSums;
10 for (auto& pile : piles) {
11 int pileSize = pile.size();
12 vector<int> sum(pileSize + 1);
13 for (int i = 0; i < pileSize; ++i)
14 sum[i + 1] = sum[i] + pile[i]; // Calculate the prefix sum for the current pile
15 prefixSums.push_back(sum); // Store it in the vector of prefix sums
16 }
17
18 // Create a DP vector to store the maximum value of coins for each k
19 vector<int> dp(k + 1);
20 // Iterate through the prefix sums of each pile
21 for (auto& sums : prefixSums) {
22 // Iterate through the possible number of coins to take in reverse
23 for (int coinsToTake = k; coinsToTake >= 0; --coinsToTake) {
24 // Iterate through each index in the current prefix sum vector
25 for (int idx = 0; idx < sums.size(); ++idx) {
26 // If the current number of coins to take is greater or equal to the index
27 if (coinsToTake >= idx)
28 dp[coinsToTake] = max(dp[coinsToTake], dp[coinsToTake - idx] + sums[idx]); // Update the DP value with max value
29 }
30 }
31 }
32 // Return the maximum value for taking k coins
33 return dp[k];
34 }
35};
361function maxValueOfCoins(piles: number[][], k: number): number {
2 // Create an array to store the prefix sums for all piles
3 let prefixSums: number[][] = [];
4 for (let pile of piles) {
5 let pileSize: number = pile.length;
6 let sum: number[] = new Array(pileSize + 1).fill(0);
7 for (let i = 0; i < pileSize; i++)
8 sum[i + 1] = sum[i] + pile[i]; // Calculate the prefix sum for the current pile
9 prefixSums.push(sum); // Store it in the array of prefix sums
10 }
11
12 // Create a DP array to store the maximum value of coins for each number up to k
13 let dp: number[] = new Array(k + 1).fill(0);
14 // Iterate through the prefix sums of each pile
15 for (let sums of prefixSums) {
16 // Iterate through the possible number of coins to take in reverse
17 for (let coinsToTake = k; coinsToTake >= 0; coinsToTake--) {
18 // Iterate through each index in the current prefix sum array
19 for (let idx = 0; idx < sums.length; idx++) {
20 // If the current number of coins to take is greater or equal to the index
21 if (coinsToTake >= idx)
22 dp[coinsToTake] = Math.max(dp[coinsToTake], dp[coinsToTake - idx] + sums[idx]); // Update the DP value with the maximum value
23 }
24 }
25 }
26 // Return the maximum value for taking k coins
27 return dp[k];
28}
29Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Time and Space Complexity
The time complexity of the provided code can be analyzed by breaking down its operations. We need to consider the number of iterations in the nested loops along with the cost of constructing the prefix sum presum.
The first operation is the construction of the prefix sums for each pile, which is O(n) per pile where n is the number of coins in the pile. If there are m piles, this step will be O(m * n).
Next, we look at the nested loops. The outermost loop iterates over each pile's prefix sum list, which will happen m times (the number of piles). The middle loop will always iterate k times since it goes from k to 0. The innermost loop depends on the length of the current prefix sum list, which can be a maximum of k+1, because we will never take more than k coins from a single pile.
Combining the total iterations for the nested loops, we have m (number of piles) multiplied by k (maximum coins we can pick) multiplied by k+1 (coinciding with the prefix sums length). Therefore, the total time complexity of the nested loops is O(m * k^2).
Hence, the overall time complexity of the algorithm is dominated by the nesting loops, resulting in O(m * k^2).
The space complexity of the algorithm can be determined by looking at the extra space used. The presum variable will store up to k+1 elements for each of the m piles, which means that its space complexity is O(m * (k+1)). However, since constants are omitted in Big O notation, it simplifies to O(m * k).
The dp array will have k+1 elements no matter what, leading to a space complexity of O(k).
Since dp does not grow with m, the overall space complexity will be dominated by presum, so the overall space complexity is O(m * k).
Learn more about how to find time and space complexity quickly using problem constraints.
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.