Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def numComponents(self, head: ListNode, G: list[int]) -> int:
        Gset = set(G)
        curr = head
        count = 0
        inComponent = False
        while curr:
            if curr.val in Gset:
                if not inComponent:
                    count += 1
                    inComponent = True
            else:
                inComponent = False
            curr = curr.next
        return count
      

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <unordered_set>
class Solution {
public:
    int numComponents(ListNode* head, std::vector<int>& G) {
        std::unordered_set<int> Gset(G.begin(), G.end());
        int count = 0;
        bool inComponent = false;
        while (head) {
            if (Gset.count(head->val)) {
                if (!inComponent) {
                    count++;
                    inComponent = true;
                }
            } else {
                inComponent = false;
            }
            head = head->next;
        }
        return count;
    }
};
      

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numComponents(ListNode head, int[] G) {
        Set<Integer> Gset = new HashSet<>();
        for (int g : G) Gset.add(g);
        int count = 0;
        boolean inComponent = false;
        while (head != null) {
            if (Gset.contains(head.val)) {
                if (!inComponent) {
                    count++;
                    inComponent = true;
                }
            } else {
                inComponent = false;
            }
            head = head.next;
        }
        return count;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number[]} G
 * @return {number}
 */
var numComponents = function(head, G) {
    const Gset = new Set(G);
    let count = 0;
    let inComponent = false;
    while (head) {
        if (Gset.has(head.val)) {
            if (!inComponent) {
                count++;
                inComponent = true;
            }
        } else {
            inComponent = false;
        }
        head = head.next;
    }
    return count;
};
      

Problem Description

Given a singly linked list head and a list of integers G, you are to find the number of connected components in the linked list, where a connected component is defined as a maximal set of consecutive nodes such that every node's value is in G.

In other words, for every sequence of nodes in the linked list whose values are all in G and which are consecutive in the list, count it as one component. The same element from G cannot be reused in a different position, and each node in the list can appear in only one component.

Constraints:

• Each node value is unique.
• All values in G are contained in the linked list.
• There is exactly one valid solution for each input.

Thought Process

At first glance, the problem seems to require us to find all groups of consecutive nodes in the linked list whose values are in G. One naive approach could be to, for each node in G, traverse the linked list and check for consecutive nodes, but this would be very inefficient.

Instead, we realize that since the linked list is traversed only in one direction, we can simply walk through the list and keep track of whether we are currently inside a component (a streak of nodes in G). Each time we start a new streak (the current node is in G and the previous node was not), we increment our component count.

This leads us to a more optimal solution where we traverse the list once, using a set for fast lookups to check if a node's value is in G.

Solution Approach

• Step 1: Convert the list G to a set for O(1) lookups. This allows us to quickly check if a node's value is in G.
• Step 2: Initialize a counter (count) to zero to keep track of the number of components found.
• Step 3: Initialize a boolean flag (inComponent) to keep track of whether we're currently inside a component.
• Step 4: Traverse the linked list from head to the end:
  • If the current node's value is in the set and inComponent is false, this marks the start of a new component. Increment count and set inComponent to true.
  • If the current node's value is not in the set, set inComponent to false (we are outside a component).
• Step 5: Continue until the end of the list. The value of count will be the number of components.

This approach is efficient because we traverse the list only once and use a set for quick value checks.

Example Walkthrough

Example Input:
Linked list: 0 → 1 → 2 → 3
G = [0, 1, 3]

1. Convert G to a set: {0, 1, 3}
2. Start at node 0: value is in set and not in a component, so increment count to 1. Set inComponent to true.
3. Move to node 1: value is in set and inComponent is true, so continue (still in the same component).
4. Move to node 2: value is not in set, set inComponent to false.
5. Move to node 3: value is in set and inComponent is false, so increment count to 2. Set inComponent to true.
6. End of list; final count is 2.

Why? The two components are [0,1] and [3].

Time and Space Complexity

• Brute-force: If we checked for every possible sequence in the list, the time complexity would be O(N * |G|), where N is the number of nodes and |G| is the size of G.
• Optimized Approach: We traverse the list once (O(N)), and set lookups are O(1), so the total time complexity is O(N + |G|) (since building the set takes O(|G|)).
• Space Complexity: O(|G|) for storing the set.

This is efficient and scales well even for large lists and sets.

Summary

The key insight is to treat the problem as finding streaks of consecutive nodes from G in the linked list. By using a set for fast membership tests and a simple traversal with a state flag, we efficiently count the number of such streaks (components) in a single pass. This approach is elegant, easy to implement, and leverages fundamental data structures for optimal performance.