Merge arrays in objects in array based on property

Question

I have the following code which takes an array that might have duplicate ids and will merge the items of those duplicate, and keep only one element per id which contains all the items of all elements with the same id.

array = [{
    id: 1,
    items: [1, 2, 3]
  },
  {
    id: 2,
    items: [1, 2]
  },
  {
    id: 1,
    items: [4]
  },
  {
    id: 3,
    items: [1]
  },
];

const mergeLines = (a) => {
  const processedIds = [];
  const finalResult = [];
  a.forEach((element) => {
    const elementId = element.id;
    if (processedIds.indexOf(elementId) === -1) {
      const occurences = a.filter((el) => el.id === elementId);
      if (occurences.length > 1) {
        const allItems = occurences.reduce((acc, curr) => {
          acc = acc.concat(curr.items);
          return acc;
        }, []);
        element = { ...element,
          items: allItems
        };
        finalResult.push(element);
      } else {
        finalResult.push(element);
      }

      processedIds.push(elementId);
    }
  });
  return finalResult;
};

console.log(mergeLines(array));

I feel this code can be optimized much further to 0(n)

Answer 1

A short review;

• This code looks incredibly complicated for what you want to achieve, sometimes a few for loops beat the functional approach
• array is a global variable (not var or set or const), that is a bad thing
• If a function is not inline, I would encourage you to use the function keyword
• I am not sure mergeLines is a great name, perhaps mergeIds ?

array = [{
    id: 1,
    items: [1, 2, 3]
  },
  {
    id: 2,
    items: [1, 2]
  },
  {
    id: 1,
    items: [4]
  },
  {
    id: 3,
    items: [1]
  },
];

function mergeIds(list){
  const out = [];
  for(entry of list){
    const existingEntry = out.find(o => o.id === entry.id);
    if(existingEntry){
      existingEntry.items = existingEntry.items.concat(entry.items);
    } else {
      out.push(entry);
    }
  }
  
  return out;
}

console.log(mergeIds(array));

Answer 2

You can reduce the computational complexity to O(n) by putting the intermediate arrays into an object indexed by id. This way, for every array item, you just need to look up the id property on the object, and don't need to search through every item in the array for a possible match:

array = [{
    id: 1,
    items: [1, 2, 3]
  },
  {
    id: 2,
    items: [1, 2]
  },
  {
    id: 1,
    items: [4]
  },
  {
    id: 3,
    items: [1]
  },
];

const mergeIds = (list) => {
  const subarrsById = {};
  for (const { id, items } of list) {
    if (!subarrsById[id]) {
      subarrsById[id] = { id, items: [...items] };
    } else {
      subarrsById[id].items.push(...items);
    }
  }
  return Object.values(subarrsById);
}

console.log(mergeIds(array));

One caveat - this will result in the output array being sorted by ascending array index, rather than by order of occurrence in the original array (because that's how object keys are arranged). If that's an issue, you can use a Map instead.

array = [{
    id: 1,
    items: [1, 2, 3]
  },
  {
    id: 2,
    items: [1, 2]
  },
  {
    id: 1,
    items: [4]
  },
  {
    id: 3,
    items: [1]
  },
];

const mergeIds = (list) => {
  const subarrsById = new Map();
  for (const { id, items } of list) {
    if (!subarrsById.has(id)) {
      subarrsById.set(id, { id, items: [...items] });
    } else {
      subarrsById.get(id).items.push(...items);
    }
  }
  return [...subarrsById.values()];
}

console.log(mergeIds(array));

A suggestion regarding your original code:

  processedIds.indexOf(elementId) === -1

When you want to check if an array contains an element, it's more natural to use .includes rather than an .indexOf check against -1.

Also, when creating a collection of processed primitives (like the IDs here), and you need to regularly check that collection to see if a particular primitive has been processed yet, consider using a Set and Set#has (O(1)) instead of an array and Array#includes (O(n)).