Coin Piles

JavaView on GFG

Intuition

Find maximum coins collectible where you pick coins from adjacent piles with given rules.

Algorithm

1DP or greedy based on problem constraints. If picking alternating: max sum of every other element.

Common Pitfalls

•Read constraints carefully: specific rule about which piles can be combined. Often a DP on sorted piles.

Coin Piles.java

Java

// Approach: Sort piles. Use greedy or binary search to find the minimum required removals.
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {
    public int minimumCoins(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);

        int[] subset = new int[n];
        subset[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--)
            subset[i] = arr[i] + subset[i + 1];

        int min = Integer.MAX_VALUE;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            int ind = findUpper(arr, arr[i] + k, i, n - 1);
            if (ind == -1) {
                min = Math.min(min, sum);
                continue;
            }

            int curr = subset[ind] - ((n - ind) * (arr[i] + k));
            curr += sum;
            min = Math.min(min, curr);
            sum += arr[i];
        }

        return min;
    }

    int findUpper(int[] arr, int target, int s, int e) {

        int ans = -1;

        while (s <= e) {
            int mid = (s + e) / 2;
            if (arr[mid] > target) {
                ans = mid;
                e = mid - 1;
            } else
                s = mid + 1;

        }
        
        return ans;
    }
}

Was this solution helpful?