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) <= 2000This 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.
C++
Java
C#
JavaScript
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)
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.
C++
Java
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 | 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. |
Maximum Value of K Coins from Piles - Leetcode 2218 - Python • NeetCodeIO • 10,469 views views
Watch 9 more video solutions →Practice Maximum Value of K Coins From Piles with our built-in code editor and test cases.
Practice on FleetCode