1. Introduction

The Optimal File Merge problem asks us to merge multiple files into a single file with the minimum possible total computation cost.

Each file has a certain size. When two files are merged, the cost of the operation is the sum of their sizes.

For example, if we merge files of sizes 3 and 2:

Code
Cost = 3 + 2 = 5
New file size = 5

The newly created file can then be merged with another file.

The important question is:

In which order should we merge the files so that the total cost is minimum?

The answer is to always merge the two smallest files first.

To efficiently find the two smallest files, we use a Min Heap, implemented in Java using PriorityQueue.

2. Example

Consider:

Code
files = [3, 2, 4]

There are multiple ways to merge these files.

Approach 1

Code
2 + 3 = 5
5 + 4 = 9

Total cost = 5 + 9 = 14

Approach 2

Code
3 + 4 = 7
7 + 2 = 9

Total cost = 7 + 9 = 16

Therefore:

Code
Minimum Cost = 14

The first approach is better.

3. Important Observation

The main observation is:

Always merge the two smallest files first.

Why?

Suppose we merge a large file early.

That merged file becomes part of future merge operations, so its size contributes to the cost multiple times.

By merging smaller files first, we keep the intermediate file sizes as small as possible.

This is a Greedy Algorithm.

4. Why Do We Need a Min Heap?

At every step, we need to find:

Code
Smallest file
Second smallest file

If we search the array every time, it can become inefficient.

For example, if there are n files and we repeatedly search for the smallest elements, the complexity can become large.

A Min Heap solves this efficiently.

In Java:

Java
PriorityQueue<Integer> pq = new PriorityQueue<>();

By default, Java's PriorityQueue works as a Min Heap.

Therefore:

Java
pq.poll()

always returns the smallest element.

5. Algorithm

The algorithm is simple:

Step 1

Create a Min Heap.

Step 2

Insert all file sizes into the heap.

Step 3

While there is more than one file:

  • Remove the smallest file.

  • Remove the second smallest file.

  • Add their sizes.

  • Add the merged size to the total cost.

  • Insert the merged file back into the heap.

Step 4

Return the total cost.

6. Java Code

Java
import java.util.PriorityQueue;

class Solution {
    public int minComputation(int[] files) {

        // Create a Min Heap
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add all file sizes to the heap
        for (int file : files) {
            pq.add(file);
        }

        int totalCost = 0;

        // Continue until only one file remains
        while (pq.size() > 1) {

            // Get the two smallest files
            int x = pq.poll();
            int y = pq.poll();

            // Merge the two files
            int merged = x + y;

            // Add merge cost
            totalCost += merged;

            // Add the merged file back to the heap
            pq.add(merged);
        }

        return totalCost;
    }
}

7. Code Explanation

Let's understand each part of the code.

Creating the Min Heap

Java
PriorityQueue<Integer> pq = new PriorityQueue<>();

Java's PriorityQueue automatically keeps the smallest element at the top.

For example:

Code
Input:
[3, 2, 4]

Min Heap:
2
3
4

So:

Java
pq.poll();

returns:

Code
2

Adding Files

Java
for (int file : files) {
    pq.add(file);
}

Every file size is inserted into the priority queue.

For:

Code
files = [2, 3, 6, 5, 7, 4]

The heap contains all six values.

The important point is that we don't need to manually sort the array.

Loop Condition

Java
while (pq.size() > 1)

We continue merging as long as there are at least two files.

When only one file remains, all files have been merged.

Getting the Two Smallest Files

Java
int x = pq.poll();
int y = pq.poll();

Because pq is a Min Heap:

Code
x = smallest
y = second smallest

For example:

Code
Heap = [2, 3, 4, 5, 6, 7]

x = 2
y = 3

Merging

Java
int merged = x + y;

If:

Code
x = 2
y = 3

then:

Code
merged = 5

The merge operation costs 5.

Adding to Total Cost

Java
totalCost += merged;

