Min Cost of Removing All Elements
Cost of removing A[i] = sum of all elements currently present. Find the order that minimises total cost.
TC: O(N log N)SC: O(1)
What is the cost?
When you remove an element, cost = sum of ALL elements still present at that moment. Total = sum of all removal costs.
Two Orders — A = [2, 4, 1]
Descending (4 → 2 → 1)
Remove 4: [2,4,1] → cost = 7 Remove 2: [2,1] → cost = 3 Remove 1: [1] → cost = 1 Total = 11 ← MINIMUM
Ascending (1 → 2 → 4)
Remove 1: [2,4,1] → cost = 7 Remove 2: [2,4] → cost = 6 Remove 4: [4] → cost = 4 Total = 17
💡
Removing in descending order always gives minimum cost.
Why Descending?
After sorting descending, element at index i (0-based) is counted exactly i+1 times. Larger elements removed first = counted fewer times.
✓
Formula: Total = Σ (i+1) × A[i] where A is sorted descending
Code
Java
import java.util.Arrays;
import java.util.Collections;
public long minCost(int[] A) {{
int n = A.length;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) arr[i] = A[i];
Arrays.sort(arr, Collections.reverseOrder());
long ans = 0;
for (int i = 0; i < n; i++)
ans += (long)(i + 1) * arr[i];
return ans;
}}Dry Run
Trace
Sorted descending: [4, 2, 1] index: 0, 1, 2i=0: (0+1) × 4 = 4 i=1: (1+1) × 2 = 4 i=2: (2+1) × 1 = 3 Total = 11 ✓