Day 21 : Count Connected LL

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in companies
IntuitGoogle inc

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1 3 2 4 6 5 -1
2
1 3
1 3 7 4 -1 
3
1 7 4
Sample Output 1 :
1
2
Explanation For Sample Input 1 :
For the first test case :

1 3  appears consecutively in the linked list. So, they are connected.  
Count: 1

For the second test case :

1 and 7 4 are connected.
Count: 2
Sample Input 2 :
2
1 3 4 5 -1
4
1 3 4 5
1 2 -1
1
1
Sample Output 2 :
1
1
Hint

Traverse the recursively linked list while checking whether the value is present in the array or not.

Approaches (2)
Recursive 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 :
 

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

 

HELPER(TEMP, CHECK, MP):
 

  1. Base case :
    • If ‘TEMP’ is equal to ‘NULL’.
      • Return 0.
  2. 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.
  3. Else
    • Call the function recursively on the node next to ‘TEMP’ by updating the value of ‘CHECK’ by FALSE and return the result.
Time Complexity

O(N), where ‘N’ is the number of nodes in the linked list.
 

We traverse the linked list once recursively to count the number of connected components. Therefore, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

The recursive stack can contain the length of the linked list. We also use a map to store the values present in the array which can be up to ‘N’. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Day 21 : Count Connected LL
Full screen
Console