Linked List Components — HashSet Membership Count Explained

Problem Statement#

LeetCode 817 — Linked List Components Difficulty: Medium | Pattern: HashSet Membership + Component Counting

You are given the head of a linked list containing unique integer values and an integer array nums that is a subset of the linked list values. Return the number of connected components in nums, where two values are connected if they appear consecutively in the linked list.

Constraints:

• Number of nodes: 1 <= n <= 10^4
• 0 <= Node.val <= n
• All values in the list are unique.
• 1 <= nums.length <= n

Example 1:

Input:  head = [0, 1, 2, 3], nums = [0, 1, 3]
Output: 2
Explanation: 0 and 1 are consecutive in the list and both in nums -> component [0,1].
             3 is in nums but 2 is not -> component [3].
             Total: 2 components.

Example 2:

Input:  head = [0, 1, 2, 3, 4], nums = [0, 3, 1, 4]
Output: 2
Explanation: [0, 1] is a component (consecutive in list, both in nums).
             [3, 4] is a component.
             Total: 2 components.

Why This Problem Matters#

This problem elegantly translates a graph concept — connected components — into a simple linear scan on a linked list. Google and Bloomberg use it to test whether candidates can recognize when a "graph" problem actually reduces to a one-pass linear scan with set membership checks.

The naive graph approach would build an adjacency structure and run BFS/DFS to count components. But the linked list's linear structure means adjacency is purely determined by consecutive positions — if two nodes are neighbors in the list and both are in the set, they are in the same component. No actual graph construction is needed.

The O(n + k) solution (where k is the size of nums) demonstrates the important skill of choosing the right data structure: a HashSet for O(1) membership lookup transforms what looks like an O(n*k) problem into an O(n + k) solution.

This problem also appears in Amazon's interview preparation materials as a hash-set fluency test. Candidates who immediately think "convert nums to a set, then scan the list once" are flagged as strong engineers. Those who iterate through nums for each node in the list get O(n*k) — a red flag for large inputs.

The Core Insight#

Key observation: A new connected component begins when you enter a run of nodes that are all in nums. Specifically, a new component starts when the current node is in nums AND either:

• It is the first node in the list, or
• The previous node was NOT in nums

Equivalently, you can count component endings: a component ends when the current node is in nums AND the next node is either null or NOT in nums. Both counting strategies give the same answer.

Algorithm using component-start counting:

1. Convert nums to a HashSet for O(1) lookup.
2. Walk the list. When you enter a run of consecutive "in-set" nodes, count +1.
3. Use a boolean in_component flag to track whether you are currently inside a component.

Algorithm using component-end counting (equivalent, often cleaner): Walk the list. Increment count when the current node is in the set AND the next node is either null or not in the set.

Visual Dry Run#

Input: head = [0, 1, 2, 3, 4], nums = [0, 3, 1, 4]

Set: {0, 1, 3, 4}

Result: 2

Component-end counting (alternative view):

Result: 2

Solution (Optimal)#

from typing import Optional, List
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def numComponents(head: Optional[ListNode], nums: List[int]) -> int:
    # Step 1: Convert nums to a HashSet for O(1) lookup
    num_set = set(nums)
 
    count = 0
    in_component = False
    curr = head
 
    while curr:
        if curr.val in num_set:
            # Start a new component when entering from outside
            if not in_component:
                count += 1
                in_component = True
        else:
            # Leaving a component
            in_component = False
        curr = curr.next
 
    return count

function numComponents(head, nums) {
    // Step 1: Convert nums to a Set for O(1) lookup
    const numSet = new Set(nums);
 
    let count = 0;
    let inComponent = false;
    let curr = head;
 
    while (curr) {
        if (numSet.has(curr.val)) {
            // Enter new component from outside
            if (!inComponent) {
                count++;
                inComponent = true;
            }
        } else {
            // Exit the component
            inComponent = false;
        }
        curr = curr.next;
    }
 
    return count;
}

Alternative — count by component endings (equally correct):

def numComponents(head, nums):
    num_set = set(nums)
    count = 0
    curr = head
    while curr:
        if curr.val in num_set:
            # Count a component when it ends
            if curr.next is None or curr.next.val not in num_set:
                count += 1
        curr = curr.next
    return count

Complexity:

Common Mistakes#

1. Using a list instead of a set for nums: x in list is O(k). With a HashSet, lookup is O(1). Always convert to a set first.
2. Counting nodes instead of components: Each component can have multiple nodes. Only count when you START entering (or END leaving) a component, not for each node.
3. Not resetting the component flag on non-set nodes: The in_component flag must be set to False whenever you encounter a node not in the set, to correctly detect the start of the next component.
4. Confusing the order of nodes in nums vs list: The order of values in nums does not matter — what matters is the order of nodes in the linked list. Nodes in the list that are consecutive and both in nums form one component.
5. Building a graph unnecessarily: Do not construct adjacency lists or run BFS/DFS. The linked list's sequential structure means components are just maximal runs of in-set nodes.

Interview Tips#

• State the key insight immediately: "Connected components in a linked list are just maximal consecutive runs of nodes in the set. I can count them in one pass."
• Show the set conversion: "I convert nums to a HashSet so each membership check is O(1) rather than O(k)."
• Explain the flag approach: "I use an in_component boolean — when I first enter a run of in-set nodes, I increment the count. When I hit a non-set node, I reset the flag."
• Mention both counting strategies: You can count starts (entering) or ends (leaving). Both give the same answer. Show you understand why.
• Verify with example 2: head = [0,1,2,3,4], nums = [0,3,1,4]. Walk through your code to confirm count = 2.

Follow-up Questions#

1. What if the list had duplicate values? The constraint says all values are unique, but if not, you would need to track by node identity (pointer), not value.
2. What if nums had values not in the list? Those values are simply never seen during the scan — they do not affect the count. The set just has some extra entries.
3. What if you needed to return the actual components, not just the count? Collect node sequences when entering each component.
4. Can this be generalized to a doubly linked list? Identical logic — both prev and next are available, but for this problem, only the next direction matters.
5. What if the list were circular? You would need to track the starting node and stop when you complete the loop.

Key Takeaways#

• Convert nums to a HashSet immediately for O(1) membership checks. Linear list lookup would degrade this to O(n * k).
• Connected components in a linked list are maximal consecutive runs of nodes whose values are in the set.
• Use a boolean flag to count component starts — increment once when you enter a new run, not once per node.
• Alternatively, count component ends — increment when the current node is in the set but the next is not (or null).
• Total time is O(n + k): O(k) to build the set, O(n) to scan the list. Space is O(k).
• This pattern — "convert lookup target to a set, then scan the sequence once" — is a widely applicable interview technique worth memorizing.