[Google Question][LeetCode] Linked List Components

Problem: We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Approach: A value 'val' in G is itself a connected component if the value of next node of the node with value 'val' does not exist in G. Right! Otherwise both the values are in the same connected component. We can solve this problem in many ways. 

One of the way is to start with an assumption that every value in G is a separate component and whenever we find that the value of next node of node with a value in G exist in G, we reduced the count of number of components. Here is how our algorithm will look like:

• node = head
• WHILE node != null
• hashMapList.Add(node.Value => node)
• node = node.Next
• for i = 0 to G.Length - 1
• hashSetG.Add(G[i])
• totalComponents = G.Length
• for i = 0 to G.Length - 1
• IF hashMapList[G[i]].next != null AND hashSetG.Contains(hashMapList[G[i]].next)
• totalComponents = totalComponents - 1
• RETURN totalComponents

This approach is fine and will work in linear time which we can't improve but here we are using two hashes; a hashmap and a hashset. Let's try to reduce the space.

Let's start with an assumption that we don't have any component. Now as per our definition, if a value exist in G and the value of the node which is next of node with same value does not exist in G then we have one connected component so if we traverse the list and see if current node's value does exist in G but its next node's value does not exist then we can increase the number of components by 1 so this approach will look like:

• for i = 0 to G.Length - 1
• hashSetG.Add(G[i])
• totalComponents = 0
• node = head
• WHILE node != null
• IF hashSetG.Contains(node.Value) AND (node.Next == null OR !hashSetG.Contains(node.Next.Value))
• totalComponents = totalComponents + 1
• node = node.Next
• RETURN totalComponents

If you see we are using less space and also we have reduced the number of loops

Implementation in C#:

Approach 1:

    public int NumComponents(ListNode head, int[] G) 

    {

        Dictionary<int, ListNode> listhash = new Dictionary<int, ListNode>();

        ListNode itr = head;

        while (itr != null)

        {

            listhash[itr.val] = itr;

            itr = itr.next;

        }

        HashSet<int> gHash = new HashSet<int>();

        foreach(int i in G)

        {

            gHash.Add(i);

        }

        int totalComponents = G.Length;

        foreach (int i in G)

        {

            if (listhash[i].next != null && gHash.Contains(listhash[i].next.val))

            {

                --totalComponents;

            }

        }

        return totalComponents;

    }

Approach 2:

    public int NumComponents(ListNode head, int[] G) 

    {

        HashSet<int> gHash = new HashSet<int>();

        foreach(int i in G)

        {

            gHash.Add(i);

        }

        int totalComponents = 0;

        ListNode itr = head;

        while (itr != null)

        {

            if (gHash.Contains(itr.val) && (itr.next == null || !gHash.Contains(itr.next.val)))

            {

                ++totalComponents;

            }

            itr = itr.next;

        }

        return totalComponents;

    }

Complexity: O(n)