Skip to content

3801. Minimum Cost to Merge Sorted Lists

Description

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.

Solutions

Solution 1: State Compression DP

Thinking

There are at most \(n \le 12\) lists, so enumerating merge orders as Catalan trees repeats the same subsets. Total length is modest, but the order itself cannot be searched.

Length and median of a merge depend only on the multiset of values, not on the intermediate merge sequence. Each subset therefore has a unique length and median.

We represent unused lists as a bit mask, precompute each nonempty subset's count and left median, then DP by splitting a set into two nonempty proper subsets, adding the median gap and the total length.

The \(2^n\) subset DP covers every collection; the answer is the cost of the full mask.

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\):

  • \(\textit{cnt}[i]\): the number of elements in the subset;
  • \(\textit{med}[i]\): the median of the subset. Binary search over distinct values and count how many elements in the subset are at most \(\textit{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] + |\textit{med}[j] - \textit{med}[k]|\big) + \textit{cnt}[i] \]

The length part of the last merge is always \(\textit{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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def minMergeCost(self, lists: List[List[int]]) -> int:
        n = len(lists)
        vals = sorted({x for v in lists for x in v})
        cnt = [0] * (1 << n)
        med = [0] * (1 << n)
        for i in range(1, 1 << n):
            for j, v in enumerate(lists):
                if i >> j & 1:
                    cnt[i] += len(v)
            need = (cnt[i] + 1) // 2
            l, r = 0, len(vals) - 1
            while l < r:
                mid = (l + r) >> 1
                le = 0
                b = i
                while b:
                    t = (b & -b).bit_length() - 1
                    le += bisect_right(lists[t], vals[mid])
                    if le >= need:
                        break
                    b &= b - 1
                if le >= need:
                    r = mid
                else:
                    l = mid + 1
            med[i] = vals[l]

        f = [inf] * (1 << n)
        for i in range(1, 1 << n):
            if i.bit_count() == 1:
                f[i] = 0
                continue
            j = (i - 1) & i
            while j:
                k = i ^ j
                if j <= k:
                    f[i] = min(f[i], f[j] + f[k] + abs(med[j] - med[k]))
                j = (j - 1) & i
            f[i] += cnt[i]
        return f[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
    public long minMergeCost(int[][] lists) {
        int n = lists.length;
        int tot = 0;
        for (int[] v : lists) {
            tot += v.length;
        }
        int[] vals = new int[tot];
        int p = 0;
        for (int[] v : lists) {
            for (int x : v) {
                vals[p++] = x;
            }
        }
        Arrays.sort(vals);
        int m = 0;
        for (int i = 0; i < tot; ++i) {
            if (m == 0 || vals[i] != vals[m - 1]) {
                vals[m++] = vals[i];
            }
        }
        int[] cnt = new int[1 << n];
        int[] med = new int[1 << n];
        for (int i = 1; i < 1 << n; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    cnt[i] += lists[j].length;
                }
            }
            int need = (cnt[i] + 1) / 2;
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                int le = 0;
                for (int b = i; b > 0; b &= b - 1) {
                    int id = Integer.numberOfTrailingZeros(b);
                    le += upperBound(lists[id], vals[mid]);
                    if (le >= need) {
                        break;
                    }
                }
                if (le >= need) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            med[i] = vals[l];
        }

        long[] f = new long[1 << n];
        Arrays.fill(f, Long.MAX_VALUE / 4);
        for (int i = 1; i < 1 << n; ++i) {
            if (Integer.bitCount(i) == 1) {
                f[i] = 0;
                continue;
            }
            for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
                int k = i ^ j;
                if (j <= k) {
                    f[i] = Math.min(f[i], f[j] + f[k] + Math.abs(med[j] - med[k]));
                }
            }
            f[i] += cnt[i];
        }
        return f[(1 << n) - 1];
    }

    private int upperBound(int[] a, int x) {
        int l = 0, r = a.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] <= x) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    long long minMergeCost(vector<vector<int>>& lists) {
        int n = lists.size();
        vector<int> vals;
        for (auto& v : lists) {
            vals.insert(vals.end(), v.begin(), v.end());
        }
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());

        vector<int> cnt(1 << n);
        vector<int> med(1 << n);
        for (int i = 1; i < 1 << n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1) {
                    cnt[i] += lists[j].size();
                }
            }
            int need = (cnt[i] + 1) / 2;
            int l = 0, r = vals.size() - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                int le = 0;
                for (int b = i; b; b &= b - 1) {
                    int id = __builtin_ctz(b);
                    le += upper_bound(lists[id].begin(), lists[id].end(), vals[mid]) - lists[id].begin();
                    if (le >= need) {
                        break;
                    }
                }
                if (le >= need) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            med[i] = vals[l];
        }

        vector<long long> f(1 << n, 1e18);
        for (int i = 1; i < 1 << n; ++i) {
            if (__builtin_popcount(i) == 1) {
                f[i] = 0;
                continue;
            }
            for (int j = (i - 1) & i; j; j = (j - 1) & i) {
                int k = i ^ j;
                if (j <= k) {
                    f[i] = min(f[i], f[j] + f[k] + abs(med[j] - med[k]));
                }
            }
            f[i] += cnt[i];
        }
        return f[(1 << n) - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
func minMergeCost(lists [][]int) int64 {
    n := len(lists)
    set := map[int]struct{}{}
    for _, v := range lists {
        for _, x := range v {
            set[x] = struct{}{}
        }
    }
    vals := make([]int, 0, len(set))
    for x := range set {
        vals = append(vals, x)
    }
    sort.Ints(vals)

    cnt := make([]int, 1<<n)
    med := make([]int, 1<<n)
    for i := 1; i < 1<<n; i++ {
        for j, v := range lists {
            if i>>j&1 == 1 {
                cnt[i] += len(v)
            }
        }
        need := (cnt[i] + 1) / 2
        l, r := 0, len(vals)-1
        for l < r {
            mid := (l + r) >> 1
            le := 0
            for b := i; b > 0; b &= b - 1 {
                id := bits.TrailingZeros(uint(b))
                le += sort.Search(len(lists[id]), func(p int) bool { return lists[id][p] > vals[mid] })
                if le >= need {
                    break
                }
            }
            if le >= need {
                r = mid
            } else {
                l = mid + 1
            }
        }
        med[i] = vals[l]
    }

    f := make([]int64, 1<<n)
    for i := range f {
        f[i] = 1e18
    }
    for i := 1; i < 1<<n; i++ {
        if bits.OnesCount(uint(i)) == 1 {
            f[i] = 0
            continue
        }
        for j := (i - 1) & i; j > 0; j = (j - 1) & i {
            k := i ^ j
            if j <= k {
                d := med[j] - med[k]
                if d < 0 {
                    d = -d
                }
                f[i] = min(f[i], f[j]+f[k]+int64(d))
            }
        }
        f[i] += int64(cnt[i])
    }
    return f[1<<n-1]
}

Comments