LeetCode 2218 - Maximum Value of K Coins From Piles

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

This problem asks us to maximize the total value of coins collected from multiple piles while following a strict removal rule. Each pile is ordered from top to bottom, meaning we cannot arbitrarily pick any coin in a pile. We may only remove coins from the top, one at a time. If we want a coin deeper in a pile, we must first remove every coin above it.

The input consists of a two dimensional array piles, where piles[i] represents the i-th pile of coins. Each pile contains positive integer values, ordered from top to bottom. We are also given an integer k, representing the exact number of coins we must pick.

The key detail is that we must choose exactly k coins, not at most k. Among all valid ways to take exactly k coins across all piles, we want the maximum possible total value.

For example, if a pile is [1, 100, 3], taking the 100 coin alone is impossible because it is buried under the 1. To access 100, we must first take 1, meaning taking the first two coins yields a total of 101.

The constraints provide important hints about the intended solution:

The number of piles can be as large as 1000.
The total number of coins across all piles is at most 2000.
k can also be as large as 2000.

A brute force search over every possible coin selection would be computationally infeasible because the number of combinations grows exponentially. However, the relatively small upper bound of 2000 for total coins suggests that a dynamic programming approach based on coin counts is feasible.

An important observation is that for each pile, the only meaningful choices are taking the first 0, 1, 2, ..., m coins, where m is the size of that pile. Since coins must be removed from the top, there are only prefix selections for each pile.

Several edge cases are worth considering upfront. One case is when k = 1, where we simply want the single highest accessible coin from the top of all piles. Another case occurs when k equals the total number of coins, forcing us to take everything. A tricky scenario happens when one pile contains very large values deeper in the stack, requiring smaller coins to be taken first to unlock a better payoff. The problem guarantees at least one valid solution because k <= sum(piles[i].length).

Approaches

Brute Force Approach

A brute force solution would recursively try every possible number of coins to take from each pile.

For every pile, we could decide to take 0, 1, 2, ..., up to all available coins. Then we recursively process the remaining piles while tracking how many coins remain to be chosen.

This approach is correct because it explores every legal combination of prefix selections across piles and evaluates the total value for each possibility. Eventually, the maximum valid sum using exactly k coins is found.

However, this strategy becomes far too slow. Suppose each pile allows several choices. The number of recursive branches grows exponentially because each pile introduces multiple possibilities. With up to 1000 piles, exhaustive exploration becomes impossible.

Key Insight for an Optimal Solution

The key insight is that this problem has overlapping subproblems, making it a natural fit for dynamic programming.

At any point, our decision depends only on:

How many piles we have processed.
How many coins we have already taken.

Instead of recomputing the best answer repeatedly, we can store intermediate results.

Another crucial optimization comes from prefix sums. Since we can only take coins from the top of a pile, the only relevant values are prefix totals:

Take 0 coins → value 0
Take first 1 coin → prefix sum
Take first 2 coins → prefix sum
And so on

This allows us to quickly compute the value gained from taking x coins from a pile.

We then use dynamic programming similar to a knapsack problem:

dp[c] represents the maximum value achievable using exactly c coins after processing some number of piles.
For each pile, we update the DP array by trying every possible number of coins to take from that pile.

This transforms an exponential search into a polynomial time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n) recursion	Tries every possible prefix choice for every pile
Optimal Dynamic Programming	O(n × k × m)	O(k)	Uses prefix sums and knapsack style DP

Here, m represents the average pile size. Since the total number of coins is bounded by 2000, this complexity is practical.

Algorithm Walkthrough

Step 1: Create a DP Array

We maintain a one dimensional dynamic programming array:

dp[c] = maximum value obtainable using exactly c coins

Initially:

dp[0] = 0

Everything else starts at 0 because we have not processed any piles yet.

The DP size is k + 1 since we only care about coin counts from 0 to k.

Step 2: Process Each Pile Independently

For every pile, we compute prefix sums.

Suppose the pile is:

[1, 100, 3]

Its prefix sums become:

[0, 1, 101, 104]

This means:

Taking 0 coins gives 0
Taking 1 coin gives 1
Taking 2 coins gives 101
Taking 3 coins gives 104

We precompute these values so each lookup becomes constant time.

Step 3: Use a Temporary DP Array

For each pile, we create a copy of the current DP array.

This prevents overwriting values that are still needed during transitions.

If we updated dp directly, we might accidentally reuse coins from the same pile multiple times.

Step 4: Try All Valid Coin Choices

For every target coin count c from 1 to k, we try taking:

0, 1, 2, ..., min(c, pile_size)

