# Friend Circles

• Just finding the number of connected islands in the 2D Matrix

• I think, the fact that we are given an adjacency matrix, the time complexity is O(N^2), even using DFS or BFS

• Agree with tiny_code, BFS/DFS's time complexity should be O(n^2) as well.

• Agree with tiny_code, time complexity should O(N^2).

• Yes you are right. I have updated it. Thanks.

• For the union-find complexity analysis: If we traverse over the complete matrix O(n^2) and union/find operations take O(n), wouldn't the complexity be O(n^3)?

• @sean46 It depends of your union/find implementation.A efficient one with rank and path compression, will give you O(1) on average.

• I have updated the complexity of union-find approach.Thanks.

• I think for Union-Find approach, the complexity could be O(n^2) if path compression is used. Union-Find complexity with path compression is O(m), which m is operations (either union/find); in this case, since m[i][j] = m[j][i], the union operation is at most n*(n-1)/2, therefore it is O(n^2)

• I think for approach 1, this test case will give an incorrect answer:[[0,0,0],[0,0,0],[0,0,0]]

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.