Last Updated: 21 Sep, 2021

Day 21 : Count Connected LL

Moderate

Asked in companies

Solve now

Problem statement

Ninjas is practicing problems on the linked list. He came across a problem in which he has given a linked list of ‘N’ nodes and an array ‘ARR’ of size ‘M’ that is the subset of the values present in the linked list. He has to print the number of connected components present in the array. Two values are said to be connected if they present next to each other in the linked list.

Input Format :

The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains the linked list separated by space and terminated by -1.

The second line of each test case contains an integer ‘M’, representing the size of the array ‘ARR’.

The third line of each test case contains ‘M’ space-separated integers, representing the array ‘ARR’.

Output Format :

For each test case, print the number of connected components.

Output for each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 3*10^3
1 <= M <= N
The linked list consists of unique integers only.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to traverse the linked list and check whether the value of the nodes is present in the array or not. We also use a map to store the values of the array so as to access them in constant time.

Here is the algorithm :

Store the elements of the array in the map (say, ‘MP’)
Create a variable (say, ‘TEMP’) that will be used to traverse the linked list and initialize it with the head of the linked list.
Create a variable (say, ‘CHECK’) that will be used for checking connected components and initialize it with FALSE.
Call the ‘HELPER’ function to find the number of connected components.

HELPER(TEMP, CHECK, MP):

Base case :
- If ‘TEMP’ is equal to ‘NULL’.
  - Return 0.
Check if data present at ‘TEMP’ is present in ‘MP’.
- If ‘CHECK’ is FALSE
  - Call the function recursively on the node next to ‘TEMP’ by updating the value of ‘CHECK’ by TRUE and return the result of a recursive call by 1 to it.
- Else
  - Call the function recursively on the node next to ‘TEMP’ by updating the value of ‘CHECK’ by TRUE and return the result.
Else
- Call the function recursively on the node next to ‘TEMP’ by updating the value of ‘CHECK’ by FALSE and return the result.

Solve now

02 Approach

This approach is similar to the previous approach. We traverse the linked list iteratively to check for the connected components.

Here is the algorithm :

Store the elements of the array in the map. (say, ‘MP’).
Create a variable (say, ‘TEMP’) that will be used to traverse the linked list and initialize it with the head of the linked list.
Create a variable (say, ‘CHECK’) that will be used for checking connected components and initialize it with FALSE.
Create a variable (say, ‘COUNT’) that will be used for storing the number of connected components and initialize it with 0.
Run a loop till ‘TEMP’ is not equal to ‘NULL’.
- Check if ‘DATA’ of ‘TEMP’ is present in the map.
  - Check if ‘CHECK’ is FALSE, increment ‘COUNT’ by 1.
  - Update ‘CHECK’ with TRUE.
- Else, update ‘CHECK’ with FALSE.
- Update ‘TEMP’ with node next to ‘TEMP’.
Finally, return ‘COUNT’.

Solve now