Ctrl K
Sign inStart free

Groups Linked by Shared Tags

Medium
Each of n objects carries exactly m tags, given as rows tags[i] (a row may repeat a tag). You also get an integer k. Two different objects are directly linked when they have at least k **distinct** tags in common. Links chain together: if a is linked to b and b to c, all three belong to the same group. Return the number of groups.
Example 1
tags=[[1, 2, 3], [3, 4, 5], [6, 7, 8], [8, 9, 6]], k=1 → 2

Rows 0 and 1 share tag 3, rows 2 and 3 share tags 6 and 8. The two pairs have nothing in common, so there are two groups.

Example 2
tags=[[5, 5, 1], [5, 1, 1]], k=2 → 1

There are two distinct common tags, 5 and 1. Repeats do not count twice, but two is enough, so there is one group.

Example 3
tags=[[4, 4], [4, 4]], k=2 → 2

Only one distinct tag (4) is shared and at least two are needed, so each row is on its own.

Constraints
  • 1 ≤ n = len(tags) ≤ 100
  • 1 ≤ m = len(tags[i]) ≤ 100, all rows have the same length
  • 1 ≤ tags[i][j] ≤ 100
  • 1 ≤ k ≤ m
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Depth-First SearchBreadth-First SearchUnion FindGraphArrayHash Table
Similar problemsRooms Open from the Hall MediumWhich Machine to Cure HardWhich Machine to Unplug HardRatio Chain Queries MediumMerge Contact Cards Medium
loading Python…
Input
tags=[[1, 2, 3], [3, 4, 5], [6, 7, 8], [8, 9, 6]], k=1
Expected
2

Run checks the first 3 tests in your browser. Submit checks all 95 tests on the server, hidden ones included.