The cost of each merge is added to the answer.

For example:

Code
First merge = 5
Second merge = 9
Third merge = 11
...

The final answer is the sum of all these merge costs.

Adding the Merged File Back

Java
pq.add(merged);

This step is very important.

After merging:

Code
2 + 3 = 5

we now have a new file of size 5.

That file must be available for future merging.

Therefore, we put it back into the heap.

8. Complete Dry Run

Let's take:

Code
files = [2, 3, 6, 5, 7, 4]

Initially:

Code
[2, 3, 4, 5, 6, 7]

Step 1

Take two smallest:

Code
2 + 3 = 5

Cost:

Code
5

Heap becomes:

Code
[4, 5, 5, 6, 7]

Step 2

Take two smallest:

Code
4 + 5 = 9

Cost:

Code
9

Total:

Code
5 + 9 = 14

Heap:

Code
[5, 6, 7, 9]

Step 3

Take:

Code
5 + 6 = 11

Cost:

Code
11

Total:

Code
14 + 11 = 25

Heap:

Code
[7, 9, 11]

Step 4

Take:

Code
7 + 9 = 16

Cost:

Code
16

Total:

Code
25 + 16 = 41

Heap:

Code
[11, 16]

Step 5

Take:

Code
11 + 16 = 27

Cost:

Code
27

Total:

Code
41 + 27 = 68

Now only one file remains.

Therefore:

Code
Answer = 68

9. Why Is This a Greedy Algorithm?

A Greedy Algorithm makes the best possible choice at the current step.

Here, our choice is:

Code
Choose the two smallest files.

We don't try every possible merging order.

Instead, we make the locally optimal choice at every step.

For this problem, this greedy strategy produces the globally optimal result.

This is the same basic idea used in:

  • Huffman Coding

  • Connect Ropes

  • Minimum Cost of Connecting Ropes

  • Optimal Merge Pattern

10. Edge Cases

Case 1: Only One File

Code
files = [10]

There is nothing to merge.

So:

Code
Answer = 0

The code handles this automatically because:

Java
while (pq.size() > 1)

is false.

Case 2: Two Files

Code
files = [5, 7]

Only one merge is required:

Code
5 + 7 = 12

Answer:

Code
12

Case 3: Equal File Sizes

Code
files = [5, 5, 5, 5]

The algorithm still works correctly:

Code
5 + 5 = 10
5 + 5 = 10
10 + 10 = 20

Total:

Code
10 + 10 + 20 = 40

11. Time Complexity

There are n files.

Each file is inserted into the priority queue.

Each merge performs:

Code
poll()
poll()
add()

Each PriorityQueue operation takes:

Code
O(log n)

There are approximately n - 1 merges.

Therefore:

Code
Time Complexity = O(n log n)

12. Space Complexity

The PriorityQueue can contain up to n elements.

Therefore:

Code
Space Complexity = O(n)

13. Important Interview Pattern

Whenever you see a problem like:

"Repeatedly combine two elements and minimize the total cost."

Think immediately:

Code
Min Heap
   ↓
Take two smallest
   ↓
Combine them
   ↓
Add cost
   ↓
Put result back
   ↓
Repeat

This is one of the most important Greedy + Heap patterns for coding interviews.

14. Final Takeaway

The key idea behind Optimal File Merge is very simple:

Code
Always merge the two smallest files first.

A Java PriorityQueue gives us an efficient way to find those two smallest files.

The complete pattern is:

Java
PriorityQueue<Integer> pq = new PriorityQueue<>();

for (int file : files) {
    pq.add(file);
}

int totalCost = 0;

while (pq.size() > 1) {

    int first = pq.poll();
    int second = pq.poll();

    int merged = first + second;

    totalCost += merged;

    pq.add(merged);
}

return totalCost;

Remember this formula:

Minimum Merge Cost = Repeatedly merge the two smallest elements using a Min Heap.

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