Katkat
Back

Count Similar Photo Groups

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of graph connectivity and equivalence relations, requiring recognition of connected components from an adjacency-matrix representation of pairwise similarity.

You are given n photos labeled 0 to n - 1 and an n x n binary matrix isSimilar.

  • isSimilar[i][j] = 1 means photo i and photo j are directly similar.
  • isSimilar[i][j] = 0 means they are not directly similar.

Similarity is also transitive: if photo A is similar to B, and B is similar to C, then A is considered similar to C even if A and C are not directly similar.

Treat each set of directly or indirectly similar photos as one photo group.

Return the total number of photo groups.

You may assume the similarity relationship is symmetric, so if isSimilar[i][j] = 1, then isSimilar[j][i] = 1.