Coding Challenge: Detecting Unique Friend Circles in NxN Matrix

Friend Circle. Photo by Margarida CSilva on Unsplash

Lately I've been trying to challenge myself by taking a stab at some common coding questions asked in software engineering job interviews. After years of working on apps you would think that this kind of thing comes easy, but software development in the modern age comes with a heavy side of Googling and lookup, so challenging your brain in this way to implement an algorithm or process from just its definition or description is good practice to keep you sharp.

Yesterday, I came across a question on LeetCode that asked me to find the total number of friend circles given an N by N matrix showing their relationships. Here is how I implemented a solution in ruby:

The exact working of the question looks like this:

There are N students in a class. Some of them are friends, while some are not.
Their friendship is transitive in nature.
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.

Note:
- N is in range [1,200].
- M[i][i] = 1 for all students.
- If M[i][j] = 1, then M[j][i] = 1.

In short, we have a matrix where each row of index i represents a different student, and each column of index j within that row represents a friendship with the student at i. Because you are always your own best friend, any row on the identity diagonal where i == j will be 1. The rest can be either a 0 or a 1, with a 1 representing a friendship between i and j. A friend circle is defined as containing anybody who is a friend, or a friend-of-a-friend. We are interested in finding how many friend circles are present within the matrix.

My initial thoughts on how to approach this was to write out some pseudocode:

Keep track of the number of circles total

While there are any friendships represented in the matrix
  Create a circle representation (array)
  Create a stack of people, starting with the frist one we saw that has a friendship
  While there are any people on the stack
    Pop a person off the stack
    Iterate over their friendships
    If 1 is found on the row (friendship)
      Unless circle already has friend
        Add the person to the circle
      Add the person to the stack
      Mark the friendship as visited by making it 0

  If the stack is empty
    The circle is complete so we should add it to the number of circles total

Once all friendships have been processed
Return the number of circles

This is basically a Breadth-First Search for each friend. As we come across new nodes on the friendship tree, we add them to the current circle and remove the friendship. When a circle is completed, we keep the process going starting with the next friendship. This next friendship will not have any friends within the first circle, otherwise they would have been found on the BFS. Thus, this new BFS will be a completely new friend circle. Finally, we keep on going, discovering new circles, until all of the friendships have been exhausted (all 0 in the matrix).

When starting with the code, I realized that I would need a helper method to determine whether or not the matrix had any friendships left, and if so, what student index i was the first one found?

# returns [true, index of first friend], or [false, -1]
def next_friendship(m)
  m.each_with_index do |row, i|
    row.each do |friendship|
      return [true, i] if friendship == 1
    end
  end

  return [false, -1]
end

We are told the input will always be a N by N matrix of arrays, with 1 <= N <= 200 so there is no need for empty or nil checks here. Now lets get started on some framework code for the main method.

# @param {Integer[][]} m
# @return {Integer}
def find_circle_num(m)

  circles = []
  has_friendships, i = next_friendship(m)

  while has_friendships
  end

  return circles.count
end

Running this as-is would obviously get stuck in the while loop forever, but shows how we will keep track of the friend circles overall, iterate over the matrix of friendships until there are none, then return the number of circles found. Let's get into the while loop:

# @param {Integer[][]} m
# @return {Integer}
def find_circle_num(m)

  circles = []
  has_friendships, i = next_friendship(m)

  while has_friendships
    stack = [i]
    circle = []

    while stack.any?
    end

    circles << circle
    has_friendships, i = next_friendship(m)
  end

  return circles.count
end

Running this as-is would still get stuck in a while loop forever, but shows that once we know we have friendships and know the first friend that has a friendship, we can use that to create a stack for us to start a BFS, keeping track of the found friends along the way inside of circles. When the stack is exhausted, our circle is complete, so we can add it to the overall circles collection, and setup the has_friendships variable for the outer while loop. Let's get into the inner while loop, the BFS:

# @param {Integer[][]} m
# @return {Integer}
def find_circle_num(m)

  circles = []
  has_friendships, i = next_friendship(m)

  while has_friendships
    stack = [i]
    circle = []

    while stack.any?
      person_i = stack.pop
      m[person_i].each_with_index do |relationship, person_j|
        if relationship == 1
          unless circle.include?(person_j)
            circle << person_j
            stack << person_j
          end
        end
        m[person_i][person_j] = 0
        m[person_j][person_i] = 0
      end
    end
    circles << circle
    has_friendships, i = next_friendship(m)
  end
  return circles.count
end

Inside the inner while loop, we first pop a friend off the stack, then iterate over all of that persons friends. At each person_j, if the relationship is a friendship (== 1), then we add it to the circle to denote that this person_j is a friend or a friend-of-a-friend of everyone there, and we also add this person_j to the stack to find their friends. Of course, we only want to add the friend person_j if we haven't already seen them before, so we check to see if the circle already includes person_j before doing so. Finally, we make sure that we mark this friendship as visited by making sure it is covered by a 0 in the friendship matrix.

This passes all LeetCode tests, but is not crazy fast:

Runtime: 76 ms, faster than 37.04% of Ruby online submissions for Friend Circles.
Memory Usage: 11 MB, less than 50.00% of Ruby online submissions for Friend Circles.

It's been awhile since I did any matrix manipulations in a computer science math class, but I seem to recall there were various tricks you could use to traverse a matrix and perform operations on them that are faster than iterations like I have done. This would probably speed things up. I could reduce memory usage by not storing the circles themselves, but just the counts, as I am never required to return the friend circles with members inside. I could probably go faster by deleting rows and columns of a student after processing them, so the overall matrix would get smaller and smaller as I go along. This would increase speed as well. I'll save all these potential optimizations for another day.

Was this page helpful for you? Buy me a slice of 🍕 to say thanks!