Crack the Backend

Problem Statement

You have some sticks with positive lengths in sticks. In each step you may connect any two sticks into one; the cost of that step is the sum of the two lengths. Repeat until one stick remains. Return the minimum total cost to connect all sticks into one.

Key Observations

Greedy (min-heap): To minimize total cost, we should always combine the two shortest sticks first (so we don't add large lengths repeatedly). Maintain a min-heap of stick lengths. While size > 1: poll two smallest a, b, add a+b to total cost, push a+b back. This is the same structure as Huffman coding (minimize sum of (length × depth)).

Approach

High-level: Min-heap of lengths. While heap.size() > 1: a = poll(), b = poll(), cost += a+b, offer(a+b). Return cost.

Steps: PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int x : sticks) pq.offer(x); int cost = 0; while (pq.size() > 1) { int a = pq.poll(), b = pq.poll(); cost += a+b; pq.offer(a+b); } return cost;

Implementation

Java

public int connectSticks(int[] sticks) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();

    for (int s : sticks) {
        pq.offer(s);
    }

    int cost = 0;

    while (pq.size() > 1) {
        int a = pq.poll(), b = pq.poll();
        cost += a + b;
        pq.offer(a + b);
    }

    return cost;
}

Test Cases

Example 1

Input

sticks = [2,4,3]

Expected

14

Explanation

2+3=5, 5+4=9; cost 5+9=14.

Complexity Analysis

Time: typically O(n log k) or O(n log n).
Space: O(k) or O(n).

Follow-ups

Stream: process one element at a time.