Skip to main content
Talentd

Minimum Cost to Merge Sorted Lists - Solution & Explanation

HardArrayTwo PointersBinary SearchDynamic Programming13 min read
Practice this problem

Problem Statement

You are given a 2D integer array lists, where each lists[i] is a non-empty array of integers sorted in non-decreasing order.

You may repeatedly choose two lists a = lists[i] and b = lists[j], where i != j, and merge them. The cost to merge a and b is:

len(a) + len(b) + abs(median(a) - median(b)), where len and median denote the list length and median, respectively.

After merging a and b, remove both a and b from lists and insert the new merged sorted list in any position. Repeat merges until only one list remains.

Return an integer denoting the minimum total cost required to merge all lists into one single sorted list.

The median of an array is the middle element after sorting it in non-decreasing order. If the array has an even number of elements, the median is the left middle element.

 

Example 1:

Input: lists = [[1,3,5],[2,4],[6,7,8]]

Output: 18

Explanation:

Merge a = [1, 3, 5] and b = [2, 4]:

  • len(a) = 3 and len(b) = 2
  • median(a) = 3 and median(b) = 2
  • cost = len(a) + len(b) + abs(median(a) - median(b)) = 3 + 2 + abs(3 - 2) = 6

So lists becomes [[1, 2, 3, 4, 5], [6, 7, 8]].

Merge a = [1, 2, 3, 4, 5] and b = [6, 7, 8]:

  • len(a) = 5 and len(b) = 3
  • median(a) = 3 and median(b) = 7
  • cost = len(a) + len(b) + abs(median(a) - median(b)) = 5 + 3 + abs(3 - 7) = 12

So lists becomes [[1, 2, 3, 4, 5, 6, 7, 8]], and total cost is 6 + 12 = 18.

Example 2:

Input: lists = [[1,1,5],[1,4,7,8]]

Output: 10

Explanation:

Merge a = [1, 1, 5] and b = [1, 4, 7, 8]:

  • len(a) = 3 and len(b) = 4
  • median(a) = 1 and median(b) = 4
  • cost = len(a) + len(b) + abs(median(a) - median(b)) = 3 + 4 + abs(1 - 4) = 10

So lists becomes [[1, 1, 1, 4, 5, 7, 8]], and total cost is 10.

Example 3:

Input: lists = [[1],[3]]

Output: 4

Explanation:

Merge a = [1] and b = [3]:

  • len(a) = 1 and len(b) = 1
  • median(a) = 1 and median(b) = 3
  • cost = len(a) + len(b) + abs(median(a) - median(b)) = 1 + 1 + abs(1 - 3) = 4

So lists becomes [[1, 3]], and total cost is 4.

Example 4:

Input: lists = [[1],[1]]

Output: 2

Explanation:

The total cost is len(a) + len(b) + abs(median(a) - median(b)) = 1 + 1 + abs(1 - 1) = 2.

 

Constraints:

  • 2 <= lists.length <= 12
  • 1 <= lists[i].length <= 500
  • -109 <= lists[i][j] <= 109
  • lists[i] is sorted in non-decreasing order.
  • The sum of lists[i].length will not exceed 2000.

Approach Overview

Problem Overview: You are given several already sorted lists and can merge any two lists at a time. Merging two lists costs the total number of elements processed. The goal is to choose the merge order that minimizes the overall cost after all lists become one.

Approach 1: Brute Force Pair Simulation (O(k^3) time, O(k) space)

Try every possible pair of lists to merge at each step and recursively evaluate the total cost. After merging two lists, update the list set and repeat until only one list remains. Each merge itself uses the standard two pointers technique to combine sorted arrays in O(a + b) time. This explores all merge orders, which grows factorially with the number of lists. The approach demonstrates the core idea that merge order affects total cost, but it quickly becomes infeasible when the number of lists grows.

Approach 2: Bitmask Dynamic Programming (O(2^k * k^2) time, O(2^k) space)

Model the problem using dynamic programming over subsets. Each state dp[mask] represents the minimum cost to merge the subset of lists represented by that bitmask. To compute a state, split the subset into two smaller subsets, merge them, and add the cost equal to the combined length. Bit operations help efficiently represent subsets and transitions, connecting the solution to bit manipulation. This guarantees the optimal merge order but still scales poorly because every subset partition must be evaluated.

