1561. Maximum Number of Coins You Can Get

📝 Problem Details

• Title: 1561. Maximum Number of Coins You Can Get
• Link: https://leetcode.com/problems/maximum-number-of-coins-you-can-get/
• Difficulty: Medium
• Tags/Categories: Sorting Greedy

💭What Were My Initial Thoughts?

- fixed-size sliding window to iterate through the piles choosing the 2nd best pile for each window
- sorting the piles would allow for a greedy approach
- the sliding is not needed as we can just emulate this with our for loop condition skipping unwanted elements

🤔What Did I Struggle With?

~ i dont believe i confirmed the sorted/unsorted nature of the piles during the mock, which is the key part to solving the problem

💡 Explanation of Solution

- sort the piles
- start with the second-to-last element 
- iterate backward through the piles, jumping 2 indices per step
- accumulate the values from these positions into maxCoins
- stop when you have selected n/3 elements (as one-third of the piles go to your friends)

⌛ Complexity Analysis

Time Complexity: O(n log n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        sort(piles.begin(), piles.end()); // Step 1: Sort the piles
        int n = piles.size();
        int maxCoins = 0;
 
        // Step 2: Pick the second largest pile in each triplet
        for (int i = n - 2; i >= n / 3; i -= 2) {
            maxCoins += piles[i];
        }
 
        return maxCoins; // Return the total coins
    }
};