I got this problem on a HackerRank challenge and this was the best I could come up with. It's basically just using DFS to find connected components (in this case, friend circles). I was having a tough time figuring out how to track unvisited nodes. Please let me know how I can improve this code. It appears to work, but the test cases given were quite simple.
Problem:
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also friend of C. A friend circle is a group of students who are directly or indirectly friends.
You have to complete a function int friendCircles(char[][] friends)
which returns the number of friend circles in the class. Its argument, friends, is a NxN
matrix which consists of characters "Y" or "N". If friends[i][j] == "Y"
then i-th and j-th students are friends with each other, otherwise not. You have to return the total number of friend circles in the class.
Sample Input 0:
4
YYNN
YYYN
NYYN
NNNY
Sample Output 0:
2
Explanation 0:
There are two pairs of friends [0, 1] and [1, 2]. So [0, 2] is also a pair of friends by transitivity.
So first friend circle contains (0, 1, 2) and second friend circle contains only student 3
Sample Input 1:
5
YNNNN
NYNNN
NNYNN
NNNYN
NNNNY
Sample output 1:
5
Constraints (sorry, couldn't get formatting down so I had to put the constraints down here):
- 1 <= N <= 300.
- Each element of matrix friends will be "Y" or "N".
- Number of rows and columns will be equal in friends.
- friends[i][j] = "Y", where 0 <= i < N.
- friends[i][j] = friends[j][i], where 0 <= i < j < N.
Solution:
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;
public class Solution {
public static int friendsCircle(char[][] friends) {
// The only alternative I could think of, instead of
// tracking unvisited nodes, was to put visited nodes
// in a set and then do setOfAllNodes.removeAll(visited)
// to see which nodes are still unvisited
Set<Integer> unvisited = new HashSet<>();
boolean[] visited = new boolean[friends.length];
Deque<Integer> stack = new ArrayDeque<>();
int connectedComponents = 0;
for (int i = 0; i < friends.length; i++) {
unvisited.add(i);
}
// dfs on friends matrix
while (!unvisited.isEmpty()) {
stack.push(unvisited.iterator().next());
connectedComponents++;
while (!stack.isEmpty()) {
int currVertex = stack.pop();
if (visited[currVertex] == false) {
visited[currVertex] = true;
unvisited.remove(currVertex);
for (int i = 0; i < friends[currVertex].length; i++) {
if (friends[currVertex][i] == 'Y' && visited[i] == false) {
stack.push(i);
}
}
}
}
}
return connectedComponents;
}
public static void main(String[] args) {
char[][] friends = {
{'Y','Y','N','N'},
{'Y','Y','Y','N'},
{'N','Y','Y','N'},
{'N','N','N','Y'}
};
System.out.println(friendsCircle(friends));
}
}