Sponsored
Sponsored
This approach involves sorting the piles of coins first. After sorting, one can consistently select the second largest pile from each group of three piles (Alice's bigger pile, your pile, and Bob's smaller pile) to maximize your coins.
By sorting the piles in descending order, the strategy becomes easier. Alice will always pick the first pile, you will always pick the second pile, and Bob will take the third.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
1using System;
2using System.Linq;
3
4public class Solution {
5 public int MaxCoins(int[] piles) {
6 Array.Sort(piles);
7 int result = 0;
8 int n = piles.Length / 3;
9 for (int i = n; i < piles.Length; i += 2) {
10 result += piles[i];
11 }
12 return result;
13 }
14 public static void Main() {
15 int[] piles = new int[] {2, 4, 1, 2, 7, 8};
16 Solution sol = new Solution();
17 Console.WriteLine(sol.MaxCoins(piles));
18 }
19}We sort the array using C#'s Array class sort method and loop over the sorted array, starting from the n (1/3 size of the array) position and adding every alternate pile's coins to our result.
Another approach, although less direct than sorting, involves analyzing the positions of piles through controlled index manipulation to ensure Alice always takes the maximum pile, you take the second, and Bob takes the least of the three for every set of operations.
Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.
1
Sort the array in descending order. You'll manipulate the index to "skip" the maximum pile (chosen by Alice), select the second, and continue, excluding the least of the three per group chosen by Bob.