# Friend circle queries in JavaScript

We get a list of queries denoting formed friendships. We need to return the max group size on each iteration.

Example:

terminal
1 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:

javascript
let 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;

## How to translate it into code?

We can transalte the previous behaviour into a function:

javascript
const 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;

javascript
const 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:

javascript
const 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.