Tag: 1101

The premise:

In a social group, there are n people, with unique integer ids from 0 to n-1.

We have a list of logs, where each logs[i] = [timestamp, id_A, id_B] contains a non-negative integer timestamp, and the ids of two different people.

Each log represents the time in which two different people became friends.  Friendship is symmetric: if A is friends with B, then B is friends with A.

Let’s say that person A is acquainted with person B if A is friends with B, or A is a friend of someone acquainted with B.

Return the earliest time for which every person became acquainted with every other person. Return -1 if there is no such earliest time.

Example test case:

Input: logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], n = 6
Output: 20190301

My solution, in Typescript:

function earliestAcq(logs: number[][], n: number): number {

    // sort the logs by timestamp (earliest first)
    logs.sort((a:number[], b:number[]) => {
       return (a[0] - b[0]);
    });

    // this map is going to serve as a container for all the sets
    let mapOfSets = new Map();
    
    // put every friend ID into its own individual set
    for (let i = 0; i < n; i++) {
        let individualSet = new Set();
        individualSet.add(i);
        mapOfSets.set(i, individualSet);
    }
    
    // now every friend is its own set in the map 
    // console.log(mapOfSets);
    
    // step through the logs and join the sets as matches are encountered 
    for (let i = 0; i < logs.length; i++) {
        let friendA = logs[i][1];
        let friendB = logs[i][2];

        // friendA and friendB have "met" - get their sets
        
        let setA = mapOfSets.get(friendA);
        let setB = mapOfSets.get(friendB);
        
        // and if their sets are not equal...
        if (setA != setB) {
            // join the two sets by adding all of the friends from setB to setA
            for (let friend of setB) {
                // add all the friends from setB to setA
                setA.add(friend);
                
                // update map of sets such that setA is pointed at by each friend originally from B
                mapOfSets.set(friend, setA);
            }
            
            if (setA.size === n) {
                // every friend is now accounted for in set A
                // return the timestamp where this was achieved
                return logs[i][0];
            }
        }
    }
    
    return -1;
};

View as a gist on GitHub

My solution, explained:

1. Sort all the inputs by timestamp so the earliest ones are first
2. Create a new map and fill it with sets representing the currently known friendships. The keys will be the friend “ID numbers”, and the values will be the sets representing who that friend is friends with. In the beginning, a friend is only friends with themselves. mapOfSets = {0:{0}, 1:{1}, 2:{2}, 3:{3}, 4:{4}, 5:{5}}
3. Now, step through the logs and grab each friend pair (friendA and friendB) from that log.
4. Get the set associated with friendA, and the set associated with friendB, and see if they’re identical
5. If the sets are not identical, copy all the friends from setB to setA and for each of those relocated friends, update their own value in the mapOfSets to point at setA
6. If setA becomes equal in size to n (the number of friends), then this is the moment where “everyone knows everyone else” and we can return the timestamp of the current log

Runtime analysis:

O(n log n) due to the sorting

Performance:

Ehh, I doubt this was the absolute best way to do this – it’s just because so few other Typescript submissions exist.