We get a list of queries denoting formed friendships. We need to return the max group size on each iteration.
Example:
terminal1 2 3 4 1 3
If members of two different circles become friends, both circles merge into a bigger one.
Graphically:
terminal. . . . . 👨 👩 . . 1 2 . ---> size = 2 . . . . . . . . . 👴 👵 . . 3 4 . ---> size = 2 . . . . . - ~ ~ ~ - . . ' ' . . . . . . . . 👨 👩 👴 👵 . ---> size = 4 . 1 2 3 4 . . . . . . . ' ' - . _ _ _ . '
We could use lines instead of circles:
terminal👨 ········ 👩 ---> size = 2 1 2 ↓ Root 👴 ········ 👵 ---> size = 2 3 4 ↓ Root Root ↑ 👨 ········ 👩 1 2 . . ---> size = 4 . 👴 ········ 👵 3 4
As we can see, there is a root element on each iteration:
javascriptlet root = {}; let size = {}; // 1 2: New group of people root[1] = 1; root[2] = 1; size[1] = 2; // 3 4: New group of people root[3] = 3; root[4] = 3; size[3] = 2; // 1 3: Union between both groups root[1] = 1; root[3] = 1; size[1] = 4;
We can transalte the previous behaviour into a function:
javascriptconst maxCircles = (queries) => { // Defining variables let root = {}; let size = {}; let res = []; let newSize; // Iterating through queries for(let i = 0; i < queries.length; i ++){ // Reading friends for each query let friends = [queries[i][0], queries[i][1]]; // Getting roots of both friends let r = [getRoot(friends[0]), getRoot(friends[1])]; // If roots are different, we need to merge both groups if(r[0] !== r[1]){ newSize = mergeGroups(r[0], r[1]); } // Pushing max group size res.push(Math.max(newSize, res.length > 0 ? res[res.length - 1] : 2)); } return res; }
Let's define first how to get the root of a friend;
javascriptconst getRoot = (friend) => { // If friend has root, find it iterating through root if(root[friend]){ // Roots satisfy root[friend] === friend while(root[friend] !== friend){ friend = root[friend]; } } // Otherwise, create new group with friend as root else{ root[friend] = friend; size[friend] = 1; } return root[friend]; }
To merge two different groups, we need to change root of one of the groups:
javascriptconst mergeGroups = (r0, r1) => { // Changing the root of one of the groups root[r1] = r0; // Size of the group increases size[r0] += size[r1]; // Size of the old root group becomes zero size[r1] = 0; // Returning size of the new group return size[r0]; }
Hi, I'm Erik, an engineer from Barcelona. If you like the post or have any comments, say hi.