Code Logo

Library Shelf Merge Log

Published at05 Jan 2026
Created by
Easy 7 views
Like27

In Library Shelf Merge Log, you are given a list of shelves, where each shelf is already sorted, plus a list of merge instructions. Each instruction tells you to merge two shelves together into one new sorted shelf.

The order of instructions matters. After you perform one merge, the shelf list changes, and the next instruction works on that updated list. You do not sort the whole library from scratch each time. Instead, you repeatedly take two already sorted shelves, merge them into one sorted result, and place that merged shelf back into the shelf list.

For example, if shelves = [[1,4],[2,3]] and merges = [], nothing changes, so the answer stays [[1,4],[2,3]]. If shelves = [[2,4],[1,3,5],[6]] and merges = [[0,1],[0,1]], you first merge the first two shelves into [1,2,3,4,5], then merge that result with [6] to get [[1,2,3,4,5,6]].

So the task is to process the merge instructions one by one and keep each merged shelf sorted as you go.

Example Input & Output

Example 1
Input
shelves = [[1,4],[2,3]], merges = []
Output
[[1,4],[2,3]]
Explanation

With no merges scheduled, the layout stays intact.

Example 2
Input
shelves = [[2,4],[1,3,5],[6]], merges = [[0,1],[0,1]]
Output
[[1,2,3,4,5,6]]
Explanation

First merge shelves 0 and 1 into [1,2,3,4,5], then merge that shelf with the final shelf [6].

Example 3
Input
shelves = [[10],[8,12],[9]], merges = [[1,2]]
Output
[[10],[8,9,12]]
Explanation

Only shelf index 1 and 2 are merged; shelf 0 remains unchanged.

Algorithm Flow

Recommendation Algorithm Flow for Library Shelf Merge Log
Recommendation Algorithm Flow for Library Shelf Merge Log

Solution Approach

A good way to solve this problem is to treat every instruction as a standard merge of two already sorted arrays. That is the key simplifying idea. Because each shelf is sorted to begin with, and each merged shelf should also stay sorted, you can use the classic two-pointer merge technique from merge sort.

Suppose an instruction says to merge shelf i and shelf j. You take those two sorted lists, walk through them with two indices, and build a new sorted shelf by always choosing the smaller front value. If one shelf runs out first, you append the rest of the other shelf. That gives you the merged result in linear time relative to the combined shelf sizes.

In JavaScript, the merge helper can look like this:

function mergeSorted(a, b) {
  const merged = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) merged.push(a[i++]);
    else merged.push(b[j++]);
  }
  while (i < a.length) merged.push(a[i++]);
  while (j < b.length) merged.push(b[j++]);
  return merged;
}

After you compute the merged shelf, you replace the two old shelves with the new one in the current shelf list. Because later instructions operate on the updated list, you must apply the merges in the exact order given. That is why this problem is more than just one isolated merge.

This approach matches the examples well. In [[2,4],[1,3,5],[6]] with merges [[0,1],[0,1]], the first merge gives [1,2,3,4,5], and the second merge combines that with [6] into [1,2,3,4,5,6]. If there are no merge instructions, you simply return the shelves unchanged.

The running time depends on the total sizes of the shelves involved in the merges, but each individual merge is linear in the amount of data being merged. The extra space comes from building the merged shelves.

So the full strategy is: process the instructions one by one, merge the chosen sorted shelves with two pointers, update the shelf list after each step, and return the final shelf structure when all merges are done.

Best Answers

java
import java.util.*;
class Solution {
    public Object library_shelf_merge_log(Object input) {
        Object[] args = (Object[]) input;
        int[][] shelves_arr = (int[][]) args[0];
        int[][] merges = (int[][]) args[1];
        List<List<Integer>> s = new ArrayList<>();
        for (int[] sh : shelves_arr) {
            List<Integer> list = new ArrayList<>();
            for (int x : sh) list.add(x);
            s.add(list);
        }
        Set<Integer> to_remove = new HashSet<>();
        for (int k = merges.length - 1; k >= 0; k--) {
            int i = merges[k][0], j = merges[k][1];
            s.get(i).addAll(s.get(j));
            Collections.sort(s.get(i));
            to_remove.add(j);
        }
        List<int[]> resList = new ArrayList<>();
        for (int idx = 0; idx < s.size(); idx++) {
            if (!to_remove.contains(idx)) {
                List<Integer> list = s.get(idx);
                int[] row = new int[list.size()];
                for (int m_idx = 0; m_idx < list.size(); m_idx++) row[m_idx] = list.get(m_idx);
                resList.add(row);
            }
        }
        return resList.toArray(new int[0][]);
    }
}