Approach 3: Greedy Min-Heap (Optimal Merge Pattern) (O(k log k) time, O(k) space)

The optimal strategy mirrors Huffman coding. Always merge the two smallest lists first. Store list sizes in a min-heap, repeatedly pop the two smallest values, merge them, add the merge cost to the total, and push the combined size back. The key insight: merging smaller lists earlier prevents large lists from being repeatedly reprocessed. Each heap operation takes O(log k), and the process runs k−1 times. The lists themselves are still merged using linear two-pointer passes, but the greedy order ensures the minimal total cost. In practice, this approach dominates because it directly minimizes the cumulative merge cost.

Recommended for interviews: Start by explaining the brute-force idea to show you understand why merge order matters. Then move to the greedy min-heap solution. Interviewers expect the optimal merge pattern because it reduces the problem to repeatedly selecting the smallest two lists, giving O(k log k) complexity and a clean implementation.

Solution

The number of lists satisfies n \le 12, so a bitmask can represent any subset of lists.

Merging two sorted lists yields the sorted union of their elements, so the length and median of a set of lists depend only on the set itself, not on the merge order. The median is the left middle element after sorting, i.e. the \lfloor (len + 1)/2 \rfloor-th smallest value.

Precompute for every nonempty subset i:

  • cnt[i]: the number of elements in the subset;
  • med[i]: the median of the subset. Binary search over distinct values and count how many elements in the subset are at most mid.

Let f[i] be the minimum cost to merge all lists in subset i into one list. If i contains a single list, f[i] = 0. Otherwise enumerate a nonempty proper subset j of i and let k = i \oplus j:

$ f[i] = min_{j \subset i} \big(f[j] + f[k] + |med[j] - med[k]|\big) + cnt[i]

The length part of the last merge is always cnt[i]. The answer is f[2^n - 1].

Time complexity is O(3^n + 2^n times n times log V times log L), and space complexity is O(2^n), where n is the number of lists, V is the number of distinct values, and L$ is the maximum length of a single list.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair SimulationO(k^3)O(k)Conceptual understanding of how merge order affects cost; very small number of lists
Bitmask Dynamic ProgrammingO(2^k * k^2)O(2^k)When k is small and you want guaranteed optimal ordering via subset DP
Greedy Min-Heap (Optimal Merge Pattern)O(k log k)O(k)Best general solution; minimizes cumulative merge cost efficiently

Video Solution

Leetcode 3801 | Minimum Cost to Merge Sorted Lists |Leetcode weekly contest 483 | DP with Bitmasking • CodeWithMeGuys • 654 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Minimum Cost to Merge Sorted Lists easy or hard?
The problem is classified as Hard because identifying the optimal merge pattern requires recognizing the greedy strategy behind Huffman-style merging. Implementation is straightforward once the correct approach is identified.
Minimum Cost to Merge Sorted Lists Python/Java solution
Typical implementations push list sizes into a priority queue. Python uses heapq, Java uses PriorityQueue, while C++ uses priority_queue with a custom comparator. Each iteration pops two values, adds their sum to the total cost, and pushes the merged size back.
How to solve Minimum Cost to Merge Sorted Lists in O(k log k)?
Store the lengths of all sorted lists in a min-heap. Repeatedly extract the two smallest lengths, merge them, add their sum to the total cost, and push the combined length back into the heap. Continue until only one list remains.
What is the best approach for Minimum Cost to Merge Sorted Lists?
The greedy min-heap approach is the best solution. Always merge the two smallest lists first, similar to the optimal merge pattern used in Huffman coding. This strategy minimizes repeated processing of large lists and achieves O(k log k) time with O(k) space.
Is Minimum Cost to Merge Sorted Lists asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google, Amazon, and Meta. The pattern is commonly tested as the 'optimal merge pattern' or a Huffman-style greedy problem involving heaps.
What data structure is used in Minimum Cost to Merge Sorted Lists?
A min-heap (priority queue) is the primary data structure. It efficiently retrieves the two smallest lists at each step, which is necessary for the optimal greedy merge order.
What is the time complexity of Minimum Cost to Merge Sorted Lists?
The optimal greedy solution runs in O(k log k) time where k is the number of lists, because each merge step uses heap push and pop operations. If the actual lists are physically merged, the total element processing cost is proportional to the total size of all lists.

Ready to solve this problem?

Practice Minimum Cost to Merge Sorted Lists with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays