Jobs

Interviews

Discussions

The Earliest Moment When Everyone Become Friends

Medium

Asked by:

13 views

Topics:

ArraysGreedy Algorithms

There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestamp_i, x_i, y_i] indicates that at time timestamp_i person x_i and person y_i have become friends.

You are also given an integer n. Return the earliest time at which all the n people become friends. If the friendship relation never happens, return -1.

Example 1:

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: 20190322
Explanation:
The first event occurs at timestamp = 20190101 and connects persons 0 and 1.
At timestamp = 20190322, the 4th event occurs and connects persons 4 and 5, making all 6 persons connected.

Example 2:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,0],[8,2,1],[9,1,3]], n = 4
Output: 7
Explanation: At timestamp = 7, all 4 people are connected.

Constraints:

2 <= n <= 100
1 <= logs.length <= 10⁴
logs[i].length == 3
0 <= timestamp_i <= 10⁹
0 <= x_i, y_i <= n - 1
x_i != y_i
All timestamp_i are unique.

Try coding it in LeetCode

The Earliest Moment When Everyone Become Friends

Medium

Asked by:

13 views

Topics:

ArraysGreedy Algorithms

You are also given an integer n. Return the earliest time at which all the n people become friends. If the friendship relation never happens, return -1.

Example 1:

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: 20190322
Explanation:
The first event occurs at timestamp = 20190101 and connects persons 0 and 1.
At timestamp = 20190322, the 4th event occurs and connects persons 4 and 5, making all 6 persons connected.

Example 2:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,0],[8,2,1],[9,1,3]], n = 4
Output: 7
Explanation: At timestamp = 7, all 4 people are connected.

Constraints:

2 <= n <= 100
1 <= logs.length <= 10⁴
logs[i].length == 3
0 <= timestamp_i <= 10⁹
0 <= x_i, y_i <= n - 1
x_i != y_i
All timestamp_i are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the 'friendship' timestamps, and what data type are they represented as (e.g., integers, floats)?
If not all individuals become friends, what value should I return?
Is the input guaranteed to be sorted by timestamp, or do I need to sort it first?
What are the valid ranges and data types for the individual IDs?
How is the input structured? Is it an array of tuples (timestamp, user1, user2) or another format?

Brute Force Solution

Approach

The brute force approach means we will explore every possible friendship event order to see when everyone is connected. We'll go through each friendship event, one at a time, and check if, after adding that friendship, everyone is friends with each other.

Here's how the algorithm would work step-by-step:

Start by considering each friendship event in the order they happened.
After adding a new friendship event to our network, check if all people are now connected, either directly or indirectly, through their friendships.
To check if everyone is connected, look at each person individually and try to find a path of friendships that links them to every other person.
If even one person can't be linked to everyone else, then everyone isn't yet friends. Move on to consider the next friendship event.
Keep repeating steps 2, 3, and 4. As soon as you find the exact moment a friendship event causes everyone to be connected, that's your answer!
If you check every friendship event and never find a moment when everyone is connected, then it's impossible for everyone to become friends.

Code Implementation

def earliest_moment_everyone_friends(number_people, friendships):
    for current_time, person_one, person_two in friendships:
        # Add the current friendship to the network
        friend_network = build_friend_network(friendships, current_time)

        # Check if everyone is connected
        if all_connected(number_people, friend_network):
            return current_time

    return -1

def build_friend_network(friendships, current_time):
    friend_network = {}
    for time_stamp, person_one, person_two in friendships:
        if time_stamp <= current_time:
            if person_one not in friend_network:
                friend_network[person_one] = []
            if person_two not in friend_network:
                friend_network[person_two] = []
            friend_network[person_one].append(person_two)
            friend_network[person_two].append(person_one)
    return friend_network

def all_connected(number_people, friend_network):
    if not friend_network:
        return number_people == 1

    first_person = next(iter(friend_network))
    visited = {first_person}
    queue = [first_person]

    # Perform BFS to find all connected people
    while queue:
        person = queue.pop(0)
        if person in friend_network:
            for friend in friend_network[person]:
                if friend not in visited:
                    visited.add(friend)
                    queue.append(friend)

    # Verify that everyone is connected
    return len(visited) == number_people

# This is an example of usage for this function
# number_people = 4
# friendships = [[0, 1, 2], [1, 2, 3], [2, 1, 4]]
# result = earliest_moment_everyone_friends(number_people, friendships)
# print(result)

Big(O) Analysis

Time Complexity

O(n * m^2) – We iterate through each of the 'n' friendship events. For each event, we check if everyone is connected. Checking if everyone is connected involves, for each of the 'm' people, finding a path to every other person. Finding a path for one person to every other person requires checking up to 'm' other people, potentially through multiple connections. Thus, the connectivity check for a single friendship event takes O(m^2) time. Therefore, the overall time complexity is O(n * m^2).

Space Complexity

O(N^2) – The provided brute force approach requires a way to represent the friendship network to determine if everyone is connected. A common way to represent this is using an adjacency matrix of size N x N, where N is the number of people. This matrix uses N^2 space to store the direct or indirect connections between each pair of individuals. Thus, the auxiliary space used scales quadratically with the number of people, resulting in a space complexity of O(N^2).

Optimal Solution

Approach

The goal is to find the earliest time when everyone is connected. To do this efficiently, we'll use a method to track connections and efficiently merge groups of people until everyone belongs to the same group, stopping at the first moment this happens.

Here's how the algorithm would work step-by-step:

Imagine each person starts in their own individual group.
Process the connections one at a time, in the order they happened.
For each connection, check if the two people involved are already in the same group. If they are, it means they are already indirectly connected, so skip this connection.
If the two people are in different groups, merge those groups together. This represents these people becoming part of a larger connected community.
Keep track of how many groups you have. Every time you merge two groups, the total number of groups goes down by one.
As you merge groups, check to see if the number of groups has reached one. This means everyone is now connected.
If everyone is connected, record the time of that last connection that made it happen. This is the earliest time everyone becomes friends.
If you process all connections and everyone never ends up in the same group, then no such time exists.

Code Implementation

def find_earliest_moment(number_of_people, connections):

    parent = list(range(number_of_people))
    number_of_groups = number_of_people

    def find(person):
        if parent[person] != person:
            parent[person] = find(parent[person])
        return parent[person]

    def union(person1, person2):
        nonlocal number_of_groups
        root_person1 = find(person1)
        root_person2 = find(person2)

        if root_person1 != root_person2:
            parent[root_person1] = root_person2
            number_of_groups -= 1

    for timestamp, person1, person2 in connections:
        # Process connections in chronological order.

        union(person1 - 1, person2 - 1)

        # Check if all people are now in a single group.
        if number_of_groups == 1:

            return timestamp

    # If no such moment exists.
    return -1

Big(O) Analysis

Time Complexity

O(N log N) – The primary cost driver is sorting the connections, which takes O(N log N) time where N is the number of connections. The Union-Find operations (find and union) inside the loop have a time complexity that is nearly constant with path compression and union by rank optimization, making them negligible compared to the sorting step. Therefore, the overall time complexity is dominated by the sorting, resulting in O(N log N).

Space Complexity

O(N) – The algorithm needs to maintain a data structure to represent the groups each person belongs to. In the worst case, each person starts in their own group, requiring an auxiliary array or dictionary of size N to map each person to their group, where N is the number of people. When merging groups, this data structure is updated. The number of groups and time of connection variables are constant and do not affect the overall space complexity. Therefore, the dominant space usage is O(N).

Edge Cases

Case	How to Handle
Empty log or no friendships established	Return -1 or appropriate error code if the log is empty, indicating no friendship ever occurred.
Only one person exists	Return 0 if only one person exists since everyone is already 'friends' from the start.
Log is not sorted by timestamp	Sort the log entries by timestamp as a preprocessing step to ensure correct order of events.
Disjointed groups that never fully connect	Return -1 if the algorithm completes and there are still disjoint groups, indicating that everyone never becomes friends.
Maximum number of people is very large, impacting Union-Find performance.	Use path compression and union by rank in the Union-Find data structure for optimal performance with a large number of people.
Integer overflow when calculating timestamp or representing person IDs.	Use appropriate data types (e.g., long) to handle large timestamps and IDs to avoid integer overflow.
Invalid person IDs (e.g., negative or out of range).	Validate person IDs at the beginning, raising an exception or returning an error if they are invalid.
Log contains redundant friendship connections between the same two people at different timestamps.	The Union-Find data structure ensures that subsequent connections between already connected people are ignored, preventing incorrect earliest moment calculation.

Empty log or no friendships established

How to Handle:

Return -1 or appropriate error code if the log is empty, indicating no friendship ever occurred.

Only one person exists

How to Handle:

Return 0 if only one person exists since everyone is already 'friends' from the start.

Log is not sorted by timestamp

How to Handle:

Sort the log entries by timestamp as a preprocessing step to ensure correct order of events.

Disjointed groups that never fully connect

How to Handle:

Return -1 if the algorithm completes and there are still disjoint groups, indicating that everyone never becomes friends.

Maximum number of people is very large, impacting Union-Find performance.

How to Handle:

Use path compression and union by rank in the Union-Find data structure for optimal performance with a large number of people.

Integer overflow when calculating timestamp or representing person IDs.

How to Handle:

Use appropriate data types (e.g., long) to handle large timestamps and IDs to avoid integer overflow.

Invalid person IDs (e.g., negative or out of range).

How to Handle:

Validate person IDs at the beginning, raising an exception or returning an error if they are invalid.

Log contains redundant friendship connections between the same two people at different timestamps.

How to Handle:

The Union-Find data structure ensures that subsequent connections between already connected people are ignored, preventing incorrect earliest moment calculation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the 'friendship' timestamps, and what data type are they represented as (e.g., integers, floats)?
If not all individuals become friends, what value should I return?
Is the input guaranteed to be sorted by timestamp, or do I need to sort it first?
What are the valid ranges and data types for the individual IDs?
How is the input structured? Is it an array of tuples (timestamp, user1, user2) or another format?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering each friendship event in the order they happened.
After adding a new friendship event to our network, check if all people are now connected, either directly or indirectly, through their friendships.
To check if everyone is connected, look at each person individually and try to find a path of friendships that links them to every other person.
If even one person can't be linked to everyone else, then everyone isn't yet friends. Move on to consider the next friendship event.
Keep repeating steps 2, 3, and 4. As soon as you find the exact moment a friendship event causes everyone to be connected, that's your answer!
If you check every friendship event and never find a moment when everyone is connected, then it's impossible for everyone to become friends.

Code Implementation

def earliest_moment_everyone_friends(number_people, friendships):
    for current_time, person_one, person_two in friendships:
        # Add the current friendship to the network
        friend_network = build_friend_network(friendships, current_time)

        # Check if everyone is connected
        if all_connected(number_people, friend_network):
            return current_time

    return -1

def build_friend_network(friendships, current_time):
    friend_network = {}
    for time_stamp, person_one, person_two in friendships:
        if time_stamp <= current_time:
            if person_one not in friend_network:
                friend_network[person_one] = []
            if person_two not in friend_network:
                friend_network[person_two] = []
            friend_network[person_one].append(person_two)
            friend_network[person_two].append(person_one)
    return friend_network

def all_connected(number_people, friend_network):
    if not friend_network:
        return number_people == 1

    first_person = next(iter(friend_network))
    visited = {first_person}
    queue = [first_person]

    # Perform BFS to find all connected people
    while queue:
        person = queue.pop(0)
        if person in friend_network:
            for friend in friend_network[person]:
                if friend not in visited:
                    visited.add(friend)
                    queue.append(friend)

    # Verify that everyone is connected
    return len(visited) == number_people

