Problem Link - Sequence Land
Problem Statement
N people live in Sequence Land. Instead of a name, each person is identified by a sequence of integers, called his or her id. Each id is a sequence with no duplicate elements. Two people are said to be each other’s relatives if their id's have at least K elements in common. The extended family of a resident of Sequence Land includes herself or himself, all relatives, relatives of relatives, relatives of relatives of relatives, and so on without any limit.
Given the ids of all residents of Sequence Land, including its President, and the number K, find the number of people in the extended family of the President of Sequence Land.
For example, suppose N = 4 and K = 2. Suppose the President has id (4, 6, 7, 8) and the other three residents have ids (8, 3, 0, 4), (0, 10), and (1, 2, 3, 0, 5, 8). Here, the President is directly related to (8, 3, 0, 4), who in turn is directly related to (1, 2, 3, 0, 5, 8). Thus, the President’s extended family consists of everyone other than (0, 10) and so has size 3.
Approach
We need to find the number of people who are in the extended family of the President. The key observation is that we can treat each person as a node and connect two people if their ids have at least K common elements. We can then treat the problem as a graph problem where each person is a node, and an edge exists between two nodes if they are related.
To solve this, we first read the ids of all people and store them. We then check for each pair of people if their ids have at least K elements in common. If they do, we create an edge between them. Now, to find the extended family of the President, we perform a breadth-first search (BFS) starting from the President. All reachable nodes from the President represent people in the extended family. The number of reachable people will give us the size of the extended family. We use BFS because it will explore all relatives, relatives of relatives, and so on, ensuring that we capture the entire extended family.
Time Complexity
The time complexity is O(N^2 \times M), where N is the number of people and M is the average size of each id, as we check every pair of people and count the common elements in their ids.
Space Complexity
The space complexity is O(N \times M), where N is the number of people and M is the average size of each id, as we store all id's and the graph.