29. Minimum Cost to Connect Sticks

hardAsked at Booking

Minimize total cost of merging elements pairwise — Booking's pricing engine applies this greedy min-heap strategy when combining hotel price segments into bundled travel packages to keep the aggregation cost as low as possible.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

You have some sticks with positive integer lengths. You can connect any two sticks to form a longer stick; the cost equals the sum of those two lengths. Return the minimum cost to connect all sticks into one.

Constraints

1 <= sticks.length <= 10^4
1 <= sticks[i] <= 10^4

Examples

Example 1

Input

sticks = [2,4,3]

Output

Explanation: Connect 2+3=5 (cost 5), then 4+5=9 (cost 9). Total = 14.

Example 2

Input

sticks = [1,8,3,5]

Output

Example 3

Input

sticks = [5]

Output

Approaches

1. Sort and merge (greedy, suboptimal)

Always merge the two smallest. Re-sort after each merge. Correct answer but O(n^2 log n).

Time: O(n^2 log n)
Space: O(n)

function connectSticks(sticks) {
  let cost = 0;
  while (sticks.length > 1) {
    sticks.sort((a, b) => a - b);
    const merged = sticks[0] + sticks[1];
    cost += merged;
    sticks = [merged, ...sticks.slice(2)];
  }
  return cost;
}

Tradeoff:

2. Min-heap (Huffman coding insight)

Insert all values into a min-heap. Repeatedly extract the two smallest, merge them, add the cost, and push the result back. O(n log n) total — same structure as Huffman encoding.

Time: O(n log n)
Space: O(n)

class MinHeap {
  constructor() { this.h = []; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2*i+1, r = 2*i+2;
        if (l < this.h.length && this.h[l] < this.h[s]) s = l;
        if (r < this.h.length && this.h[r] < this.h[s]) s = r;
        if (s === i) break;
        [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
        i = s;
      }
    }
    return top;
  }
  get size() { return this.h.length; }
}

function connectSticks(sticks) {
  const heap = new MinHeap();
  for (const s of sticks) heap.push(s);
  let cost = 0;
  while (heap.size > 1) {
    const merged = heap.pop() + heap.pop();
    cost += merged;
    heap.push(merged);
  }
  return cost;
}

Tradeoff:

Booking-specific tips

Booking explicitly mentions Huffman-style cost aggregation in some interview rounds for their pricing science team. If you name the Huffman analogy upfront, you signal pattern depth. Always implement a real MinHeap in JS interviews — using Array.sort() inside the loop will fail large-n performance checks.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Minimum Cost to Connect Sticks and other Booking interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →