Maximum Number of Coins You Can Get

Medium

Asked by:

12 views

Topics:

ArraysGreedy AlgorithmsArrays

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

In each step, you will choose any 3 piles of coins (not necessarily consecutive).
Of your choice, Alice will pick the pile with the maximum number of coins.
You will pick the next pile with the maximum number of coins.
Your friend Bob will pick the last pile.
Repeat until there are no more piles of coins.

Given an array of integers piles where piles[i] is the number of coins in the i^th pile.

Return the maximum number of coins that you can have.

Example 1:

Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.

Example 2:

Input: piles = [2,4,5]
Output: 4

Example 3:

Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18

Constraints:

3 <= piles.length <= 10⁵
piles.length % 3 == 0
1 <= piles[i] <= 10⁴

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 size of the `piles` array, and the value of each element in `piles`?
Can the number of piles (`n`) ever be zero, or can I assume `n` will always be a positive integer?
Are the values in the `piles` array guaranteed to be non-negative integers?
If there are multiple ways to choose piles to maximize my coins, is any valid solution acceptable?
Could you provide an example input, say for n=5, and the expected corresponding optimal output?

Brute Force Solution

Approach

The brute force method for this coin problem means trying every possible combination of taking piles of coins for you, your friend, and the remaining piles for someone else. We'll check which of these combinations gives you the most coins.

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

Imagine all the piles of coins laid out.
Pick every possible group of piles that you could take.
For each of these possible choices of your piles, then pick every possible group of piles that your friend could take from the remaining piles.
Whatever piles are left after you and your friend choose go to someone else.
For each choice of piles for you and your friend, calculate how many coins you would get.
Keep track of the choice that results in you getting the most coins.
After considering every single possible choice, tell me the most coins you could get.

Code Implementation

def max_coins_brute_force(piles):	maximum_coins = 0

	# Iterate through all possible combinations for your piles
	for i in range(1 << len(piles)):
		your_piles = []
		friends_piles = []
		other_piles = []
		current_coins = 0

		# Assign piles based on the current combination
		for pile_index in range(len(piles)):
			# The 'i' variable represents our potential piles
			if (i >> pile_index) & 1:
				your_piles.append(piles[pile_index])
			else:
				remaining_piles = piles[:pile_index] + piles[pile_index+1:]
				friend_assigned = False
				#Assign friends piles
				for j in range(1 << len(remaining_piles)):
					friends_piles_inner = []
					others_piles_inner = []
					for remaining_index in range(len(remaining_piles)):
						if (j >> remaining_index) & 1:
							friends_piles_inner.append(remaining_piles[remaining_index])
						else:
							others_piles_inner.append(remaining_piles[remaining_index])
					#Calculate total for the current combination
					current_coins = sum(your_piles)

					#Update maximum coins earned
					maximum_coins = max(maximum_coins, current_coins)

	return maximum_coins

Big(O) Analysis

Time Complexity

O(3^n) – The brute force approach considers every possible combination of pile selections for you, your friend, and the remaining piles. This involves iterating through all possible subsets of the piles. For each pile, there are three choices: you take it, your friend takes it, or the third person takes it. Since there are n piles, this leads to 3^n possible combinations. Therefore, the time complexity is O(3^n).

Space Complexity

O(1) – The brute force approach, as described, does not use any significant auxiliary space. It iterates through different combinations without storing them explicitly. The space needed for simple variables like the maximum coins found so far remains constant regardless of the input size N (the number of piles).

Optimal Solution

Approach

The best way to maximize your coins is to focus on always picking the best possible pile for yourself. We can do this by focusing on what piles the worst possible picker will take, so we can avoid those piles.

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

First, organize all the coin piles from smallest to largest.
Imagine three players are picking piles, including you.
Realize that you never want the weakest player to get the biggest pile.
You should always pick the second largest pile out of every three.
The weakest player will always take the smallest, and the other player will take the largest.
So, select the second largest pile from the right end of the list.
Move down the list of piles, skipping one at the end each time, and grabbing the second largest remaining pile.
Sum up all the piles you selected, and that will be the maximum number of coins you can obtain.

Code Implementation

def maximum_number_of_coins_you_can_get(piles):    piles.sort()
    number_of_piles = len(piles)
    my_coins = 0
    left_index = 0
    right_index = number_of_piles - 1
    
    # We iterate while we have at least 3 piles remaining.
    while left_index < right_index:
        # We always pick the second largest from the remaining piles
        my_coins += piles[right_index - 1]
        
        # Move the left pointer to avoid smallest piles.
        left_index += 1
        
        # Decrement right pointer by 2 since other players pick one each
        right_index -= 2

    return my_coins

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this solution is sorting the input array of size n in the first step. Common sorting algorithms like merge sort or quicksort have a time complexity of O(n log n). The subsequent steps involve iterating through a portion of the sorted array, which takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step. Therefore the Big O time complexity is O(n log n).

Space Complexity

O(1) – The provided solution sorts the input piles in place. Beyond the input array, only a few constant space variables are used to iterate and sum the selected piles. These variables don't depend on the number of piles, N. Therefore, the auxiliary space complexity is constant, regardless of the input size.

Edge Cases

Case	How to Handle
Null or empty piles array	Return 0 immediately as there are no piles to collect from.
piles array with only one or two elements	If the length is 1 or 2, return 0, as you need at least 3 piles to execute a turn.
piles array with maximum size (e.g., 10^5)	Ensure the algorithm's time complexity is efficient (O(n log n) or better) to avoid exceeding time limits by using sorting.
piles array contains all identical values	The sorting step should correctly handle this case, distributing coins evenly, but ensure the indexing logic is correct after sorting.
piles array contains negative numbers	The problem statement doesn't specify this so assume positive numbers but clarify with the interviewer, and if negative, ensure the solution handles negative pile sizes by either throwing an exception or returning 0 as an error condition.
piles array contains zero values	The algorithm should function correctly with zero-value piles, as they would just contribute nothing to the total sum.
Integer overflow when calculating the sum of coins	Use long long integers for accumulating the sum if the individual pile values or the number of piles are large enough to cause an overflow with regular integers.
piles array is already sorted in descending order	The sorting algorithm should still execute correctly, albeit potentially less efficiently, and the coin selection logic should proceed as intended.

Null or empty piles array

How to Handle:

Return 0 immediately as there are no piles to collect from.

piles array with only one or two elements

How to Handle:

If the length is 1 or 2, return 0, as you need at least 3 piles to execute a turn.

piles array with maximum size (e.g., 10^5)

How to Handle:

Ensure the algorithm's time complexity is efficient (O(n log n) or better) to avoid exceeding time limits by using sorting.

piles array contains all identical values

How to Handle:

The sorting step should correctly handle this case, distributing coins evenly, but ensure the indexing logic is correct after sorting.

piles array contains negative numbers

How to Handle:

The problem statement doesn't specify this so assume positive numbers but clarify with the interviewer, and if negative, ensure the solution handles negative pile sizes by either throwing an exception or returning 0 as an error condition.

piles array contains zero values

How to Handle:

The algorithm should function correctly with zero-value piles, as they would just contribute nothing to the total sum.

Integer overflow when calculating the sum of coins

How to Handle:

Use long long integers for accumulating the sum if the individual pile values or the number of piles are large enough to cause an overflow with regular integers.

piles array is already sorted in descending order

How to Handle:

The sorting algorithm should still execute correctly, albeit potentially less efficiently, and the coin selection logic should proceed as intended.