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.