Leetcode 1561. Maximum Number of Coins You Can Get

Problem statement

https://leetcode.com/problems/maximum-number-of-coins-you-can-get/

Solution

Sort elements, then if we each time choose the smallest and two biggest piles, we will have sum(A[n//3::2]).

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def maxCoins(self, A):
        A = sorted(A)
        n = len(A)
        return sum(A[n//3::2])