DSAhardArrays~40m

The Merge Queue

Problem

You are a software engineer on Google Gemini's RAG (Retrieval Augmented Generation) pipeline. Before sending documents to Gemini, your system must merge n adjacent document chunks into a single context window.

Each merge operation costs tokens equal to the total size of the two groups being merged. For example, merging a group of 10 tokens with a group of 20 tokens costs 30 tokens of compute — and that merged group of 30 tokens will be counted again in any future merge it participates in.

The order of merges matters. Merging large chunks early causes them to be counted repeatedly in subsequent merges, inflating total cost.

Given an array of chunk token counts, return the minimum total compute cost to merge all chunks into one.

Examples

Example 1

Input: [100, 10, 10]

Output: 140

Left-to-right: merge(100,10)=110, then merge(110,10)=120, total=230. Optimal: merge(10,10)=20 first, then merge(100,20)=120, total=140.

Example 2

Input: [6, 4, 4, 6]

Output: 40

Greedy (merge smallest pair 4,4 first): costs 8+14+20=42. Optimal DP: merge(6,4) and (4,6) separately costs 10+10+20=40.

Example 3

Input: [10, 10, 10, 10]

Output: 80

Optimal: split in the middle. Merge left pair (10+10=20) and right pair (10+10=20), then merge both (20+20=40). Total: 20+20+40=80.

Constraints

›1 <= n <= 300
›1 <= chunks[i] <= 1000

Loading question…