17. Coin Piles
✅ GFG solution to the Coin Piles problem: minimize coins removed to maintain difference ≤ k between any two piles using sliding window technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array arr[]
of integers, where each element represents the number of coins in a pile. You are also given an integer k
. Your task is to remove the minimum number of coins such that the absolute difference between the number of coins in any two updated piles is at most k.
Note: You can also remove a pile by removing all the coins of that pile.
📘 Examples
Example 1
Input: arr[] = [2, 2, 2, 2], k = 0
Output: 0
Explanation: For any two piles the difference in the number of coins is <= 0.
So no need to remove any coin.
Example 2
Input: arr[] = [1, 5, 1, 2, 5, 1], k = 3
Output: 2
Explanation: If we remove one coin each from both the piles containing 5 coins,
then for any two piles the absolute difference in the number of coins is <= 3.
🔒 Constraints
$1 \le \text{arr.size()} \le 10^5$
$1 \le \text{arr}[i] \le 10^4$
$0 \le k \le 10^4$
✅ My Approach
The optimal approach uses Sorting combined with Sliding Window technique to find the minimum coins to remove:
Sliding Window with Range Optimization
Sort the Array:
Sort the array to group similar pile sizes together.
This allows us to consider contiguous ranges where max - min ≤ k.
Calculate Total Sum:
Store the total sum of all coins for reference.
This helps in calculating removal costs efficiently.
Sliding Window Technique:
For each possible starting position
s
, find the maximum range[s, e)
wherearr[e-1] - arr[s] ≤ k
.All piles in this range can coexist without violating the constraint.
Optimization Strategy:
Keep piles in range: Sum of coins in window
[s, e)
.Remove prefix: All coins before position
s
.Adjust suffix: Reduce piles after position
e
toarr[s] + k
(or remove if too small).
Cost Calculation:
Prefix removal cost: Sum of
arr[0]
toarr[s-1]
Window preservation: Keep all coins in
[s, e)
Suffix adjustment:
max(0, remaining_sum - (n-e) * (arr[s] + k))
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n log n), where n is the array size. Sorting takes O(n log n) and the sliding window traversal takes O(n) with each element visited at most twice.
Expected Auxiliary Space Complexity: O(1), as we only use constant extra space for variables (excluding the input array sorting space).
🧑💻 Code (C++)
class Solution {
public:
int minimumCoins(vector<int>& a, int k) {
sort(a.begin(), a.end());
int n = a.size(), t = accumulate(a.begin(), a.end(), 0), res = t, w = 0, p = 0, e = 0;
for (int s = 0; s < n; s++) {
while (e < n && a[e] - a[s] <= k) w += a[e++];
int r = max(0, (t - p - w) - (n - e) * (a[s] + k));
res = min(res, p + r);
if (e == s) e++; else w -= a[s];
p += a[s];
}
return res;
}
};
🧑💻 Code (Java)
class Solution {
public int minimumCoins(int[] a, int k) {
Arrays.sort(a);
int n = a.length, t = Arrays.stream(a).sum(), res = t, w = 0, p = 0, e = 0;
for (int s = 0; s < n; s++) {
while (e < n && a[e] - a[s] <= k) w += a[e++];
int r = Math.max(0, (t - p - w) - (n - e) * (a[s] + k));
res = Math.min(res, p + r);
if (e == s) e++; else w -= a[s];
p += a[s];
}
return res;
}
}
🐍 Code (Python)
class Solution:
def minimumCoins(self, a, k):
a.sort()
n, t, res, w, p, e = len(a), sum(a), sum(a), 0, 0, 0
for s in range(n):
while e < n and a[e] - a[s] <= k:
w += a[e]
e += 1
r = max(0, (t - p - w) - (n - e) * (a[s] + k))
res = min(res, p + r)
if e == s: e += 1
else: w -= a[s]
p += a[s]
return res
🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated