Friend Circles — Day 32(Python)
Today’s question is an interesting discovery from Leetcode. It is a frequent question in Amazon, Goldman Sachs, and Dropbox’s technical coding round.
547. Friend Circles
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
1 <= N <= 200
M[i][i] == 1
M[i][j] == M[j][i]
Let us take an example and try solving it.
Input: A B C
C [0,0,1]]Output: 2
Let rows depict a person, and let columns be friends.
Let row 1 be person “A”. “A” is friends with himself and “B”.
Let row 2 be person “B”. “B” is friends with himself and “A”.
Let row 3 be person “C”. “C” is friends with himself.
The graphical representation would look like the following.
Here we have two separately connected components. Hence the answer is two.
The gist of the question requires us to find the number of connected graphs. This diagram reminds me of the Number of Islands problem. You can find the solution here. Now we know that we will be using Depth-First-Search to proceed with the problem.
- Let us have a set/list that can keep track of all the people as well as his friends that we have visited. We can make use of a variable counter that keeps track of connected components.
- We will need to run a loop for all the people in the matrix.
- Start from the first person, Check if this person has been visited. If not, insert the row number into the set and increment the counter.
- Check for his neighbors. Each neighbor will now act as a starting person, call step 3 again.
Let us look into the code.
def findCircleNum(self, M: List[List[int]]) -> int:
output = 0
visited = set()
for row in range(len(M)):
if M[row][row] == 1 and row not in visited:
output += 1
visited = self.dfs(row, M, visited)
def dfs(self, row, M, visited):
for neigh in range(len(M[row])):
if M[row][neigh] == 1 and neigh not in visited:
self.dfs(neigh, M, visited)
We are visiting all the cells in the matrix therefore the time complexity of the above code snippet is O(N²) where N is the number of people.
We are using a set that holds all the people visited. Hence the space complexity is O(N).
I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.