373. Minimum Cost of Ropes

Given n ropes of various lengths, connect all of them into a single rope. Connecting two ropes of length a and b costs a + b, and the newly formed rope can itself be connected again. Find the minimum total cost to connect all n ropes into one.

Input: The first line contains an integer n, the number of ropes. The second line contains n space-separated integers, the length of each rope. Output: Print a single integer - the minimum total cost to connect all ropes into one.

1 <= n <= 10^5

This problem is structurally identical to 'Minimum Cost to Connect N Ropes' seen in the Heap category - the same greedy-plus-min-heap technique applies directly, since minimizing connection cost naturally falls under both categorizations.

Connect several ropes into one, minimizing the total cost, where connecting two ropes costs the sum of their lengths. Brute force: Try every possible ORDER of connecting ropes and compute the total cost for each - this is combinatorially expensive, impractical for larger n. Optimised: Greedily always connecting the two CURRENTLY SHORTEST ropes minimizes total cost, since a shorter rope's length gets 'counted' in fewer total future connections - a min-heap makes finding the two shortest ropes at every step efficient, in O(log n) per extraction.

Build a min-heap from all the rope lengths, then repeatedly pop the two smallest values, add their sum to the total cost, and push the sum back onto the heap, until only one rope remains. This achieves the same O(n log n) time as the two-queue technique but generalizes more simply - it correctly handles any future insertions of new rope lengths mid-process without relying on the special non-decreasing-merge property the two-queue trick depends on, making it the standard, simplest-to-implement optimal solution. Time: O(n log n) Space: O(n)

Repeatedly scan the full list of remaining rope lengths to find the two smallest ones, add their sum to the running total cost, remove those two lengths, and insert the new combined rope length back into the list; repeat until only one rope remains. This directly follows the greedy rule of always combining the two currently-cheapest ropes, but finding the two minimums by rescanning the whole list every time makes each of the n-1 merge steps cost O(n). Time: O(n^2) Space: O(n)

Sort all rope lengths once in ascending order, then maintain two queues: the original sorted lengths, and a second queue that accumulates the sums produced by merges so far. At each step, look at the fronts of both queues, take the two smallest values across them (which is always achievable in O(1) because both queues are individually non-decreasing), combine them, and push the result to the back of the merged-sums queue. Because merged values are always at least as large as what produced them, this two-queue merge never needs random access or re-sorting, letting the whole process run in O(n log n) dominated purely by the initial sort. Time: O(n log n) Space: O(n)

1. Maintain a min-heap of all rope lengths. 2. Repeatedly extract the TWO SHORTEST ropes, connect them (adding their combined length to a running total cost), and push the newly combined rope back into the heap. 3. Continue until only one rope remains in the heap.

Time: O(n log n) - there are n-1 total connections needed, each involving O(log n) heap operations. Space: O(n), for the heap holding all the ropes.

n = 1 (no connections needed, cost 0), n = 10^5 for min-heap performance, and multiple ropes of equal length.

Be ready to explain this is the exact same underlying idea as Huffman coding's core merge step (always combine the two smallest-weight nodes) - a strong pattern-recognition signal connecting a standalone puzzle to a fundamental algorithm.