PPractick

The problem

A carpenter must join n sticks into one. Joining two sticks of lengths x and y costs x + y and produces a stick of length x + y. What's the minimum total cost? Every join adds the lengths involved, and a stick's length is paid again each time its piece is joined, so long sticks should be joined as late as possible. Always join the two shortest sticks first. A min-heap does that, and this is exactly the Huffman coding construction.

Example: [1, 8, 3, 5] → 30 (1+3 = 4, 4+5 = 9, 9+8 = 17, total 4 + 9 + 17).

Function signature

long long connectSticks(const vector<int>& sticks);

Test cases

Input	Output	Explanation
[2, 4, 3]	14	2+3 = 5, then 5+4 = 9: 5 + 9
[1, 8, 3, 5]	30	4 + 9 + 17
[1, 1, 1, 1]	8	2 + 2 + 4
[3, 3, 3]	15	6 + 9
[5]	0	Nothing to join

(Confirm: lengths are positive; any two sticks can be joined; the answer can exceed 32 bits.)

How interviewers phrase it

• "Connect all the sticks into one; the cost of connecting two sticks is the sum of their lengths. Return the minimum cost" (LeetCode 1167). The GeeksforGeeks version is "Minimum Cost of ropes".

Clarifying questions to ask

1. Can any two sticks be joined, not only neighbours? (Yes. If only neighbours could be joined, it would be an interval DP.)
2. Is a single stick free? (Yes: cost 0.)
3. How large can the total get? (Use 64-bit.)

Follow-ups to expect

1. "Why is joining the two shortest optimal?"
2. "Why a min-heap?"
3. "Can you avoid the heap?"
4. "What if only adjacent sticks could be joined?"
5. "Complexity?"

Related questions

• Task Scheduler Medium
• Hand of Straights Medium
• Kadane's Algorithm Medium
• Capacity to Ship Packages Within D Days Medium
• Remove K Digits Medium
• Implement Min Heap Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in