Domain 2MediumMEDIUM

Linked List Components

Traverse the linked list once while maintaining a state flag to count transitions from non-G nodes into G sequences.

Domain: medium•Updated: 2026-09-01
#Linear Scan#Hash Set#O(N)#O(M)

Problem Breakdown

We are given two inputs: head, which points to the start of a singly linked list containing unique integer values, and an array/list G representing a subset of those node values. Our goal is to count how many “connected components” exist within this set G. Two nodes in G belong to the same component if they appear consecutively in the linked list without any intervening nodes that are not present in G. Essentially, non-G nodes act as delimiters breaking a sequence of G-nodes into separate components.

Inputs:

  • head: Head node of a singly linked list (NN nodes).
  • G: List/array of integers (subset of values in the linked list).

Outputs:

  • An integer representing the count of connected components formed by consecutive elements from G.

Constraints & Edge Cases:

  • 1≤N≤10,0001 \le N \le 10,000 (List length).
  • Values are unique integers within range [0, N - 1].
  • 1≤∣G∣≤10,0001 \le |G| \le 10,000.
  • G is a subset of values in the list.
  • Edge cases to consider: List ends while inside a component (handled naturally), no nodes from G are adjacent at all (each forms its own component if separated by non-G or start/end).

Intuition

A naive approach might try to check every pair of elements in G to see if they form a path, but determining connectivity requires traversing the list structure. A brute-force traversal for each element would lead to O(N2)O(N^2) complexity due to repeated scanning.

Key Insight: We only care about whether we are currently “inside” a sequence of nodes belonging to G. If we encounter a node in G that wasn’t preceded by another node from G, it signifies the start of a new component (or continuation). Conversely, if we hit a node not in G, any current streak is broken.

Optimization: Since checking membership needs to be fast (O(1)O(1)), converting list G into a Hash Set (set) allows us to check existence instantly during the single pass over the linked list. This reduces complexity from quadratic to linear time relative to NN.

Approach

  1. Preprocessing: Convert the input array/list G into a Python set for constant-time lookups (O(M)O(M) where M is length of G).
  2. Initialization: Initialize a counter count = 0 and a boolean flag in_component = False. The flag tracks whether we are currently traversing nodes that belong to G.
  3. Traversal: Iterate through the linked list starting from head:
    • If the current node’s value exists in our set:
      • Check if in_component is already True.
        • If False, we have found a new sequence of G-nodes (either at start or after a gap). Increment count. Set in_component = True.
    • If the current node’s value does not exist in our set:
      • We are outside any component. Reset in_component to False.
  4. Termination: Once we reach the end of the list, return count. Note that if a sequence ends at the tail of the linked list, no reset is needed because there’s nothing left to process; the count was already incremented when entering the component.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the number of nodes in the linked list. We traverse the list exactly once (O(N)O(N)) and construct a set from G which takes O(M)O(M) (where M ≤N\le N). Total time is linear with respect to input size.
  • Space Complexity: O(M)O(M), where MM is the number of elements in G, required for storing the hash set used for lookups.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def numComponents(head: 'ListNode', G: list[int]) -> int:
    # Convert G to a set for O(1) lookup time. 
    # This is crucial because we need frequent membership checks during traversal.
    g_set = set(G)
    
    count = 0
    in_component = False
    
    curr = head
    while curr:
        if curr.val in g_set:
            # If current node is in G, check if this starts a new component sequence.
            # We only increment the counter when we transition from 'not in' to 'in'.
            if not in_component:
                count += 1
                in_component = True
        else:
            # Current node breaks connectivity; reset flag for next potential start.
            in_component = False
        
        curr = curr.next
    
    return count

# Example usage logic (not part of submission):
# head = ListNode(0)
# head.next = ListNode(1)
# head.next.next = ListNode(2)
# head.next.next.next = ListNode(3)
# G = [0, 1, 3]
# print(numComponents(head, G)) # Output: 2

Edge Cases Handled

  • Component at the end of list: The logic increments count when entering a component. If that component extends to the last node and ends there, no reset occurs because the loop terminates naturally; the count remains correct.
  • No consecutive G nodes (e.g., 0->2 with G=[0,1]): Node 0 enters (in_component=True). Node 2 is not in set -> in_component=False. Count stays at 1 for {0}. If node 3 was also in G later separated by non-G, it would trigger a new increment.
  • All nodes are in G: The flag remains True throughout the loop after the first element; count increments exactly once (at start). Correctly returns 1 component.
  • Empty list or single node: Loop runs once or zero times depending on implementation details, but constraints ensure N≥1N \ge 1. If head exists and is in G, count becomes 1 immediately.