Linked List Components - Video Solutions

Problem Overview: You are given the head of a linked list and an array nums containing a subset of node values. A component is a group of consecutive nodes in the list where every node value appears in nums. The task is to count how many such connected components exist.

Approach 1: Set for Quick Lookup (O(n) time, O(k) space)

The cleanest solution uses a hash table (set) to quickly check whether a node value exists in nums. Insert all values from nums into a set, then iterate through the linked list once. When the current node value exists in the set and the next node either does not exist in the set or is null, you found the end of a component. Increment the counter. The key insight: each component is counted exactly once at its boundary (the last node belonging to that component). Membership checks become O(1) due to hashing, so the full traversal remains linear. This approach is straightforward and performs well even when nums is large.

Approach 2: Two-Pass on Linked List without Extra Space (O(n * k) time, O(1) space)

If you want to avoid additional memory, skip the hash set and work directly with the array nums. Traverse the linked list and determine membership by scanning the nums array each time you need to check if a value belongs to the subset. Similar to the set approach, you detect a component when the current node value exists in nums and the next node either does not belong to nums or is null. Because each membership test scans the array, the complexity becomes O(n * k), where k is the size of nums. The benefit is constant extra space. This works when nums is small or memory usage is tightly constrained.

Recommended for interviews: The hash set approach is what most interviewers expect. It demonstrates that you recognize the repeated membership check and optimize it with constant-time lookups. Mentioning the no-extra-space variation shows awareness of trade-offs, but the O(n) hash set solution best balances clarity and efficiency.