# This is an example of usage for this function
# number_people = 4
# friendships = [[0, 1, 2], [1, 2, 3], [2, 1, 4]]
# result = earliest_moment_everyone_friends(number_people, friendships)
# print(result)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each person starts in their own individual group.
Process the connections one at a time, in the order they happened.
For each connection, check if the two people involved are already in the same group. If they are, it means they are already indirectly connected, so skip this connection.
If the two people are in different groups, merge those groups together. This represents these people becoming part of a larger connected community.
Keep track of how many groups you have. Every time you merge two groups, the total number of groups goes down by one.
As you merge groups, check to see if the number of groups has reached one. This means everyone is now connected.
If everyone is connected, record the time of that last connection that made it happen. This is the earliest time everyone becomes friends.
If you process all connections and everyone never ends up in the same group, then no such time exists.

Code Implementation

def find_earliest_moment(number_of_people, connections):

    parent = list(range(number_of_people))
    number_of_groups = number_of_people

    def find(person):
        if parent[person] != person:
            parent[person] = find(parent[person])
        return parent[person]

    def union(person1, person2):
        nonlocal number_of_groups
        root_person1 = find(person1)
        root_person2 = find(person2)

        if root_person1 != root_person2:
            parent[root_person1] = root_person2
            number_of_groups -= 1

    for timestamp, person1, person2 in connections:
        # Process connections in chronological order.

        union(person1 - 1, person2 - 1)

        # Check if all people are now in a single group.
        if number_of_groups == 1:

            return timestamp

    # If no such moment exists.
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty log or no friendships established	Return -1 or appropriate error code if the log is empty, indicating no friendship ever occurred.
Only one person exists	Return 0 if only one person exists since everyone is already 'friends' from the start.
Log is not sorted by timestamp	Sort the log entries by timestamp as a preprocessing step to ensure correct order of events.
Disjointed groups that never fully connect	Return -1 if the algorithm completes and there are still disjoint groups, indicating that everyone never becomes friends.
Maximum number of people is very large, impacting Union-Find performance.	Use path compression and union by rank in the Union-Find data structure for optimal performance with a large number of people.
Integer overflow when calculating timestamp or representing person IDs.	Use appropriate data types (e.g., long) to handle large timestamps and IDs to avoid integer overflow.
Invalid person IDs (e.g., negative or out of range).	Validate person IDs at the beginning, raising an exception or returning an error if they are invalid.
Log contains redundant friendship connections between the same two people at different timestamps.	The Union-Find data structure ensures that subsequent connections between already connected people are ignored, preventing incorrect earliest moment calculation.

Empty log or no friendships established

How to Handle:

Return -1 or appropriate error code if the log is empty, indicating no friendship ever occurred.

Only one person exists

How to Handle:

Return 0 if only one person exists since everyone is already 'friends' from the start.

Log is not sorted by timestamp

How to Handle:

Sort the log entries by timestamp as a preprocessing step to ensure correct order of events.

Disjointed groups that never fully connect

How to Handle:

Return -1 if the algorithm completes and there are still disjoint groups, indicating that everyone never becomes friends.

Maximum number of people is very large, impacting Union-Find performance.

How to Handle:

Use path compression and union by rank in the Union-Find data structure for optimal performance with a large number of people.

Integer overflow when calculating timestamp or representing person IDs.

How to Handle:

Use appropriate data types (e.g., long) to handle large timestamps and IDs to avoid integer overflow.

Invalid person IDs (e.g., negative or out of range).

How to Handle:

Validate person IDs at the beginning, raising an exception or returning an error if they are invalid.

Log contains redundant friendship connections between the same two people at different timestamps.

How to Handle:

The Union-Find data structure ensures that subsequent connections between already connected people are ignored, preventing incorrect earliest moment calculation.