coins from the current pile.

The transition formula becomes:

new_dp[c] =
max(
    new_dp[c],
    dp[c - x] + prefix_sum[x]
)

Where:

x = coins taken from current pile
dp[c - x] = best previous result
prefix_sum[x] = value gained from current pile

We evaluate all valid choices and keep the best one.

Step 5: Replace the DP Array

After processing a pile:

dp = new_dp

Now dp[c] reflects the best possible answer using processed piles.

Step 6: Return Final Result

At the end:

dp[k]

contains the maximum value achievable using exactly k coins.

Why it works

The algorithm works because of optimal substructure. For every pile, we exhaustively consider every valid number of coins that could be taken from it. If taking x coins from the current pile is part of the optimal solution, then the remaining k - x coins must also form an optimal solution among previously processed piles. Dynamic programming guarantees that these smaller optimal answers are already stored in dp, so combining them always produces the correct global optimum.

Python Solution

from typing import List

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        dp = [0] * (k + 1)

        for pile in piles:
            prefix_sums = [0]

            current_sum = 0
            for coin in pile:
                current_sum += coin
                prefix_sums.append(current_sum)

            new_dp = dp[:]

            pile_size = len(pile)

            for coins_taken in range(1, k + 1):
                max_take = min(coins_taken, pile_size)

                for take in range(1, max_take + 1):
                    new_dp[coins_taken] = max(
                        new_dp[coins_taken],
                        dp[coins_taken - take] + prefix_sums[take]
                    )

            dp = new_dp

        return dp[k]

The implementation begins by initializing a dynamic programming array of size k + 1. Each position stores the best achievable value for an exact number of chosen coins.

For every pile, we first compute prefix sums. This preprocessing step allows us to instantly determine the total value of taking the first x coins from that pile.

A copy of the DP array is created as new_dp. This is important because transitions for the current pile must only depend on results from previously processed piles.

We then iterate through every possible number of coins we want to end up with, from 1 to k. For each count, we try taking every feasible number of coins from the current pile. The DP transition updates the maximum obtainable value.

Finally, after processing all piles, dp[k] contains the optimal answer.

Go Solution

func maxValueOfCoins(piles [][]int, k int) int {
	dp := make([]int, k+1)

	for _, pile := range piles {
		prefixSums := []int{0}

		currentSum := 0
		for _, coin := range pile {
			currentSum += coin
			prefixSums = append(prefixSums, currentSum)
		}

		newDP := make([]int, k+1)
		copy(newDP, dp)

		pileSize := len(pile)

		for coinsTaken := 1; coinsTaken <= k; coinsTaken++ {
			maxTake := pileSize
			if maxTake > coinsTaken {
				maxTake = coinsTaken
			}

			for take := 1; take <= maxTake; take++ {
				candidate := dp[coinsTaken-take] + prefixSums[take]

				if candidate > newDP[coinsTaken] {
					newDP[coinsTaken] = candidate
				}
			}
		}

		dp = newDP
	}

	return dp[k]
}

The Go implementation follows the same dynamic programming strategy as Python. One difference is slice handling. Since Go slices are references to underlying arrays, we explicitly allocate a fresh newDP slice and copy values using copy().

Go integers are safe here because the maximum possible answer remains well within integer limits. Since coin values are at most 10^5 and total coins are at most 2000, the maximum sum is approximately 2 × 10^8, which comfortably fits in Go's int.

Unlike Python lists, Go requires explicit bounds handling, so we manually compute maxTake.

Worked Examples

Example 1

Input

piles = [[1,100,3],[7,8,9]]
k = 2

Initial State

dp = [0, 0, 0]

Process First Pile: `[1,100,3]`

Prefix sums:

[0, 1, 101, 104]

Coins	Calculation	Result
1	dp[0] + 1	1
2	dp[0] + 101	101

Updated DP:

dp = [0, 1, 101]

Process Second Pile: `[7,8,9]`

Prefix sums:

[0, 7, 15, 24]

For 2 coins:

Take From Current Pile	Formula	Value
1	dp[1] + 7	8
2	dp[0] + 15	15
0	existing	101

Best result remains:

Final answer:

dp[2] = 101

Example 2

Input

piles = [
    [100],
    [100],
    [100],
    [100],
    [100],
    [100],
    [1,1,1,1,1,1,700]
]
k = 7

After processing the six single coin piles:

dp = [0,100,200,300,400,500,600,600]

Prefix sums for last pile:

[0,1,2,3,4,5,6,706]

When computing dp[7]:

