Jobs

Interviews

Discussions

Maximum Value of K Coins From Piles

Hard

Asked by:

28 views

Topics:

Dynamic Programming

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 i^th 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.length
1 <= n <= 1000
1 <= piles[i][j] <= 10⁵
1 <= k <= sum(piles[i].length) <= 2000

Try coding it in LeetCode

Maximum Value of K Coins From Piles

Hard

Asked by:

28 views

Topics:

Dynamic Programming

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.

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.length
1 <= n <= 1000
1 <= piles[i][j] <= 10⁵
1 <= k <= sum(piles[i].length) <= 2000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of piles and the number of coins in each pile? What is the maximum value of k?
Can the coin values be zero or negative?
If k is zero, should I return zero or is it an invalid input?
If the total number of coins across all piles is less than k, should I return the maximum possible value or is it an invalid input?
Are the piles guaranteed to be non-empty, or could there be empty piles in the input?

Brute Force Solution

Approach

The brute force way to solve this coin problem is to explore absolutely every possible combination of coins we could pick from the given piles. We'll look at every way to choose some coins from some of the piles, making sure we don't pick more coins than we're allowed overall.

Here's how the algorithm would work step-by-step:

Start by considering the first pile and how many coins to take from it: maybe zero, maybe one, maybe two, and so on, up to the total number of coins in that pile.
For each of those choices of how many coins to take from the first pile, now consider the second pile. Again, explore taking zero coins, one coin, two coins, and so on, up to the total coins in the second pile.
Keep doing this for each pile. So, for every decision about how many coins to take from the first pile AND how many from the second pile, explore all possibilities for the third pile, and so on.
Each time we make a decision about how many coins to take from each pile, we must keep track of the *total* number of coins we've taken so far.
If, at any point, the total number of coins we've taken exceeds the limit we're allowed to take, we have to discard that path and try something else.
Whenever we reach the end of the piles (meaning we've considered how many coins to take from *every* pile) and the number of coins taken is still under our allowed maximum, we note the total value of the coins we have.
After exhaustively trying every single possible combination of coins from all the piles, we compare all the total values we recorded.
The largest of these values is the maximum value we can obtain, and that's our answer.

Code Implementation

def max_value_of_k_coins_brute_force(piles, max_coins_to_take):
    maximum_value = 0

    def solve(pile_index, coins_taken, current_value):
        nonlocal maximum_value

        # Base case: If we've processed all piles
        if pile_index == len(piles):
            # Update the maximum value if possible.
            maximum_value = max(maximum_value, current_value)
            return

        # Iterate through possible number of coins to take from the current pile
        for coins_to_take_from_pile in range(min(len(piles[pile_index]), max_coins_to_take - coins_taken) + 1):
            next_coins_taken = coins_taken + coins_to_take_from_pile
            next_value = current_value

            # Calculate the value of the coins taken from the current pile
            for coin_index in range(coins_to_take_from_pile):
                next_value += piles[pile_index][coin_index]

            # Explore the next pile with updated coins taken and value
            solve(pile_index + 1, next_coins_taken, next_value)

    # Start the recursion from the first pile with no coins taken.
    solve(0, 0, 0)

    return maximum_value

Big(O) Analysis

Time Complexity

O(nk) – Let 'n' be the number of piles and 'k' be the maximum number of coins allowed. The algorithm explores every possible combination of coins from each pile. For each pile, we can choose 0 to k coins (or the pile's size if it's smaller than k). Because we have 'n' piles, and for each pile we're exploring up to 'k' options, in the worst-case, the algorithm has a branching factor of 'k' at each of the 'n' levels of recursion. Therefore, we could consider k^n possibilities. More precisely, the number of operations depends on the size of each pile, but in the worst case we perform k operations for each of the n piles. Therefore, the total time complexity is O(nk).

Space Complexity

O(K) – The brute force approach described uses recursion to explore all possible combinations of coins. In the worst-case scenario, the recursion depth can reach the number of piles, let's denote it by K, as we consider each pile one by one. Each recursive call adds a new frame to the call stack, storing local variables and the return address. Therefore, the auxiliary space is determined by the maximum depth of the recursion, which is proportional to the number of piles K, resulting in a space complexity of O(K).

Optimal Solution

Approach

We want to find the maximum total value of coins we can collect from different piles, given a limit on how many coins we can take. We'll use a strategy that builds up the best solution gradually by considering each pile and the number of coins we can take from it, storing the best results along the way.

Here's how the algorithm would work step-by-step:

Imagine you have a chart that stores the best possible coin value you can achieve for each number of coins you're allowed to take and for each pile you've considered so far.
Start with the first pile. For each possible number of coins you could take from this pile (from zero up to the maximum available in the pile), calculate the total value of those coins and store it in the chart.
Move to the second pile. For each possible number of coins you could take from *this* pile, add that to the best coin values you've already calculated for the *previous* piles, considering all possible combinations that don't exceed your total coin limit. Update the chart to store the new best values.
Repeat this process for each pile, always updating the chart with the maximum coin value you can achieve for each number of coins you're allowed to take, considering all the piles you've looked at so far.
Once you've processed all the piles, the final entry in the chart corresponding to your maximum allowed number of coins will contain the overall maximum value you can obtain.

Code Implementation

def maximum_value_of_k_coins_from_piles(piles, max_coins_to_take):
    number_of_piles = len(piles)
    # dp[i][j] stores max value using first i piles and j coins.
    dp_table = [[0] * (max_coins_to_take + 1) for _ in range(number_of_piles + 1)]

    for pile_index in range(1, number_of_piles + 1):
        for coins_taken in range(max_coins_to_take + 1):
            # Not taking any coins from the current pile.
            dp_table[pile_index][coins_taken] = dp_table[pile_index - 1][coins_taken]
            current_pile_sum = 0
            for number_of_coins_from_current_pile in range(1, min(len(piles[pile_index - 1]) + 1, coins_taken + 1)):

                current_pile_sum += piles[pile_index - 1][number_of_coins_from_current_pile - 1]
                # Update dp_table with the maximum value by taking coins from current pile
                if coins_taken >= number_of_coins_from_current_pile:
                    dp_table[pile_index][coins_taken] = max(dp_table[pile_index][coins_taken],
                                                    dp_table[pile_index - 1][coins_taken - number_of_coins_from_current_pile] + current_pile_sum)

    # The result is stored in the last cell of the table.
    return dp_table[number_of_piles][max_coins_to_take]

Big(O) Analysis

Time Complexity

O(n*k) – Let n be the number of piles and k be the maximum number of coins we can take. The outer loop iterates through each of the n piles. The inner loop iterates through all possible numbers of coins to take from the current pile. For each pile, we potentially iterate up to k times to update the chart with the best coin values achievable so far. Thus the overall time complexity is O(n*k).

Space Complexity

O(n*k) – The algorithm utilizes a chart (which can be represented as a 2D array or matrix) to store the best possible coin value for each number of coins allowed (up to k) and for each pile considered. The dimensions of this chart are determined by the number of piles (let's denote it as n) and the maximum number of coins we can take (k). Therefore, the space required to store this chart is proportional to n multiplied by k. This auxiliary space directly corresponds to the temporary storage of intermediate results as the algorithm builds up the solution, pile by pile.

Edge Cases

Case	How to Handle
Empty list of piles	Return 0, as no coins can be taken from empty piles.
k is zero	Return 0, as no coins can be taken if the limit is zero.
Piles are empty lists	Treat empty piles as having no coins and proceed with the remaining piles.
k is greater than the total number of coins in all piles	Sum all coins from all piles as that will be the maximum possible value.
A pile has a very large number of coins	Ensure that prefix sum calculations for a single pile do not cause an integer overflow.
Piles contain a mix of very small and very large coin values	The algorithm should correctly select the piles based on overall optimal sum and not be biased by the presence of extremely small or large individual coin values using DP.
k is very large, and the number of piles is also very large	Optimization of the dynamic programming solution is crucial to avoid exceeding time or memory limits.
A pile has coins with zero value.	Include zero value coins in the prefix sum calculations without affecting the correctness of the maximum value.

Empty list of piles

How to Handle:

Return 0, as no coins can be taken from empty piles.

k is zero

How to Handle:

Return 0, as no coins can be taken if the limit is zero.

Piles are empty lists

How to Handle:

Treat empty piles as having no coins and proceed with the remaining piles.

k is greater than the total number of coins in all piles

How to Handle:

Sum all coins from all piles as that will be the maximum possible value.

A pile has a very large number of coins

How to Handle:

Ensure that prefix sum calculations for a single pile do not cause an integer overflow.

Piles contain a mix of very small and very large coin values

How to Handle:

The algorithm should correctly select the piles based on overall optimal sum and not be biased by the presence of extremely small or large individual coin values using DP.

k is very large, and the number of piles is also very large

How to Handle:

Optimization of the dynamic programming solution is crucial to avoid exceeding time or memory limits.

A pile has coins with zero value.

How to Handle:

Include zero value coins in the prefix sum calculations without affecting the correctness of the maximum value.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of piles and the number of coins in each pile? What is the maximum value of k?
Can the coin values be zero or negative?
If k is zero, should I return zero or is it an invalid input?
If the total number of coins across all piles is less than k, should I return the maximum possible value or is it an invalid input?
Are the piles guaranteed to be non-empty, or could there be empty piles in the input?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the first pile and how many coins to take from it: maybe zero, maybe one, maybe two, and so on, up to the total number of coins in that pile.
For each of those choices of how many coins to take from the first pile, now consider the second pile. Again, explore taking zero coins, one coin, two coins, and so on, up to the total coins in the second pile.
Keep doing this for each pile. So, for every decision about how many coins to take from the first pile AND how many from the second pile, explore all possibilities for the third pile, and so on.
Each time we make a decision about how many coins to take from each pile, we must keep track of the *total* number of coins we've taken so far.
If, at any point, the total number of coins we've taken exceeds the limit we're allowed to take, we have to discard that path and try something else.
Whenever we reach the end of the piles (meaning we've considered how many coins to take from *every* pile) and the number of coins taken is still under our allowed maximum, we note the total value of the coins we have.
After exhaustively trying every single possible combination of coins from all the piles, we compare all the total values we recorded.
The largest of these values is the maximum value we can obtain, and that's our answer.

Code Implementation

def max_value_of_k_coins_brute_force(piles, max_coins_to_take):
    maximum_value = 0

    def solve(pile_index, coins_taken, current_value):
        nonlocal maximum_value

        # Base case: If we've processed all piles
        if pile_index == len(piles):
            # Update the maximum value if possible.
            maximum_value = max(maximum_value, current_value)
            return

        # Iterate through possible number of coins to take from the current pile
        for coins_to_take_from_pile in range(min(len(piles[pile_index]), max_coins_to_take - coins_taken) + 1):
            next_coins_taken = coins_taken + coins_to_take_from_pile
            next_value = current_value

            # Calculate the value of the coins taken from the current pile
            for coin_index in range(coins_to_take_from_pile):
                next_value += piles[pile_index][coin_index]

            # Explore the next pile with updated coins taken and value
            solve(pile_index + 1, next_coins_taken, next_value)

    # Start the recursion from the first pile with no coins taken.
    solve(0, 0, 0)

    return maximum_value

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a chart that stores the best possible coin value you can achieve for each number of coins you're allowed to take and for each pile you've considered so far.
Start with the first pile. For each possible number of coins you could take from this pile (from zero up to the maximum available in the pile), calculate the total value of those coins and store it in the chart.
Move to the second pile. For each possible number of coins you could take from *this* pile, add that to the best coin values you've already calculated for the *previous* piles, considering all possible combinations that don't exceed your total coin limit. Update the chart to store the new best values.
Repeat this process for each pile, always updating the chart with the maximum coin value you can achieve for each number of coins you're allowed to take, considering all the piles you've looked at so far.
Once you've processed all the piles, the final entry in the chart corresponding to your maximum allowed number of coins will contain the overall maximum value you can obtain.

Code Implementation

def maximum_value_of_k_coins_from_piles(piles, max_coins_to_take):
    number_of_piles = len(piles)
    # dp[i][j] stores max value using first i piles and j coins.
    dp_table = [[0] * (max_coins_to_take + 1) for _ in range(number_of_piles + 1)]

    for pile_index in range(1, number_of_piles + 1):
        for coins_taken in range(max_coins_to_take + 1):
            # Not taking any coins from the current pile.
            dp_table[pile_index][coins_taken] = dp_table[pile_index - 1][coins_taken]
            current_pile_sum = 0
            for number_of_coins_from_current_pile in range(1, min(len(piles[pile_index - 1]) + 1, coins_taken + 1)):

                current_pile_sum += piles[pile_index - 1][number_of_coins_from_current_pile - 1]
                # Update dp_table with the maximum value by taking coins from current pile
                if coins_taken >= number_of_coins_from_current_pile:
                    dp_table[pile_index][coins_taken] = max(dp_table[pile_index][coins_taken],
                                                    dp_table[pile_index - 1][coins_taken - number_of_coins_from_current_pile] + current_pile_sum)

    # The result is stored in the last cell of the table.
    return dp_table[number_of_piles][max_coins_to_take]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty list of piles	Return 0, as no coins can be taken from empty piles.
k is zero	Return 0, as no coins can be taken if the limit is zero.
Piles are empty lists	Treat empty piles as having no coins and proceed with the remaining piles.
k is greater than the total number of coins in all piles	Sum all coins from all piles as that will be the maximum possible value.
A pile has a very large number of coins	Ensure that prefix sum calculations for a single pile do not cause an integer overflow.
Piles contain a mix of very small and very large coin values	The algorithm should correctly select the piles based on overall optimal sum and not be biased by the presence of extremely small or large individual coin values using DP.
k is very large, and the number of piles is also very large	Optimization of the dynamic programming solution is crucial to avoid exceeding time or memory limits.
A pile has coins with zero value.	Include zero value coins in the prefix sum calculations without affecting the correctness of the maximum value.

Empty list of piles

How to Handle:

Return 0, as no coins can be taken from empty piles.

k is zero

How to Handle:

Return 0, as no coins can be taken if the limit is zero.

Piles are empty lists

How to Handle:

Treat empty piles as having no coins and proceed with the remaining piles.

k is greater than the total number of coins in all piles

How to Handle:

Sum all coins from all piles as that will be the maximum possible value.

A pile has a very large number of coins

How to Handle:

Ensure that prefix sum calculations for a single pile do not cause an integer overflow.

Piles contain a mix of very small and very large coin values

How to Handle:

The algorithm should correctly select the piles based on overall optimal sum and not be biased by the presence of extremely small or large individual coin values using DP.

k is very large, and the number of piles is also very large

How to Handle:

Optimization of the dynamic programming solution is crucial to avoid exceeding time or memory limits.

A pile has coins with zero value.

How to Handle:

Include zero value coins in the prefix sum calculations without affecting the correctness of the maximum value.