177. Minimum Cost to Connect N Ropes

Given the lengths of n ropes, you may connect any two ropes into one at a cost equal to the sum of their lengths, repeating until only one rope remains. Find the minimum total cost to connect all 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 Huffman encoding's core merge step (always combine the two smallest-weight nodes) - recognizing this connection links a seemingly standalone puzzle to one of the most important greedy algorithms in computer science.

Repeatedly connect two ropes together (at a cost equal to their combined length) until only one rope remains, minimizing the total connection cost. Brute force: Try every possible ORDER of connecting ropes and compute the total cost for each - this is combinatorially expensive (many possible connection orders), impractical for larger n. Optimised: Greedily always connecting the two CURRENTLY SHORTEST ropes minimizes total cost, since a shorter rope's length gets 'counted' fewer times across the whole process (it participates in fewer total connections going forward) - a min-heap makes finding the two shortest ropes at every step efficient, in O(log n) per extraction.

Repeatedly scan the current list of rope lengths to find the two smallest values, remove them, add their sum to a running total cost, and insert the merged rope's length back into the list; repeat this n-1 times until only one rope remains. This is correct because always combining the two currently-cheapest ropes is the greedy strategy that minimizes total cost, but finding the two minimums via a fresh linear scan every single time makes each of the n-1 rounds cost O(n), adding up considerably. Time: O(n^2) Space: O(1)

Sort the rope lengths once, then maintain two queues: one holding the original sorted lengths and one holding newly created merged sums (which are always produced in non-decreasing order). At each step, take the two smallest available values by comparing only the fronts of the two queues, merge them, add the cost, and push the new sum to the back of the merged-sums queue. This is correct for the same greedy reason as before, and it is faster in practice than the heap approach because after the one-time sort, every subsequent merge only needs constant-time comparisons between queue fronts rather than a logarithmic heap insertion and removal. Time: O(n log n) Space: O(n)

Push all n rope lengths into a min-heap, then repeatedly pop the two smallest values, add their sum to the total cost, and push that sum back into the heap, continuing until only one value remains in the heap. This uses the same greedy justification as the brute force - always merging the two cheapest ropes available is optimal, proven by an exchange argument - but a min-heap gives O(log n) access to the current minimum instead of a full linear rescan, so each of the n-1 merge rounds is much cheaper. 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 ropes with equal or repeated lengths.

Be ready to explain WHY the greedy 'always connect the two shortest' strategy is provably optimal - this is essentially the same underlying idea as Huffman coding's greedy merge strategy, and mentioning that connection is a strong signal of broader algorithmic pattern recognition.