Coins Taken From Last Pile	Formula	Result
1	dp[6] + 1	601
2	dp[5] + 2	502
7	dp[0] + 706	706

Best result:

Final answer:

dp[7] = 706

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k × totalCoins)	Each pile considers every feasible coin count and prefix choice
Space	O(k)	Only a one dimensional DP array is maintained

The total runtime is efficient because the total number of coins across all piles is bounded by 2000. For each pile, we try all possible coin counts up to k, and for each count, we try all valid prefix lengths. Since the sum of pile sizes is limited, the practical upper bound is approximately O(k × totalCoins).

The space complexity is only O(k) because we reuse a one dimensional DP array rather than maintaining a full two dimensional table.

Test Cases

sol = Solution()

# Example 1
assert sol.maxValueOfCoins([[1, 100, 3], [7, 8, 9]], 2) == 101

# Example 2
assert (
    sol.maxValueOfCoins(
        [[100], [100], [100], [100], [100], [100], [1, 1, 1, 1, 1, 1, 700]],
        7
    ) == 706
)

# Single pile, must take all coins
assert sol.maxValueOfCoins([[1, 2, 3]], 3) == 6

# Single pile, partial selection
assert sol.maxValueOfCoins([[10, 20, 30]], 2) == 30

# Multiple piles, best choice spans piles
assert sol.maxValueOfCoins([[1, 100], [50, 50]], 2) == 101

# k = 1
assert sol.maxValueOfCoins([[5], [10], [7]], 1) == 10

# Taking everything
assert sol.maxValueOfCoins([[1, 2], [3, 4]], 4) == 10

# Deep valuable coin requires unlocking
assert sol.maxValueOfCoins([[1, 1, 100]], 3) == 102

# Many small piles
assert sol.maxValueOfCoins([[1], [2], [3], [4]], 2) == 7

# Equal values
assert sol.maxValueOfCoins([[5, 5], [5, 5]], 3) == 15

Test	Why
`[[1,100,3],[7,8,9]], k=2`	Verifies provided example
Multiple `100` piles plus `700`	Ensures deep reward logic works
Single pile, take all	Tests full prefix selection
Single pile, partial	Verifies limited selection
Cross pile optimization	Ensures DP combines piles correctly
`k = 1`	Tests minimum coin requirement
Take all coins	Tests upper boundary
Valuable deep coin	Validates unlocking requirement
Many small piles	Verifies pile iteration
Equal values	Tests duplicate handling

Edge Cases

Edge Case 1: A Valuable Coin Deep in a Pile

A common mistake is assuming we can freely select any coin. Consider:

[[1, 1, 100]]
k = 1

The answer is 1, not 100, because the large coin is inaccessible without removing the coins above it first. Our implementation handles this correctly by only considering prefix sums, meaning deeper coins are never selected independently.

Edge Case 2: `k` Equals Total Number of Coins

When k equals the total number of available coins, the algorithm has no freedom, it must take everything.

Example:

[[1,2],[3,4]]
k = 4

The answer is simply the sum of all coins. Since DP evaluates every valid prefix combination, it naturally converges to taking all piles completely.

Edge Case 3: Many Small Piles

With up to 1000 piles, recursive approaches may become inefficient or risk stack overhead.

Example:

[[1],[2],[3],[4],...]

Our iterative dynamic programming solution processes piles one at a time using only O(k) memory, making it scalable even when the number of piles is very large.

Edge Case 4: Taking Zero Coins From a Pile

Sometimes the optimal choice is skipping a pile entirely.

Example:

[[1,2,3],[100]]
k = 1

The correct answer is 100.

Our implementation handles this automatically because new_dp begins as a copy of dp, implicitly representing the option of taking zero coins from the current pile.

LeetCode 2218 - Maximum Value of K Coins From Piles

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight for an Optimal Solution

Algorithm Walkthrough

Step 1: Create a DP Array

Step 2: Process Each Pile Independently

Step 3: Use a Temporary DP Array

Step 4: Try All Valid Coin Choices

Step 5: Replace the DP Array

Step 6: Return Final Result

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Initial State

Process First Pile: [1,100,3]

Process Second Pile: [7,8,9]

Example 2

Complexity Analysis

Test Cases

Edge Cases

Edge Case 1: A Valuable Coin Deep in a Pile

Edge Case 2: k Equals Total Number of Coins

Edge Case 3: Many Small Piles

Edge Case 4: Taking Zero Coins From a Pile

Process First Pile: `[1,100,3]`

Process Second Pile: `[7,8,9]`

Edge Case 2: `k` Equals Total Number of Coins