skip to Main Content

I have a target array, say: [A, C, E, F, H].
I have another array toMerge that needs to be merged into target, say: [B, D, G, I].
I also have an integer array that tells the indices of target array where toMerge items will be finally merged at, say: [1, 3, 6, 8].

I need a function that will merge toMerge array into target in-place, at indices specified by the indices array so that target eventually looks like

[A(0), B(1), C(2), D(3), E(4), F(5), G(6), H(7), I(8)]

I tried using inbuilt array splice functions to iterate over indices array and splice(add) each at each index. Something along the lines:

for (let i = 0; i < indices.length; i++) {
    target.splice(indices[i], 0, toMerge[i]);
}

I am looking for any solution that can do it more efficiently and elegantly.

It gets trickier if the indices array is unsorted or worse – reverse-sorted! For e.g.,

toMerge: [I, G, D, B]
indices: [8, 6, 3, 1]

after applying the above algorithm, target ends up being:

target: [A, B, C, E, D, F, H, I, G]

One solution to this is to sort the indices array in non-decreasing order along with the toMerge array ensuring the sequence is honored, further complicating things.

2

Answers


  1. Unsorted indices + absolute

    If you are working with unsorted indices: you would have to "zip" (need to first transpose) the array to be merged and its corresponding indices. Once you have a matrix of [index, value][] sorted, you can perform an in-order splice.

    const transpose = (a) => a[0].map((_, i) => a.map(r => r[i]));
    const sortByIndex = (a) => a.sort((x, y) => x[0] - y[0]);
    
    const absoluteMerge = (a, toMerge, unsortedIndices) => {
      const res = [...a];
      const sorted = sortByIndex(transpose([unsortedIndices, toMerge]));
      for (let i = 0; i < sorted.length; i++) {
        res.splice(sorted[i][0], 0, sorted[i][1]);
      }
      return res;
    };
    
    const a = ['A', 'C', 'E', 'F', 'H'], b = ['I', 'G', 'D', 'B'];
    
    const c = absoluteMerge(a, b, [8, 6, 3, 1]);
    
    console.log(...c); // A B C D E F G H I

    Original response

    If you are working with absolute indices (as you are), you can insert the items in-order; but if you use relative indices, you need to reverse the insertion.

    Absolute merge

    const absoluteMerge = (a, b, insertionIndices) => {
      const res = [...a];
      for (let i = 0; i < insertionIndices.length; i++) {
        res.splice(insertionIndices[i], 0, b[i]);
      }
      return res;
    };
    
    const a = ['A', 'C', 'E', 'F', 'H'], b = ['B', 'D', 'G'];
    
    const c = absoluteMerge(a, b, [1, 3, 6]);
    
    console.log(...c); // A B C D E F G H

    Relative merge

    const relativeMerge = (a, b, insertionIndices) => {
      const res = [...a];
      for (let i = insertionIndices.length - 1; i >= 0; i--) {
        res.splice(insertionIndices[i], 0, b[i]);
      }
      return res;
    };
    
    const a = ['A', 'C', 'E', 'F', 'H'], b = ['B', 'D', 'G'];
    
    const c = relativeMerge(a, b, [1, 2, 4]);
    
    console.log(...c); // A B C D E F G H
    Login or Signup to reply.
  2. Thinking on sorted, reverse-sorted, and a possibility of unsorted list toMerge, at first we need to merge the toMerge with the indices list and sort, then we can merge these values with the target list, for example:

    const mergeArraysByIndex = (target, toMerge, indices) => {
      // Create an array of objects with keys and values
      const toMergeWithIndex = toMerge.map((key, index) => ({key, value: indices[index]}));
    
      // Sort the array of objects by value
      toMergeWithIndex.sort((a, b) => a.value - b.value);
    
      // Create a final object with sorted keys and values
      const resultObject = {};
      toMergeWithIndex.forEach(item => {
        resultObject[item.key] = item.value;
      });
    
      //Merge the arrays together
      return Object.values(resultObject).reduce((acc, index, i) => {
        acc.splice(index, 0, Object.keys(resultObject)[i]);
        return acc;
      }, [...target])
    }
    
    //First example (sorted!)
    console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['B', 'D', 'G'], [1, 3, 6]));
    
    //Second example (reverse-sorted!)
    console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['I', 'G', 'D', 'B'], [8, 6, 3, 1]));
    
    //Third example (unsorted!)
    console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['D', 'I', 'G', 'B'], [3, 8, 6, 1]));

    Or in a resumed way:

    const mergeArraysByIndex = (target, toMerge, indices) => {
      return indices
        .map((index, i) => ({ key: toMerge[i], index }))
        .sort((a, b) => a.index - b.index)
        .reduce((acc, { key, index }) => {
          acc.splice(index, 0, key);
          return acc;
        }, [...target]);
    };
    
    //First example (sorted!)
    console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['B', 'D', 'G'], [1, 3, 6]));
    
    //Second example (reverse-sorted!)
    console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['I', 'G', 'D', 'B'], [8, 6, 3, 1]));
    
    //Third example (unsorted!)
    console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['D', 'I', 'G', 'B'], [3, 8, 6, 1]));
    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search