# 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;
root = 1;
size = 2;

// 3 4: New group of people
root = 3;
root = 3;
size = 2;

// 1 3: Union between both groups
root = 1;
root = 1;
size = 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], queries[i]];

// Getting roots of both friends
let r = [getRoot(friends), getRoot(friends)];

// If roots are different, we need to merge both groups
if(r !== r){

newSize = mergeGroups(r, r);

}

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