3
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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));

\$\endgroup\$
  • \$\begingroup\$ Thank you so much for the advice! I appreciate your time. \$\endgroup\$ – callback Dec 3 '20 at 11:53
3
\$\begingroup\$

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)).

\$\endgroup\$
  • \$\begingroup\$ Love const { id, items } of list, nice! \$\endgroup\$ – konijn Dec 3 '20 at 14:27
  • \$\begingroup\$ Thank you so much for all the details!! I am indebted! \$\endgroup\$ – callback Dec 3 '20 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.