1561. Maximum Number of Coins You Can Get LeetCode Solution

In this guide, you will get 1561. Maximum Number of Coins You Can Get LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Coins You Can Get problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Maximum Number of Coins You Can Get solution in C++
  4. Maximum Number of Coins You Can Get solution in Java
  5. Maximum Number of Coins You Can Get solution in Python
  6. Additional Resources
1561. Maximum Number of Coins You Can Get LeetCode Solution image

Problem Statement of Maximum Number of Coins You Can Get

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 ith 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.

See also  3261. Count Substrings That Satisfy K-Constraint II LeetCode Solution

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 <= 105
piles.length % 3 == 0
1 <= piles[i] <= 104

Complexity Analysis

  • Time Complexity: O(\texttt{sort})
  • Space Complexity: O(\texttt{sort})

1561. Maximum Number of Coins You Can Get LeetCode Solution in C++

class Solution {
 public:
  int maxCoins(vector<int>& piles) {
    ranges::sort(piles);

    int ans = 0;

    // piles = [S S M L M L], pick all the M.
    for (int i = piles.size() / 3; i < piles.size(); i += 2)
      ans += piles[i];

    return ans;
  }
};
/* code provided by PROGIEZ */

1561. Maximum Number of Coins You Can Get LeetCode Solution in Java

class Solution {
  public int maxCoins(int[] piles) {
    Arrays.sort(piles);

    int ans = 0;

    // piles = [S S M L M L], pick all the M.
    for (int i = piles.length / 3; i < piles.length; i += 2)
      ans += piles[i];

    return ans;
  }
}
// code provided by PROGIEZ

1561. Maximum Number of Coins You Can Get LeetCode Solution in Python

class Solution:
  def maxCoins(self, piles: list[int]) -> int:
    return sum(sorted(piles)[len(piles) // 3::2])
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: